句構造言語
[math] \newcommand{\mathsetextension}[1]{% \left\{ #1 \right\}% } \newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}^{*}}} \newcommand{\mathgen}{\rightsquigarrow} \newcommand{\emptyword}{\varepsilon} \newcommand{\kleenecl}[1]{{#1}^{*}} \newcommand{\interpret}[1]{[\![#1]\!]} \newcommand{\mathautomaton}[1]{\mathcal{#1}} \newcommand{\mathnat}{\mathbb{N}} \newcommand{\qed}{\blacksquare} [/math]
句構造言語（phrase structure language）とは句構造文法によって生成される形式言語である。
以下、項目形式言語において定められている言語上の演算などについては特に断らず用いる。
句構造言語の導入
この節では句構造言語を定義する。
定義 1 (句構造文法)
句構造文法（phrase structure grammar）とは
- 記号集合 $\Sigma$
- $\Sigma$ と互いに素な変数記号（variable）の有限集合 $V$
- 生成規則（production rule）と呼ばれる有限集合 $R \subseteq (\kleenecl{(\Sigma \cup V)}\setminus\{\emptyword\}) \times \kleenecl{(\Sigma \cup V)}$
- 開始記号(start symbol)または初期記号と呼ばれる $S\in V$
の４つ組 $(V, \Sigma, R, S)$ である。
句構造言語論の文脈においては、$\Sigma$ の元を終端記号(terminal)、$V$ の元を非終端記号(non-terminal)と呼ぶことも多い。
以下では、元 $(\alpha, \beta)\in R$ のことを$\alpha\mathgen\beta$ と書く。
定義 2 (導出)
$G=(V, \Sigma, R, S)$ を句構造文法とする。
直接導出（direct derivation）とは \[\hat{G}:=\left\{(\gamma \alpha\delta, \gamma\beta\delta)\left| \gamma, \delta \in (\Sigma \cup V)^{*}, \alpha\mathgen\beta \in R \right.\right\}\] である。
直接導出の元 $(\gamma\alpha\delta, \gamma\beta\delta)$を $\gamma\alpha\delta \Rightarrow_{G} \gamma\beta\delta$ と書く。$G$ が文脈上明らかなときは単に $\gamma\alpha\delta \Rightarrow \gamma\beta\delta$ と書く。
直接導出の反射推移閉包のことを導出（derivation）と呼ぶ。導出の元 $(\eta, \theta)$ を $\eta \mathderiv_{G} \theta$ と書く。 $G$ が文脈上明らかなときは単に $\eta \mathderiv \theta$ と書く。
定義 3 (句構造文法により生成される言語)
$G=(V, \Sigma, R, S)$ を句構造文法とする。 $G$ によって生成される言語 $L(G)$は \[L(G):=\left\{w\in \Sigma^{*} \left| S \mathderiv w \right.\right\}\] と定義される。
句構造言語とは何らかの句構造文法によって生成される言語のことを言う。
定義 4 (句構造文法の等価性)
句構造文法 $G_{1}$, $G_{2}$ について、$L(G_1)=L(G_2)$ のとき、$G_{1}$ と $G_{2}$ は等価であるという。
Chomsky 階層
この節では Chomsky 階層という句構造言語全体の部分集合のなす階層構造について述べる。
句構造文法のことをタイプ0の文法、 文脈依存文法のことをタイプ1の文法、 文脈自由文法のことをタイプ2の文法、 右線形文法および 左線形文法のことを タイプ3の文法と言うことがある。
このとき、タイプ $i$ の文法とタイプ $j$ の文法 (ただし$i\lt j$)について、 タイプ $j$ の文法はタイプ $i$ の文法の 特殊なものになっている。 すなわち、タイプ $j$ の文法によって生成される言語全体はタイプ $i$ の文法によって生成される言語全体に含まれている。 実はこの包含関係は真の包含関係であることが知られている。
すなわち次が成り立つ。 \[\text{句構造言語全体} \supsetneq \text{文脈依存言語全体} \supsetneq \text{文脈自由言語全体} \supsetneq \text{正規言語全体}\] この句構造言語全体の部分集合のなす階層構造をChomsky階層(Chomsky hierarchy)と呼ぶ。
これらの形式言語についてはそれらと対応する計算モデル（オートマトン）がそれぞれ存在することが知られている。
| 文法のタイプ | 言語のクラス | 計算モデル |
|---|---|---|
| タイプ0 | 句構造言語 | Turingマシン |
| タイプ1 | 文脈依存言語 | 線形有界オートマトン |
| タイプ2 | 文脈自由言語 | プッシュダウン・オートマトン |
| タイプ3 | 正規言語 | 有限オートマトン |
参考文献
- 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3、https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
- 五十嵐喜英他、『数理情報科学シリーズ ２４ オートマトンと形式言語の基礎』、牧野書店、2011
関連項目
| 文法のタイプ | 言語のクラス | 計算モデル |
|---|---|---|
| タイプ0 | 句構造言語 | Turingマシン |
| タイプ1 | 文脈依存言語 | 線形有界オートマトン |
| タイプ2 | 文脈自由言語 | プッシュダウン・オートマトン |
| タイプ3 | 正規言語 | 有限オートマトン |
