[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 G_{2}
that also defines L.

## Example

Consider the following grammar:
G = ({S, A, B}, {a, b}, S, {SAB,
AaA, A,
BBb, B})

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, {SA,
AaA, AB,
BbB, B})

Copyright © 1996 by David Matuszek

Last modified Feb 26, 1996