With a few examples you should be able to convince yourself that if the
original dfa accepts a 1 a 2 a 3 a 4 , the new automaton will accept λa 2 λa 4 …, and
therefore even (L).
15. Suppose we have a dfa that accepts L. We then
(a) Identify all states that can be reached from q 0 , reading any twosymbol prefix v, that is,
(b) Introduce a new initial state p 0 and add
It should not be hard to see that the new nfa accepts chop2 (L). Although the
construction is plausible, a complete answer requires a proof of the last
statement.
Section 2.4
2. (c)
This is minimal for the following reason. q 3 F and q 4 ∈ F, so q 3 and q 4
are distinguishable. Next, δ * (q 2 , a) F and δ * (q 4 , a) ∈ F, so q 2 and q 4 are
distinguishable. Similarly, δ * (q 1 , aa) F and δ * (q 3 , aa) ∈ F, so q 1 and q 3
are distinguishable. Continuing this way, we see that all states are
original dfa accepts a 1 a 2 a 3 a 4 , the new automaton will accept λa 2 λa 4 …, and
therefore even (L).
15. Suppose we have a dfa that accepts L. We then
(a) Identify all states that can be reached from q 0 , reading any twosymbol prefix v, that is,
(b) Introduce a new initial state p 0 and add
It should not be hard to see that the new nfa accepts chop2 (L). Although the
construction is plausible, a complete answer requires a proof of the last
statement.
Section 2.4
2. (c)
This is minimal for the following reason. q 3 F and q 4 ∈ F, so q 3 and q 4
are distinguishable. Next, δ * (q 2 , a) F and δ * (q 4 , a) ∈ F, so q 2 and q 4 are
distinguishable. Similarly, δ * (q 1 , aa) F and δ * (q 3 , aa) ∈ F, so q 1 and q 3
are distinguishable. Continuing this way, we see that all states are