曖昧な文法
ある言語(文法によって生成される文字列の集合)は曖昧な文法と曖昧でない文法と対応しているが、曖昧でない文法とは対応しない言語も存在する。本質的に曖昧な言語の例として、 { a n b m c m d n | n , m > 0 } {\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}} と { a n b n c m d m | n , m > 0 } {\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}} の和集合がある。これは文脈自由言語の和集合なので文脈自由だが、参考文献に挙げた Introduction to Automata Theory... には、2つの言語の積集合 { a n b n c n d n | n > 0 } {\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}} の部分集合(文脈自由でない)の文字列を曖昧でなく構文解析する方法がないことの証明が掲載されている。