q 0 ⇒ aq 1 ⇒ aaq 2 ⇒ aabq 2 ⇒ aabaq f ⇒ aaba.
Figure 3.18
Equivalence of Regular Languages and Regular
Grammars
The previous two theorems establish the connection between regular languages
and right-linear grammars. One can make a similar connection between regular
languages and left-linear grammars, thereby showing the complete equivalence
of regular grammars and regular languages.
Theorem 3.5
A language L is regular if and only if there exists a left-linear grammar G such
that L = L ( G).
Proof: We only outline the main idea. Given any left-linear grammar with
productions of the form
A Bv,
or
A v,
we construct from it a right-linear grammar by replacing every such
production of G with
A→ v R B,