CS 334: Problem Set 4

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.