Problem Set 3 Solution

Description

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

1. What is the language generated by G?

2. Show that G is ambiguous.

3. Give an unambiguous grammar that generates the language of G.

4. 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)

1. Prove that the language { : , ≥ 0} is not context free.

2. Prove that the language { ⁺ : , ≥ 0} is context free.

Problem 6. (10 points) Give a CFG for { ∶ , ≥ 0} ∪ { ∶ 1, ≥ 0}. Is your grammar ambiguous?