Editing Context-free grammar (section)

=== Words concatenated with their reverse ===

The grammar <math>G = (\{S\}, \{\mathrm{a}, \mathrm{b}\}, P, S)</math>, with productions
: {{math|''S'' → a''S''a}},
: {{math|''S'' → b''S''b}},
: {{math|''S'' → ε}},
is context-free. It is not proper since it includes an {{math|ε}}-production. A typical derivation in this grammar is
: {{math|''S'' → a''S''a → aa''S''aa → aab''S''baa → aabbaa}}.
This makes it clear that <math>L(G) = \{ww^R:w\in\{a,b\}^*\}</math>. 
The language is context-free; however, it can be proved that it is not [[Regular language|regular]].

If the productions
: {{math|''S'' → a}},
: {{math|''S'' → b}},
are added, a context-free grammar for the set of all [[palindrome]]s over the alphabet {{math|{{mset|a, b}}}} is obtained.{{sfn|Hopcroft|Ullman|1979|loc=Exercise 4.1a| p=103}}