states q 0 , q 1 ,…, and introduce a “parallel” automaton with states
Then arrange matters so that the spurious symbol
nondeterministically transfers from any state of the original automaton
to the corresponding state in the parallel part. For example, if part of
the original dfa looks like
then the dfa with its parallel will be an nfa whose corresponding part is
It is not hard to make the argument that the original dfa accepts L if and
only if the constructed nfa accepts insert (L).
Section 3.3
4. Right linear grammar:
Left linear grammar:
8. We can show by induction that if w is a sentential form derived with G, then
w R can be derived in the same number of steps by .
Because w is created with left linear derivations, it must have the form w =
Then arrange matters so that the spurious symbol
nondeterministically transfers from any state of the original automaton
to the corresponding state in the parallel part. For example, if part of
the original dfa looks like
then the dfa with its parallel will be an nfa whose corresponding part is
It is not hard to make the argument that the original dfa accepts L if and
only if the constructed nfa accepts insert (L).
Section 3.3
4. Right linear grammar:
Left linear grammar:
8. We can show by induction that if w is a sentential form derived with G, then
w R can be derived in the same number of steps by .
Because w is created with left linear derivations, it must have the form w =