Figure 3.17
Right-Linear Grammars for Regular Languages
To show that every regular language can be generated by some right-linear
grammar, we start from the dfa for the language and reverse the construction
shown in Theorem 3.3. The states of the dfa now become the variables of the
grammar, and the symbols causing the transitions become the terminals in the
productions.
Theorem 3.4
If L is a regular language on the alphabet ∈, then there exists a right-linear
grammar G = (V, E,S, P) such that L = L < (G).
Proof: Let M = (Q, E,δ,q 0 ,F) be a dfa that accepts L. We assume that Q = {q 0 ,q 1 ,
…,qn} and Σ = {a 1 ,a 2 ,…,a m }. Construct the right-linear grammar G =(V, E,S,P)
with
V = {q 0 ,q 1 ,…,q n }
and S = q 0 . For each transition
δ( q i ,a j )=q k
of M, we put in P the production
In addition, if q k is in F, we add to P the production