文脈自由言語
文脈自由言語についての以下の問題は決定不能である。
等価性: 2つの文脈自由文法 A と B が与えられたとき、 L ( A ) = L ( B ) {\displaystyle L(A)=L(B)} か?
L ( A ) ∩ L ( B ) = ∅ {\displaystyle L(A)\cap L(B)=\emptyset } か?
L ( A ) = Σ ∗ {\displaystyle L(A)=\Sigma ^{*}} か?
L ( A ) ⊆ L ( B ) {\displaystyle L(A)\subseteq L(B)} か?
文脈自由言語についての以下の問題は決定可能である。
L ( A ) = ∅ {\displaystyle L(A)=\emptyset } か?
L(A) は有限か?
メンバーシップ: ある単語 w を与えたとき w ∈ L ( A ) {\displaystyle w\in L(A)} か?(メンバーシップ問題は多項式時間で決定可能である。CYK法を参照されたい)
基本的な文脈自由言語 L = { a n b n : n ≥ 1 } {\displaystyle L=\{a^{n}b^{n}:n\geq 1\}} は、偶数個の文字から成る文字列で構成され、各文字列の前半は a で、後半は b で構成される。L を生成する文法は S → a S b | a b {\displaystyle S\to aSb~|~ab} であり、プッシュダウン・オートマトン M = ( { q 0 , q 1 , q f } , { a , b } , { a , z } , δ , q 0 , { q f } ) {\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},\{q_{f}\})} に受容される。ここで δ {\displaystyle \delta } は以下のように定義される。