Example CFGs

Example 1

We have shown that L = {aⁿbⁿ: n

0} is not regular. Here is a context-free grammar for this language.

G = ({S}, {a, b}, S, {SaSb, S}

We have shown that L = {aⁿ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}).

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}).