Problem Set 4 Solution

Description

Problem 1. (15 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.

Problem 2. (25 points)

1. (3 points) Prove that if is a regular language, then so is ^̅,the complement of .

2. (2 points) Prove that if , are each regular, then so is − , the difference of and .

3. (10 points) Show that the language

= { : , , ≥ 0 and = 1 ⇒ = }

satisfies the three conditions of the pumping lemma. Hint: set the pumping threshold to 2 and argue that every string in can be divided into three parts to satisfy the conditions of the pumping lemma.

4. (5 points) Prove that is not regular. Use the result of part (b), and note that

= ^{∗ ∗}∪ ^{∗ ∗ ∗}∪{ : ≥0}.

4. (5 points) Explain why parts (c) and (d) do not contradict the pumping lemma.

Optional Problem. (20 points)

In class we showed how to convert a DFA = ( , Σ, , ₀, ) into a reduced DFA

= ( , Σ, , ₀ , ) where = {[ ]: ∈ }, = {{ ]: ∈ }, ₀ = [ ], ([ ], ) = [ ( , )] ∀ ∈ Σ, ∈ .

1. Show that [ ] ∈∈ .

2. Prove, by induction on the length of string :

∀ ∈ Σ^∗ ∶ ([ ], ) = [ ( , )].

3. Prove that ( ) = ( ).

3. Show that is the minimum state DFA for ( ) by showing that every pair of states of is distinguishable.

3. Use the result of part (d) to argue that every DFA for the language = {1 } has at least + 2 states.