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

## Example 1

We have shown that L = {a^{n}b^{n}: n
0} is not regular. Here is a context-free grammar for this language.
G = ({S}, {a, b}, S, {SaSb,
S}

## Example 2

We have shown that L = {a^{n}b^{k}: k > n
0} is not regular. Here is a context-free grammar for this language.
G = ({S, B}, {a, b}, S, {SaSb,
SB, BbB,
Bb}).

## Example 3

The language L = {ww^{R}: w
{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, {SaSa,
SbSb, S}).

Copyright © 1996 by David Matuszek

Last modified Feb 26, 1996