Editing Context-free language (section)

==Examples==

An example context-free language is <math>L = \{a^nb^n:n\geq1\}</math>, the language of all non-empty even-length strings, the entire first halves of which are {{mvar|a}}'s, and the entire second halves of which are {{mvar|b}}'s. {{mvar|L}} is generated by the grammar <math>S\to aSb ~|~ ab</math>.
This language is not [[regular language|regular]].
It is accepted by the [[pushdown automaton#Formal definition|pushdown automaton]] <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\})</math> where <math>\delta</math> is defined as follows:<ref group="note">meaning of <math>\delta</math>'s arguments and results: <math>\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})</math></ref>

:<math>\begin{align}
\delta(q_0, a, z) &= (q_0, az) \\
\delta(q_0, a, a) &= (q_0, aa) \\
\delta(q_0, b, a) &= (q_1, \varepsilon) \\
\delta(q_1, b, a) &= (q_1, \varepsilon) \\
\delta(q_1, \varepsilon, z) &= (q_f, \varepsilon)
\end{align}</math>

Unambiguous CFLs are a proper subset of all CFLs: there are [[Inherently ambiguous language|inherently ambiguous]] CFLs. An example of an inherently ambiguous CFL is the union of <math>\{a^n b^m c^m d^n | n, m > 0\}</math> with <math>\{a^n b^n c^m d^m | n, m > 0\}</math>. This set is context-free, since the union of two context-free languages is always context-free. But there is no way to unambiguously parse strings in the (non-context-free) subset <math>\{a^n b^n c^n d^n | n > 0\}</math> which is the intersection of these two languages.{{sfn|Hopcroft|Ullman|1979|p=100|loc=Theorem 4.7}}

===Dyck language===

The [[Dyck language|language of all properly matched parentheses]] is generated by the grammar <math>S\to SS ~|~ (S) ~|~ \varepsilon</math>.