(^64) FINITE AUTOMATA
(3) We accept (I: if the two parallel simulations of step (2) end at a same
state Q~C (which is not required to be in F).
To implement this idea of parallel simulation, we need two tracks in the
states of the new machine, one track simulates AI on x and the other simulates
M on y. That is, our new NFA IV’, like the product automaton AI x M, uses
states in Q x Q. More precisely, we define NFA AI’ = (Q’, C, S’, s, F’) by
Q’ = (Q x Q) u (s), F’ = {[qi,qi] 1 qi E Q} and
Note that, in an NFA, we actually cannot guess a string y and verify that
1x1 = Iyl, but we can guess the symbols of y one at a time. This guessing
technique is implemented above in the definition of S’([qi, qj], a). From the
above discussion, it follows that AI’ accepts LL 2. cl
Proof 2. Let AI = (Q, X,6, qo, F) be a DFA accepting L, with Q = (40,
Ql, l * ‘9 qn}. The idea of this construction is a combination of the product
automaton method and the simulation idea of Example 2.40. That is, we
need to nondeterministically guess a state qa and a string y, then we simulate
IV, in parallel, on x from state qo and on y from state qi. We accept x: if the
first simulation ends at state qi and the second simulation ends at a state in F.
Since we simulate them in parallel, the guessed string y must have 1~1 = 1x1.
To implement this idea, we define, for each state q; E Q, an NFA &!i =
(Q,c,&qiJ) by
Qlj4) = (S(qj,b) 1 b E C}*
(All NFA’s A,& h ave the same transition function Z) The NFA I@ then
simulates AI on all strings y, starting from state qi.
Then, we combine machine AI and machines AIi into a new NFA AI’ with
IQ1 + 1 tracks, with the first track simulating AI on x and the (i + 1)st track
simulating IUi on y. Formally, JI’ = (Q’, C, S’, s, F’), where Q’ = Qn+2,
s=[qO,QO,Q1,..~,Qn],F'={[q~,qj,,qj,,...,4j,](0<i~n,qjiEF},and
The second proof above, though creating an NFA with more states than
that in the first proof, is a more general proof technique with many applica-
tions. The following is another example.
- Example 2.42 Show that if L is a regular set, so is