COSC 4P61: Theory of Computation Midterm, Oct. 30, 2020
Note: your answers must be precise, clear, legible, and as short as possible. Feel free to use the results/theorems/etc. that are covered in class or done in assignments without having to provide a proof. You can use your course notes and course notes only. No materials from other sources such as books and internet or discussions with others are allowed. please. The work submitted must be your own.
Please submit your finished midterm to Sakai.
1. (5) Design DFA’s (draw their transition diagrams) for the following two languages: (a) (ab∗a)∗; (b) The set of all strings over {0, 1} such that each prefix has at most one more 0’s than 1’s and at most one more 1’s than 0’s.
2. (4) A function f from N to N has a fixed point if there is some natural number i such that f(i) = i. For example, f(n) = n2 has a fixed point at 1. Using the technique of diagonalization, show that the set of functions that do not have fixed points is uncountable.
3. (8) Answer True or False for each of the following. Give a short proof to each of your answers. All languages are over alphabet Σ = {a, b, c, d}.
• If a language satisfies the pumping lemma, then it must be regular. • The union of infinite number of regular languages is also regular.
• Any non-regular language must be infinite.
• Any subset of a regular language must be regular.
• Any subset of a regular language must be non-regular. • abcd ∈ (a(cd)∗b)∗.
• For any languages L1 and L2, L1L2 = L2L1.
• If L is regular, L∗ must also be regular.
4. (4) Show that the set of all regular languages over any finite alphabet is countable.
5. (4) In A2, we see that when L∗ is regular, L itself does not have to be regular. An example is when L = {ap | for all primes p}. Is the converse true? That is, if L is non-regular, L∗ is always regular? Prove your answer.