[Overview] [Previous] [Next]
# More Example CFGs

## Example 4

The language L = {w: w
{a, b}*, n_{a}(w) = n_{b}(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, {SaSb,
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