[Overview] [Previous] [Next]

Languages and Grammars

A regular language is a language that can be defined by a regular grammar.

A context-free language is a language that can be defined by a context-free grammar.

If grammar G is context free but not regular, we know the language L(G) is context free. We do not know that L(G) is not regular. It might be possible to find a regular grammar G2 that also defines L.

Example

Consider the following grammar:

G = ({S, A, B}, {a, b}, S, {Sgoes toAB, Agoes toaA, Agoes toempty string, Bgoes toBb, Bgoes toempty string})

Is G a context-free grammar?
Yes.

Is G a regular grammar?
No.

Is L(G) a context-free language?
Yes.

Is L(G) a regular language?
Yes -- the language L(G) is regular because it can be defined by the regular grammar:

G = ({S, A, B}, {a, b}, S, {Sgoes toA, Agoes toaA, Agoes toB, Bgoes tobB, Bgoes toempty string})


Copyright 1996 by David Matuszek
Last modified Feb 26, 1996