Chomsky階層

（文法の符号化）終端記号が $0,1$ の文脈依存文法は、変数記号の名前を $A_1,\ldots,A_k$（開始記号を $A_1$）と付け替えれば、次の七個の記号からなる文字列として書ける：$0$、$1$、$\mathtt{A}$、$\mathtt{i}$、$\mathtt{e}$、$\mathtt{>}$、$\mathtt{;}$。変数記号 $A_j$ を $\mathtt{A}\mathtt{i}^{j}$、空語を $\mathtt{e}$ と書き、規則 $\alpha\to\beta$ を「$\alpha$ の表記、$\mathtt{>}$、$\beta$ の表記」と書き、規則を $\mathtt{;}$ で区切って並べる。七個の記号に長さ $3$ の $0,1$ の列を一つずつ割り当てて置き換えれば、文法は $\{0,1\}^{*}$ の文字列として表される。これを文法の符号という。名前の付け替えは導出を一対一に移すので生成言語を変えず、したがって終端記号が $0,1$ のどの文脈依存文法 $G$ についても、$L(G')=L(G)$ となる文法 $G'$ の符号が存在する。
文字列 $w\in\{0,1\}^{*}$ が符号であるかどうかは、長さが $3$ の倍数かを見て三文字ずつ七個の記号に戻し、上の書式に合っているか、各規則が 文脈依存言語 の記事の定義「文脈依存文法」の形をしているか（左辺と右辺の共通の文脈を除いて一つの変数記号が空でない列に置き換わっているか、$A_1\to\varepsilon$ があるなら $A_1$ が右辺に現れないか）を調べれば、有限回の操作で判定できる。$w$ が符号のとき、それが表す文法を $G_w$ と書く。
（対角線論法）
$$D:=\{\,w\in\{0,1\}^{*}\mid w\text{ は符号でない}\ \text{または}\ \bigl(w\text{ は符号で }w\notin L(G_w)\bigr)\,\}$$
とおく。
$D$ は文脈依存言語でない：$D=L(G)$ となる文脈依存文法 $G$ があったとすると、上により $L(G_{w_0})=L(G)=D$ となる符号 $w_0$ がある。$w_0$ は符号なので、$D$ の定義により $w_0\in D\iff w_0\notin L(G_{w_0})=D$ となり、矛盾する。
$D$ は帰納的である：入力 $w$ に対し、まず $w$ が符号かどうかを判定し、符号でなければ受理する。符号なら、文脈依存言語 の記事の命題「所属問題の決定可能性」の手続き（長さ $|w|$ 以下の文字列を頂点とする有限グラフの到達可能性を調べる）で $w\in L(G_w)$ かどうかを判定し、属するなら拒否、属さないなら受理する。どの段階も有限の探索であり、文法と入力を入力として受け取って一様に実行できるので、すべての入力で停止する Turing 機械として実現できる。有限で一様な手続きを Turing 機械として書けることは、アルゴリズムを Turing 機械と同一視する Church–Turing のテーゼの立場（MSm24 §4.4、pp. 151–152）による。機械の構成はこの記事では証明しない。

$\Sigma$ の相異なる二文字を $0,1$ と書き、$\{0,1\}$ 上の言語を $\Sigma$ 上の言語ともみなす。
（包含）$\mathcal{L}_3\subset\mathcal{L}_2$ は 文脈自由言語 の記事の命題「正規言語は文脈自由言語である」、$\mathcal{L}_2\subset\mathcal{L}_1$ は 文脈依存言語 の記事の命題「文脈自由言語は文脈依存言語である」による。$\mathcal{L}_1\subset\mathcal{R}$ は 文脈依存言語 の記事の命題「所属問題の決定可能性」の手続きが Turing 機械で実現できることによる（線形有界オートマトン の記事の命題「所属問題の決定可能性」も同じ議論）。この「実現できる」は prop-ch-diagonal の証明と同じく Church–Turing のテーゼの立場（MSm24 §4.4、pp. 151–152）によるもので、機械の構成はこの記事では証明しない。$\mathcal{L}_1\subset\mathcal{R}$ と $\mathcal{L}_1\ne\mathcal{R}$ はこの立場に依存している。$\mathcal{R}\subset\mathcal{L}_0$ は、帰納的言語を判定する機械はその言語を受理する Turing 機械でもあるので、句構造言語 の記事の定理「Turing 機械との同値性」による。
（真の包含）$\mathcal{L}_3\ne\mathcal{L}_2$：$\{0^{n}1^{n}\mid n\in\mathbb{N}\}$ は文脈自由だが正規でない（ex-ch-separating の一つ目）。$\mathcal{L}_2\ne\mathcal{L}_1$：$P_2:=\{0^{2^{k}}\mid k\in\mathbb{N}\}$ は文脈依存だが文脈自由でない。文脈依存であることは、線形有界オートマトン の記事の例「2 の冪乗の長さの文字列」の機械（$a$ を $0$ と読み替える）に「$0$ 以外の文字を読んだら止まる」ことを加えたものが $P_2$ を受理することと、同じ記事の定理「文脈依存言語との同値性」による。文脈自由でないことを示す。$P_2=L(G)$ となる $\Sigma$ 上の文脈自由文法 $G$ があったとする。文脈自由文法の導出では一度現れた終端記号は消えないので、$P_2$ の元の導出は右辺に $0$ 以外の終端記号を含む規則を使わない。そこでそのような規則を除いた $\{0\}$ 上の文脈自由文法 $G'$ をとると $L(G')=P_2$ となり、cor-ch-unary-examples に反する。アルファベットが三文字以上なら、ex-ch-separating の二つ目の $\{a^{n}b^{n}c^{n}\mid n\ge1\}$ も使える。$\mathcal{L}_1\ne\mathcal{R}$：prop-ch-diagonal の $D$ は $\Sigma$ 上でも帰納的である（$0,1$ 以外の文字を含む入力は拒否すればよい）。$\Sigma$ 上の文脈依存文法 $G$ で $L(G)=D$ となるものがあったとすると、文脈依存文法の規則は変数記号だけを書き換えるので一度現れた終端記号は消えず、$D$ の元の導出には $0,1$ 以外の終端記号は現れない。そこで $0,1$ 以外の終端記号を左辺か右辺に含む規則を除けば、$\{0,1\}$ 上の文脈依存文法で $D$ を生成するものが得られ、prop-ch-diagonal に反する。$\mathcal{R}\ne\mathcal{L}_0$：$\{0,1\}$ 上に符号化した $A_{\mathrm{TM}}$ は Turing 機械で受理できる（MSm24 Theorem 5.4.4、p. 177）ので句構造言語であるが、帰納的でない（MSm24 Theorem 5.1.6、p. 162）。

1 から 2 は 文脈自由言語 の記事の命題「正規言語は文脈自由言語である」による。
2 から 3：$N:=N(L)$ とし、文脈自由言語 の記事の命題「文脈自由言語の反復補題」の反復定数を $p$ とする。$P:=p!$ とおく。まず「$n\ge p$ かつ $n\in N$ ならば、すべての $t\in\mathbb{N}$ について $n+tP\in N$」を示す。$a^{n}\in L$、$n\ge p$ なので、$a^{n}=uvxyz$、$1\le|vy|\le|vxy|\le p$、すべての $m$ について $uv^{m}xy^{m}z\in L$ となる分解がある。$k:=|vy|$ とおくと $uv^{m}xy^{m}z=a^{n+(m-1)k}$ である。$1\le k\le p$ なので $k$ は $P=p!$ を割り切り、$m:=1+tP/k$ とおけば $a^{n+tP}\in L$ を得る。
次に、$P$ を法とする各剰余類 $r\in\{0,1,\ldots,P-1\}$ について、$C_r:=\{n\in N\mid n\ge p,\ n\equiv r\pmod P\}$ を考える。$C_r\ne\emptyset$ ならその最小元を $m_r$ とおくと、前段により $C_r=\{m_r+tP\mid t\in\mathbb{N}\}$ である（$m_r$ より小さい同じ剰余類の元は最小性により $C_r$ に属さず、$m_r$ 以上の元は $m_r+tP$ の形なので前段により $N$ に属する）。$n_0$ を $p$ と、空でない $C_r$ の $m_r$ すべてのうちの最大値とする。$n\ge n_0$ とし、$n\equiv r$ とする。$C_r\ne\emptyset$ なら $n\ge m_r$ なので $n,n+P$ はともに $C_r\subset N$ に属し、$C_r=\emptyset$ なら $n,n+P$ はともに $N$ に属さない。よって $n\in N\iff n+P\in N$ である。
3 から 1：$n_0,P$ を 3 のとおりとする。$n\ge n_0$ について、$n$ と同じ剰余類に属する $[n_0,n_0+P)$ の元を $r(n)$ とおくと、$n=r(n)+tP$（$t\in\mathbb{N}$）であり、3 を $t$ 回使って $n\in N\iff r(n)\in N$ である。したがって
$$L=\{a^{n}\mid n< n_0,\ n\in N\}\ \cup\bigcup_{r\in N,\ n_0\le r< n_0+P}a^{r}\bigl(a^{P}\bigr)^{*}$$
である。右辺の第一項は有限言語、各 $\{a^{r}\}$ と $\{a^{P}\}$ も有限言語なので正規言語であり（正規言語 の記事の例「有限言語」）、正規言語のクラスは和・連接・Kleene 閉包について閉じている（正規言語 の記事の命題「和・連接・Kleene 閉包に関する閉包性」）ので、$L$ は正規言語である。

thm-ch-unary により、長さの集合が終局的に周期的でないことを示せばよい。$N=\{2^{k}\mid k\in\mathbb{N}\}$ が $n_0,P$ について 3 を満たすとすると、$2^{k}\ge n_0$ かつ $2^{k}> P$ となる $k$ をとれば、$2^{k}\in N$ から $2^{k}+P\in N$ が従うが、$2^{k}< 2^{k}+P< 2^{k+1}$ なので $2^{k}+P$ は $2$ の冪乗でなく、矛盾する。素数の集合 $N$ が $n_0,P$ について 3 を満たすとすると、$n_0$ 以上の素数 $q$ をとって 3 を $q$ 回使えば $q+qP=q(1+P)\in N$ となるが、$1+P\ge2$ なのでこれは素数でなく、矛盾する。