[Overview] [Previous] [Next]

Example CFGs

Example 1

We have shown that L = {anbn: n >= 0} is not regular. Here is a context-free grammar for this language.

G = ({S}, {a, b}, S, {Sgoes toaSb, Sgoes toempty string}

Example 2

We have shown that L = {anbk: k > n >= 0} is not regular. Here is a context-free grammar for this language.

G = ({S, B}, {a, b}, S, {Sgoes toaSb, Sgoes toB, Bgoes tobB, Bgoes tob}).

Example 3

The language L = {wwR: w is a member of {a, b}*}, where each string in L is a palindrome, is not regular. Here is a context-free grammar for this language.

G = ({S}, {a, b}, S, {Sgoes toaSa, Sgoes tobSb, Sgoes toempty string}).


Copyright 1996 by David Matuszek
Last modified Feb 26, 1996