Editing Context-free grammar (section)

== Examples ==

{{more citations needed section|date=July 2018}}

=== 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}}

=== Well-formed parentheses ===
The canonical example of a context-free grammar is parenthesis matching, which is representative of the general case. There are two terminal symbols {{math|(}} and {{math|)}} and one nonterminal symbol {{math|''S''}}. The production rules are
: {{math|''S'' → ''SS''}},
: {{math|''S'' → (''S'')}},
: {{math|''S'' → ()}}

The first rule allows the {{math|''S''}} symbol to multiply; the second rule allows the {{math|''S''}} symbol to become enclosed by matching parentheses; and the third rule terminates the recursion.{{sfn|Hopcroft|Ullman|1979|loc=Exercise 4.1b|p=103}}

=== Well-formed nested parentheses and square brackets ===

A second canonical example is two different kinds of matching nested parentheses, described by the productions:
: {{math|''S'' → ''SS''}}
: {{math|''S'' → ()}}
: {{math|''S'' → (''S'')}}
: {{math|''S'' → []}}
: {{math|''S'' → [''S'']}}
with terminal symbols {{math|[}}, {{math|]}}, {{math|(}}, {{math|)}} and nonterminal {{math|''S''}}.

The following sequence can be derived in that grammar:
: {{math|([ [ [ ()() [ ][ ] ] ]([ ]) ])}}

=== Matching pairs ===
In a context-free grammar, we can pair up characters the way we do with [[bracket]]s. The simplest example:
: {{math|''S'' → a''Sb''}}
: {{math|''S'' → ab}}

This grammar generates the language {{math|{{mset|a<sup>''n''</sup>b<sup>''n''</sup> : ''n'' ≥ 1}}}}, which is not [[regular language|regular]] (according to the [[pumping lemma for regular languages]]).

The special character {{math|ε}} stands for the empty string. By changing the above grammar to
: {{math|''S'' → a''S''b}}
: {{math|''S'' → ε}}
we obtain a grammar generating the language {{math|{{mset|a<sup>''n''</sup>b<sup>''n''</sup> : ''n'' ≥ 0}}}} instead. This differs only in that it contains the empty string while the original grammar did not.

=== Distinct number of as and bs ===

A context-free grammar for the language consisting of all strings over {{mset|a, b}} containing an unequal number of {{math|a}}s and {{math|b}}s:
: {{math|''S'' → ''T'' {{pipe}} ''U''}}
: {{math|''T'' → ''V''a''T'' {{pipe}} ''V''a''V'' {{pipe}} ''T''a''V''}}
: {{math|''U'' → ''V''b''U'' {{pipe}} ''V''b''V'' {{pipe}} ''U''b''V''}}
: {{math|''V'' → a''V''b''V'' {{pipe}} b''V''a''V'' {{pipe}} ε}}
Here, the nonterminal {{math|''T''}} can generate all strings with more as than {{math|b}}s, the nonterminal {{math|''U''}} generates all strings with more {{math|b}}s than {{math|a}}s and the nonterminal {{math|''V''}} generates all strings with an equal number of {{math|a}}s and {{math|b}}s. Omitting the third alternative in the rules for {{math|''T''}} and {{math|''U''}} does not restrict the grammar's language.

=== Second block of bs of double size ===

Another example of a non-regular language is <math> \{ \text{b}^n \text{a}^m \text{b}^{2n} : n \ge 0, m \ge 0 \} </math>. It is context-free as it can be generated by the following context-free grammar:
: {{math|''S'' → b''S''bb {{!}} ''A''}}
: {{math|''A'' → a''A'' {{!}} ε}}

=== First-order logic formulas ===

The [[First-order logic#Formation rules|formation rules]] for the terms and formulas of formal logic fit the definition of context-free grammar, except that the set of symbols may be infinite and there may be more than one start symbol.