Grammars for Regular
Languages
Theorem: For every RLG G, there is an FA M such that L(G) = L(M).
Proof: See page 575 in [Meduna:
Automata and Languages]
Conclusion: Grammars for regular languages are
Right-linear grammar
Theorem: For every FA M, there is a RLG G such that L(M) = L(G).
Proof: See page 583 in [Meduna:
Automata and Languages]
35/45