Sale!

CS 334: Problem Set 4

$30.00

Category:
Rate this product

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.

Open chat
Need help?
Hello
Can we help you?