[Overview] [Previous] [Next]

Regular Grammars Are Context Free

Recall that productions of a right-linear grammar must have one of the two forms
A goes to x
or
A goes to xB
where Since T* is a proper subset of (V union T)* and T*V is a proper subset of (V union T)*, it follows that every right-linear grammar is also a context-free grammar.

Similarly, right-linear grammars and linear grammars are also context-free grammars.

Important! A context-free language (cfl) is a language that can be defined by a context-free grammar.


Copyright 1996 by David Matuszek
Last modified Feb 26, 1996