CS 334: Problem Set 4.

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)

a) (3 points) Prove that if π΄ is a regular language, then so is π΄Μ
, the complement of π΄.

b) (2 points) Prove that if π΄, π΅ are each regular, then so is π΄ β π΅, the difference of π΄ and π΅.

c) (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.

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

πΏ = π

β

π

β βͺ πππ

βπ

β

π

β βͺ {ππ

π

π

π

: π β₯ 0}.

e) (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 π = (π, Ξ£, πΏ, π0, πΉ) into a reduced DFA

ππ
= (ππ
, Ξ£, πΏπ
, π0π
, πΉπ

) where ππ
= {[π]: π β π}, πΉπ
= {{π]: π β πΉ},

π0π
= [ππ

], πππ πΏπ

([π], π) = [πΏ(π, π)] βπ β Ξ£, π β π.

(a) Show that [π] β πΉπ
ππ πππ ππππ¦ ππ π β πΉ.

(b) Prove, by induction on the length of string π€:

βπ€ β Ξ£

β

βΆ Ξ([π], π€) = [Ξ(π, π€)].

(c) Prove that πΏ(π) = πΏ(ππ
).

(d) Show that ππ
is the minimum state DFA for πΏ(π) by showing that every pair of states

of ππ
is distinguishable.

(e) Use the result of part (d) to argue that every DFA for the language πΏπ = {1

π

} has at least

π + 2 states.

Sale!