文脈自由文法
文脈自由文法は数学的な「形式的」言語だけで利用されるわけではない。例えば、タミル語の詩である Venpa は文脈自由文法で定式化できることが指摘されている。
言語 L {\displaystyle L\,} は、 L = L ( G ) {\displaystyle L\,=\,L(G)} となるような文脈自由文法 G {\displaystyle G\,} が存在するとき、文脈自由言語(CFL)であるという。
任意の u , v ∈ ( V ∪ Σ ) ∗ {\displaystyle u,v\in (V\cup \Sigma )^{*}} について、 u {\displaystyle u\,} が v {\displaystyle v\,} を生成することを u ⇒ v {\displaystyle u\Rightarrow v} で表す。ただし、 u = u 1 α u 2 {\displaystyle u\,=u_{1}\alpha u_{2}} かつ v = u 1 β u 2 {\displaystyle v\,=u_{1}\beta u_{2}} で ∃ ( α , β ) ∈ R , u 1 , u 2 ∈ ( V ∪ Σ ) ∗ {\displaystyle \exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}} が成り立たねばならない。