CS154 Spring 2020Practice Midterm

Due to the coronavirus the midterm will be online and open book/internet. That said, you will be on the honor system not to communicate with other members of the class or internet community about problems on the test. I will give 24 hours from when I post the test to complete it. If you have a correctly filed AEC accommodation and need more time please send me an email.

To study for the midterm I would suggest you:

• Know how to do (by heart) all the practice problems.
• Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
• Go over the homework problems.
• Try to create your own problems similar to the ones I have given and solve them.
• Skim the relevant sections from the book.
• If you want to study in groups, at this point you are ready to quiz each other.

The practice midterm is below.

1. Define the following set theory concepts: (a) one set is a subset of another (define using `in`), (b) ordered pair `(a,b)` (define as a set), (c) partition of sets.
2. Prove: (a) the set of even numbers is countable. (b) `sum_{i=1}^n i^2 = Omega(n^3)`.
3. The binary relation on pair integers `tilde` given by `(a, b)` `\tilde` `(c, d)` iff `a cdot d=c cdot b` is an equivalence relation.
4. Given a graph `G=(V,E)` and two vertices `s, t in V`, give the algorithm from class to determine a path from `s` to `t` in `G` if it exists.
5. (a) Draw a DFA for the language: {w | w has 010 as a substring}. (b) Write down your DFA formally as a 5-tuple. (c) Prove formally your machine accepts the string 10101.
6. Show that the class of regular languages is closed under (a) intersection, (b) homomorphism.
7. Explain how the DFA state minimization algorithm from class works. Give a concrete example of using it.
8. Use the algorithms from class (a) to step-by-step convert the regular expression `(00 cup 11)^{\star}` to an NFA. (b) convert this NFA to a DFA (only need to show portion reachable from start state).
9. Show step by step how the algorithm from class could determine directly from the NFA (no powerset construction) of the last problem whether 001101 was in the language or not.
10. Prove {w| `w=xy` such that `x in {0,1}^\star`, `y \in {0}^{\star}` and `|x|=|y|` } is not regular.