Problem 1. (10 points) Apply the DFA minimization algorithm to the DFA shown below. Show the matrix of distinguishable pairs of states after each iteration of the loop. Finally, give a regular expression that describes the language of the DFA.
Problem 2. (10 points) Consider the following languages:
= {0 : ≥ 1, ∈ {0,1}∗, 0 }
= {0 : ≥ 1, ∈ {0,1}∗, 0 }
For each language, prove whether it is regular or non-regular.
Problem 3. (10 points) Consider the following CFG G:
→ |
→ 0 1 | 01
What is the language generated by G?
Show that G is ambiguous.
Give an unambiguous grammar that generates the language of G.
Give an argument showing that your grammar in part (c) is unambiguous.
Problem 4. (10 points) Give a CFG for the language of palindromes over the alphabet {0,1}. Is the language of palindromes that contain equal numbers of 0s and 1s context free? Either give a CFG for this language or prove that it is not context free.
Problem 5. (10 points)
Prove that the language { : , ≥ 0} is not context free.
Prove that the language { + : , ≥ 0} is context free.
Problem 6. (10 points) Give a CFG for { ∶ , ≥ 0} ∪ { ∶ 1, ≥ 0}. Is your grammar ambiguous?
