句構造言語
概要
句構造言語（phrase structure language）とは、生成規則の左辺に空でない任意の記号列、右辺に任意の記号列（空語を含む）を許した最も一般的な文法である句構造文法（無制限文法、タイプ 0 の文法）によって生成される形式言語のことである。開始記号から規則を繰り返し適用して終端記号だけの文字列に至る導出によって言語が定まり、正規言語・文脈自由言語・文脈依存言語をすべて特別な場合として含む。句構造言語のクラスは Turing 機械が受理する言語（帰納的可算言語）のクラスと一致し、Chomsky 階層の最上位に位置する。文法は有限の記号列で書けるので句構造言語は可算個しかなく、句構造言語でない言語が存在し、また補集合について閉じていない。
前提知識: 形式言語, 二項関係, 数学的帰納法, 可算集合
定義
句構造言語は、生成規則の左辺にも右辺にも記号の任意の列を許した最も一般的な文法で生成される形式言語である。以下、$\Sigma$ はアルファベット、$\Sigma^{*}$ はその上の文字列全体、$\varepsilon$ は空語を表す。
句構造文法（phrase structure grammar。無制限文法（unrestricted grammar）、タイプ 0 の文法ともいう）とは、$4$ つ組 $G=(V,\Sigma,R,S)$ であって次を満たすものをいう。
句構造文法 $G=(V,\Sigma,R,S)$ に対し、$(V\cup\Sigma)^{*}$ 上の二項関係 $\Rightarrow_G$（直接導出）を
$$\gamma\alpha\delta\Rightarrow_G\gamma\beta\delta\qquad(\gamma,\delta\in(V\cup\Sigma)^{*},\ \alpha\to\beta\in R)$$
で定める。すなわち、文字列の中に規則の左辺 $\alpha$ が部分文字列として現れているとき、その一つの出現を右辺 $\beta$ で置き換える操作である。$\Rightarrow_G$ の反射推移閉包を $\Rightarrow_G^{*}$ と書き、$\eta\Rightarrow_G^{*}\theta$ のとき $\theta$ は $\eta$ から導出されるという。すなわち $\eta\Rightarrow_G^{*}\theta$ とは、$n\in\mathbb{N}$ と文字列の列 $\eta=\eta_0\Rightarrow_G\eta_1\Rightarrow_G\cdots\Rightarrow_G\eta_n=\theta$ が存在することである。文法が文脈から明らかなときは $\Rightarrow$、$\Rightarrow^{*}$ と書く。
$G$ が生成する言語は
$$L(G):=\{\,w\in\Sigma^{*}\mid S\Rightarrow_G^{*}w\,\}$$
である。二つの句構造文法 $G_1,G_2$ が $L(G_1)=L(G_2)$ を満たすとき、両者は等価（equivalent）であるという。
$\Sigma$ 上の言語 $L\subset\Sigma^{*}$ が句構造言語（phrase structure language。タイプ 0 の言語ともいう）であるとは、ある句構造文法 $G$ が存在して $L=L(G)$ となることをいう。
生成規則の左辺に「少なくとも一つの変数記号を含む」ことを要求する流儀もある（HU79 §9.2、Sip12 の演習（番号は未確認））。左辺が終端記号だけからなる規則 $x\to\beta$ を持つ文法は、各終端記号 $a$ を新しい変数記号 $X_a$ に置き換えて規則 $X_a\to a$ を加えることで、その流儀の文法に直せる（prop-phrase-structure-language-separated-form）ので、生成される言語のクラスは同じである。句構造言語のクラスは、Turing機械が受理する言語（帰納的可算言語）のクラスと一致する（thm-phrase-structure-language-turing）。
直感
句構造文法は「開始記号から出発し、規則を好きな順序・好きな箇所に繰り返し適用して文字列を書き換え、終端記号だけになったら一つの語が完成する」という最も自由な書き換え系である。文脈自由文法の規則は一つの変数記号だけを書き換えるが、句構造文法では左辺が複数の記号からなる列でもよいので、「隣に何があるか」に応じて書き換えを制御できる。この文脈依存性により、文脈自由言語では扱えない $\{a^{n}b^{n}c^{n}\}$ のような言語や、任意の計算機の動作を模倣する言語が生成できる。
規則の適用は「マーカーとなる変数記号を文字列の中で往復させ、通過するたびに記号を書き換える」という形で使われることが多く（ex-phrase-structure-language-powers-of-two）、これはTuring機械のヘッドがテープ上を往復する動作にほかならない。句構造文法と Turing 機械が同じ言語のクラスを定めるのは、この対応の帰結である。
例
$\Sigma=\{a\}$、$V=\{S\}$、$R=\{S\to a\}$ とすると、$S$ から導出できる文字列は $S$ 自身と $a$ だけであり、$L(G)=\{a\}$ である。規則が一本だけの最も単純な句構造文法の例である。同様に、任意の有限言語 $\{w_1,\ldots,w_m\}$ は規則 $S\to w_1,\ldots,S\to w_m$ で生成される。
$\Sigma=\{a,b\}$、$V=\{S\}$、$R=\{S\to aSb,\ S\to ab\}$ とすると、$S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow\cdots\Rightarrow a^{n-1}Sb^{n-1}\Rightarrow a^{n}b^{n}$ により $L(G)=\{\,a^{n}b^{n}\mid n\ge1\,\}$ である。この文法の規則は左辺が一つの変数記号なので文脈自由文法でもあり、句構造文法が文脈自由文法を特別な場合として含むことが見てとれる（証明は Backus–Naur記法 の記事の命題と同様）。
$\Sigma=\{a,b,c\}$、$V=\{S,B,C\}$ とし、規則を
$$S\to aSBC,\quad S\to aBC,\quad CB\to BC,\quad aB\to ab,\quad bB\to bb,\quad bC\to bc,\quad cC\to cc$$
とすると $L(G)=\{\,a^{n}b^{n}c^{n}\mid n\ge1\,\}$ である。最初の二つの規則で $a^{n}(BC)^{n}$ を作り、$CB\to BC$ で $B$ をすべて $C$ の左に集めて $a^{n}B^{n}C^{n}$ とし、残りの規則で $B$、$C$ を左から順に小文字にする。たとえば
$$S\Rightarrow aSBC\Rightarrow aaBCBC\Rightarrow aaBBCC\Rightarrow aabBCC\Rightarrow aabbCC\Rightarrow aabbcC\Rightarrow aabbcc$$
である。規則 $CB\to BC$ や $bB\to bb$ は左辺が $2$ 記号であり、文脈自由文法の規則ではない。この文法が $a^{n}b^{n}c^{n}$ 以外の終端文字列を生成しないことの証明は 文脈依存言語 の記事の命題にある（左辺の長さが右辺の長さを超えない文法なので文脈依存言語の例でもある）。この言語は文脈自由言語ではない（文脈自由言語 の記事の命題）。
$\Sigma=\{a\}$、$V=\{S,A,B,C,D,E\}$ とし、規則を
$$S\to ACaB,\quad Ca\to aaC,\quad CB\to DB,\quad CB\to E,\quad aD\to Da,\quad AD\to AC,\quad aE\to Ea,\quad AE\to\varepsilon$$
とすると $L(G)=\{\,a^{2^{n}}\mid n\ge1\,\}$ である（HU79 §9.2 の例）。$A$ と $B$ は文字列の左端と右端の目印であり、$C$ は左から右へ動きながら通過した $a$ を $aa$ に置き換える（$a$ の個数を $2$ 倍にする）。右端に着いた $C$ は、$D$ に変わって左端まで戻り $A$ の隣で再び $C$ になるか（もう一度 $2$ 倍する）、$E$ に変わって左端まで戻り $A$ とともに消える（終了する）。$C$ が右端に着くたびに $a$ の個数は $2$ 倍になるので、生成される文字列は $a^{2^{n}}$ である。たとえば
$$S\Rightarrow ACaB\Rightarrow AaaCB\Rightarrow AaaE\Rightarrow AaEa\Rightarrow AEaa\Rightarrow aa$$
は $a^{2}$ の導出である。この文法は規則 $AE\to\varepsilon$ で文字列を短くするので、文脈依存文法（文脈依存言語）の規則の形をしていない。この言語は文脈自由言語ではなく（長さ $2^{n}$ の文字列を反復補題で反復すると長さが $2^{n}$ と $2^{n+1}$ の間に落ちる。文脈自由言語 の記事の反復補題による）、したがって正規言語でもない。
$\Sigma=\{a\}$、$V=\{S\}$、$R=\{S\to\varepsilon\}$ は句構造文法であり、$L(G)=\{\varepsilon\}$ である（右辺の空語は許される）。一方 $R'=\{S\to\varepsilon,\ \varepsilon\to a\}$ は左辺が空語の規則を含むので、句構造文法の定義を満たさない。左辺が空語の規則を許す書き換え系を考えることはできるが（$\varepsilon\to a$ は任意の位置への $a$ の挿入を意味し、この例では生成言語が $\{a\}^{*}$ になる）、それは別の規約による対象であり、Chomsky 階層の議論の枠外である。すなわち $R'$ は「有限個の書き換え規則の集合である」という性質は満たすが、「左辺が空でない」という定義の条件を満たさない。
句構造言語は可算個しかない（prop-phrase-structure-language-countable）ので、どの句構造文法でも生成できない言語が存在する。具体的な例は計算可能性理論によって与えられる。たとえば Turing 機械の符号 $\langle M\rangle$ で「$M$ が入力 $\langle M\rangle$ に対して受理しない」ものの全体は帰納的可算でなく、thm-phrase-structure-language-turing により句構造言語でない（Sip12 Theorem 4.11 と Corollary 4.23、HU79 §8.3）。この言語は「補集合が句構造言語である」という性質を満たすが、「句構造言語である」という性質を満たさない。したがって句構造言語のクラスは補集合について閉じていない。
性質
句構造文法 $G$ について、$\eta\Rightarrow_G^{*}\theta$ ならば、任意の $\gamma,\delta\in(V\cup\Sigma)^{*}$ について $\gamma\eta\delta\Rightarrow_G^{*}\gamma\theta\delta$ が成り立つ。また $\eta_1\Rightarrow_G^{*}\theta_1$ かつ $\eta_2\Rightarrow_G^{*}\theta_2$ ならば $\eta_1\eta_2\Rightarrow_G^{*}\theta_1\theta_2$ が成り立つ。
$\eta\Rightarrow_G^{*}\theta$ は、文字列の列 $\eta=\eta_0\Rightarrow_G\eta_1\Rightarrow_G\cdots\Rightarrow_G\eta_n=\theta$ の存在を意味する。各一歩 $\eta_{i-1}\Rightarrow_G\eta_i$ は、ある $\gamma',\delta'$ と規則 $\alpha\to\beta$ について $\eta_{i-1}=\gamma'\alpha\delta'$、$\eta_i=\gamma'\beta\delta'$ となることである。このとき $\gamma\eta_{i-1}\delta=(\gamma\gamma')\alpha(\delta'\delta)$、$\gamma\eta_i\delta=(\gamma\gamma')\beta(\delta'\delta)$ であるから、同じ規則を文脈 $(\gamma\gamma',\delta'\delta)$ で適用して $\gamma\eta_{i-1}\delta\Rightarrow_G\gamma\eta_i\delta$ を得る。これを $i=1,\ldots,n$ についてつなげば $\gamma\eta\delta\Rightarrow_G^{*}\gamma\theta\delta$ である。後半は、前半により $\eta_1\eta_2\Rightarrow_G^{*}\theta_1\eta_2\Rightarrow_G^{*}\theta_1\theta_2$ となることから従う。
句構造文法全体の上で、「$G_1$ と $G_2$ は等価である」という関係は同値関係である。
等価性は $L(G_1)=L(G_2)$ という集合の等号で定義されているので、等号の反射律・対称律・推移律からそのまま従う。
任意の句構造文法 $G=(V,\Sigma,R,S)$ に対し、終端記号が右辺に現れる規則が $X_a\to a$（$a\in\Sigma$、$X_a$ は変数記号）の形のものだけであり、それ以外の規則の左辺・右辺が変数記号だけからなるような句構造文法 $G'$ で $L(G')=L(G)$ となるものが存在する。特に、すべての規則の左辺に変数記号が含まれるようにできる。
各 $a\in\Sigma$ に対し新しい変数記号 $X_a$ をとり、文字列 $\alpha\in(V\cup\Sigma)^{*}$ の各終端記号 $a$ を $X_a$ に置き換えた文字列を $\hat\alpha\in(V\cup\{X_a\}_{a\in\Sigma})^{*}$ と書く。$V':=V\cup\{X_a\mid a\in\Sigma\}$、
$$R':=\{\,\hat\alpha\to\hat\beta\mid\alpha\to\beta\in R\,\}\cup\{\,X_a\to a\mid a\in\Sigma\,\},\qquad G':=(V',\Sigma,R',S)$$
とおく。$\hat\alpha$ は $\alpha\ne\varepsilon$ なら空でないので $R'$ は句構造文法の規則の集合であり、$R'$ の規則は主張の形をしている。
$L(G)\subset L(G')$：$S\Rightarrow_G^{*}w$ の各一歩 $\gamma\alpha\delta\Rightarrow_G\gamma\beta\delta$ に対し、$\hat\gamma\hat\alpha\hat\delta\Rightarrow_{G'}\hat\gamma\hat\beta\hat\delta$ が規則 $\hat\alpha\to\hat\beta$ による一歩である。よって $S=\hat S\Rightarrow_{G'}^{*}\hat w$ であり、$\hat w$ の各 $X_a$ を規則 $X_a\to a$ で置き換えれば $\hat w\Rightarrow_{G'}^{*}w$ となる。
$L(G')\subset L(G)$：変数記号だけからなる文字列 $\hat\theta$ から終端記号を含む文字列への $G'$ の導出を考える。規則 $X_a\to a$ で生じた終端記号 $a$ は、$R'$ の他の規則の左辺（変数記号だけからなる）に含まれないので、以後の導出で書き換えられることはない。したがって $S\Rightarrow_{G'}^{*}w$（$w\in\Sigma^{*}$）の導出において、規則 $X_a\to a$ の適用をすべて最後に回しても（他の規則の適用は終端記号に触れないので順序を入れ替えられる）同じ $w$ に至り、$S\Rightarrow_{G'}^{*}\hat w\Rightarrow_{G'}^{*}w$ の形になる。ここで前半は規則 $\hat\alpha\to\hat\beta$ だけを用いた導出であり、各一歩の $X_a$ を $a$ に戻せば $G$ の導出 $S\Rightarrow_G^{*}w$ が得られる。
固定したアルファベット $\Sigma$ 上の句構造言語は可算無限個である。したがって句構造言語でない言語が存在する。
句構造文法 $G=(V,\Sigma,R,S)$ は、変数記号の名前を $A_1,A_2,\ldots,A_k$ と付け替えれば、有限個の記号（$\Sigma$ の元、記号 $A$、添字を表す数字、矢印、区切り記号）からなる一つの有限の文字列として書き表せる。名前の付け替えは生成言語を変えないので、句構造言語全体は、この有限のアルファベット上の文字列全体の部分集合から全射で写されることになり、形式言語 の記事の命題（言語の個数）により可算である。有限言語はすべて句構造言語であり（ex-phrase-structure-language-single）無限個あるので、句構造言語は可算無限個である。一方、$\Sigma$ 上の言語全体は非可算個である（同じ命題）から、句構造言語でない言語が存在する。
$\Sigma$ 上の言語 $L$ が句構造言語であることと、$L$ を受理するTuring機械が存在すること（$L$ が帰納的可算言語であること）は同値である。
証明は HU79 §9.2（Theorems 9.3、9.4）、Sip12 の演習（番号は未確認）を参照。文法から Turing 機械へは、入力文字列に対して $S$ からの導出を非決定的に推測して照合する機械を作る。Turing 機械から文法へは、機械の様相（テープの内容・ヘッドの位置・状態）を文字列で表し、機械の一歩を規則で模倣し、受理した後に計算の痕跡を消して入力だけを残す。ここで「受理する」とは、言語に属する入力に対しては受理して停止し、属さない入力に対しては停止しないことも許すという意味である。すべての入力で停止する Turing 機械（判定手続き）で受理される言語を帰納的言語といい、帰納的でない帰納的可算言語が存在する（停止問題。Sip12 Theorem 4.11）。したがって $w\in L(G)$ かどうかを判定する一般的な手続きは存在しない。これは文脈依存言語（文脈依存言語 の記事の命題により所属問題が判定できる）との違いである。
補足
階層における位置
句構造言語は Chomsky階層（表は 形式言語 の記事の補足）の最上位（タイプ 0）であり、文脈依存言語を真に含む（prop-phrase-structure-language-includes-csl と、文脈依存言語 の記事の反例にある文脈依存でない帰納的言語の存在）。句構造言語のクラスは和・連接・Kleene 閉包・共通部分・鏡像について閉じているが、補集合については閉じていない（rem-phrase-structure-language-nonexample-uncountable。HU79 §9.4）。
歴史
句構造文法は N. Chomsky（Cho59）が階層の最上位として導入し、Turing 機械との同値もそこで示唆された。「句構造」（phrase structure）という名称は、自然言語の文を句の入れ子として分析する統語論に由来する。標準的な教科書として HU79 第 9 章、Sip12 第 3–4 章、Igr11 第 5 章を挙げる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
