[Overview] [Previous] [Next]

More Example CFGs

Example 4

The language L = {w: w is a member of {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, {Sgoes toaSb, Sgoes tobSa, Sgoes toSS, Sgoes toempty string}).

  1. Does every string recognized by this grammar have an equal number of a's and b's?
  2. 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, {Sgoes to(S), Sgoes toSS, Sgoes toempty string}).


Copyright 1996 by David Matuszek
Last modified Feb 26, 1996