We first show that G defined in this way can generate every string in L.
Consider w ∈ L of the form
w = a i a j …. a k a l .
For M to accept this string it must make moves via
By construction, the grammar will have one production for each of these δ’s.
Therefore, we can make the derivation
with the grammar G, and w ∈ L(G).
Conversely, if w ∈ L(G), then its derivation must have the form (3.7). But
this implies that
δ* (q 0 , a i a j …a k a i )= q f ,
completing the proof.
For the purpose of constructing a grammar, it is useful to note that the
restriction that M be a dfa is not essential to the proof of Theorem 3.4. With
minor modification, the same construction can be used if M is an nfa.
Example 3.16
Construct a right-linear grammar for L (aab*a). The transition function for an
nfa, together with the corresponding grammar productions, is given in Figure
3.18. The result was obtained by simply following the construction in Theorem
3.4. The string aaba can be derived with the constructed grammar by
Consider w ∈ L of the form
w = a i a j …. a k a l .
For M to accept this string it must make moves via
By construction, the grammar will have one production for each of these δ’s.
Therefore, we can make the derivation
with the grammar G, and w ∈ L(G).
Conversely, if w ∈ L(G), then its derivation must have the form (3.7). But
this implies that
δ* (q 0 , a i a j …a k a i )= q f ,
completing the proof.
For the purpose of constructing a grammar, it is useful to note that the
restriction that M be a dfa is not essential to the proof of Theorem 3.4. With
minor modification, the same construction can be used if M is an nfa.
Example 3.16
Construct a right-linear grammar for L (aab*a). The transition function for an
nfa, together with the corresponding grammar productions, is given in Figure
3.18. The result was obtained by simply following the construction in Theorem
3.4. The string aaba can be derived with the constructed grammar by