[Overview] [Previous] [Next]
More Example CFGs
Example 4
The language L = {w: w 
{a, b}*, na(w) = nb(w)}, where each string in L has an equal
number of a's and b's, is not regular. Consider the following grammar:
G = ({S}, {a, b}, S, {S
aSb,
SbSa, SSS,
S
}).
- Does every string recognized by this grammar have
an equal number of a's and b's?
- Is every string consisting of an equal number of
a's and b's recognized by this grammar?
Example 5
The language L, consisting of balanced strings of parentheses,
is context-free but not regular.
The grammar is simple, but we have to be careful to keep
our symbols
( and ) separate
from our metasymbols ( and ).
G = ({S}, {(, )}, S, {S(S),
SSS, S}).
Copyright © 1996 by David Matuszek
Last modified Feb 26, 1996