文脈自由言語
[math] \newcommand{\mathsetextension}[1]{% \left\{ #1 \right\}% } \newcommand{\mathsetintension}[2]{% \left\{ #1 \left| #2 \right.\right\}% } \newcommand{\mathof}[2]{% \mathop{#1}\left(#2\right)% } \newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}^{*}}} \newcommand{\mathgen}{\rightsquigarrow} \newcommand{\mathgenfun}[1]{\mathbf{#1}} \newcommand{\mirrorim}[1]{\overleftarrow{#1}} \newcommand{\emptyword}{\varepsilon} \newcommand{\kleenecl}[1]{{#1}^{*}} \newcommand{\interpret}[1]{[\![#1]\!]} \newcommand{\mathautomaton}[1]{\mathcal{#1}} \newcommand{\mathnat}{\mathbb{N}} \newcommand{\qed}{\blacksquare} \newcommand{\mathrelbar}{\mathrel{|}} [/math]
文脈自由言語（context-free language）とは文脈自由文法によって生成される形式言語である。
文脈自由文法は句構造文法の一種であるから、 文脈自由言語は句構造言語の一種である。 また、文脈自由文法は文脈依存文法の一種であるから、 文脈自由言語は文脈依存言語の一種である。
以下、項目形式言語において定められている言語上の演算などについては特に断らず用いる。
文脈自由言語の導入
この節では文脈自由言語を定義する。
定義 1 (文脈自由文法)
文脈自由文法（context-free grammar）とは
- 記号集合 $\Sigma$
- $\Sigma$ と互いに素な変数記号（variable）の有限集合 $V$
- 生成規則（production rule）と呼ばれる有限集合 $R \subseteq V \times \kleenecl{(\Sigma \cup V)}$
- 開始記号(start symbol)または初期記号と呼ばれる $S\in V$
の４つ組$(V, \Sigma, R, S)$である。
これは、 句構造文法の一種である。また、 文脈依存文法の一種である。
句構造言語のときと同様、$\Sigma$ の元を終端記号(terminal)、$V$ の元を非終端記号(non-terminal)と呼ぶことも多い。
以下では、元$(A, \alpha)\in R$ のことを$A\mathgen\alpha$と書く。
導出、 生成される言語などは 句構造言語と同様に定義される。
文脈自由言語とは何らかの文脈自由文法によって生成される言語のことを言う。
文脈自由言語の例
この節では文脈自由言語の例を紹介する。
例 2 (Dyck言語)
$V=\left\{ S \right\}$, $\Sigma=\left\{ [, ] \right\}$, $R=\left\{ S\mathgen\varepsilon, S\mathgen [S]S \right\}$ とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。 この文脈自由文法によって生成される言語 $L(G)$ をDyck言語と呼ぶ
Dyck言語の元となる記号列とその記号列を生成する導出の列をいくつかあげる。
\begin{gather*} S \Rightarrow \varepsilon \\ S \Rightarrow [S]S \Rightarrow [\varepsilon]S \Rightarrow [\varepsilon]\varepsilon \equiv [] \\ S \Rightarrow [S]S \Rightarrow [[]]S \Rightarrow [[]]\varepsilon \equiv [[]] \\ S \Rightarrow [S]S \Rightarrow [\varepsilon]S \Rightarrow [\varepsilon][S]S \mathderiv [\varepsilon][\varepsilon]\varepsilon \equiv [][] \\ S \Rightarrow [S]S \Rightarrow [[S]S]S \Rightarrow [[[S]S]S]S \mathderiv [[[\varepsilon]\varepsilon]\varepsilon]\varepsilon \equiv [[[]]] \\ S \Rightarrow [S]S \Rightarrow [[S]S]S \Rightarrow [[S]S][S]S \mathderiv [[\varepsilon]\varepsilon][\varepsilon]\varepsilon \equiv [[]][] \\ S \Rightarrow [S]S \Rightarrow [S][S]S \Rightarrow [S][[S]S]S \mathderiv [\varepsilon][[\varepsilon]\varepsilon]\varepsilon \equiv [][[]] \\ S \Rightarrow [S]S \Rightarrow [S][S]S \Rightarrow [S][S][S]S \mathderiv [\varepsilon][\varepsilon][\varepsilon]\varepsilon \equiv [][][] \end{gather*}
例 3 (二進表現された自然数同士の四則演算の式全体)
\begin{align*} V&=\left\{ S, B, B', M, P \right\}, \\ \Sigma&=\left\{ 0, 1, +, -, \times, \div, (, ) \right\}, \\ R&=\{ S \mathgen M, S \mathgen S + M, S \mathgen S - M, M \mathgen P, M \mathgen M \times P, M \mathgen M \div P, P \mathgen B, P \mathgen ( S ), B \mathgen 0, B \mathgen 1, B \mathgen 1B', B' \mathgen 0, B' \mathgen 1, B' \mathgen 0B', B' \mathgen 1B' \} \end{align*}
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。 この文法によって生成される言語は二進表現された自然数同士の四則演算の式全体である。
二進表現された自然数同士の四則演算の式の導出の例をあげる。
\begin{align*} S &\Rightarrow M \\ &\Rightarrow M \div P \\ &\Rightarrow M \times P \div P \\ &\Rightarrow P \times P \div P \\ &\Rightarrow (S) \times P \div P \\ &\Rightarrow (S - M) \times P \div P \\ &\Rightarrow (S + M - M) \times P \div P \\ &\Rightarrow (M + M - M) \times P \div P \\ &\Rightarrow (P + M - M) \times P \div P \\ &\Rightarrow (B + M - M) \times P \div P \\ &\Rightarrow (0 + M - M) \times P \div P \\ &\Rightarrow (0 + P - M) \times P \div P \\ &\Rightarrow (0 + B - M) \times P \div P \\ &\Rightarrow (0 + 1B' - M) \times P \div P \\ &\Rightarrow (0 + 10 - M) \times P \div P \\ &\Rightarrow (0 + 10 - P) \times P \div P \\ &\Rightarrow (0 + 10 - B) \times P \div P \\ &\Rightarrow (0 + 10 - 1) \times P \div P \\ &\Rightarrow (0 + 10 - 1) \times B \div P \\ &\Rightarrow (0 + 10 - 1) \times 1B' \div P \\ &\Rightarrow (0 + 10 - 1) \times 10B' \div P \\ &\Rightarrow (0 + 10 - 1) \times 101 \div P \\ &\Rightarrow (0 + 10 - 1) \times 101 \div B \\ &\Rightarrow (0 + 10 - 1) \times 101 \div 1 \\ \end{align*}
例 4 ((命題変数が有限の)命題論理の論理式全体)
\begin{align*} V&=\left\{ S \right\}, \\ \Sigma&=\left\{ p_1, \ldots p_n, \top, \bot, \lnot, \land, \lor, \to, (, )\right\}, \\ R&=\{ S\mathgen p_1, \ldots, S\mathgen p_n, S\mathgen \top, S\mathgen \bot, S\mathgen(\lnot S), S\mathgen(S\land S), S\mathgen(S\lor S), S\mathgen({S\to S}) \} \end{align*}
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ は数理論理学の基礎・命題論理において定義されている命題論理の論理式全体である（ただし、命題変数の集合の濃度を有限としたときに限る）。
例 5 ($0^{n}1^{n}$ という形をした記号列全体)
$V=\left\{ S \right\}$, $\Sigma=\left\{ 0, 1 \right\}$, $R=\left\{ S\mathgen\emptyword, S\mathgen 0S1 \right\}$ とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。 この文脈自由文法によって生成される言語 $L(G)$ は $0^{n}1^{n}$ （ただし、$n\in\mathnat$）という形をした記号列全体になっている。
$0^{n}1^{n}$ という形をした記号列の導出の例をいくつかあげる。
\begin{gather*} S \Rightarrow \varepsilon \\ S \Rightarrow 0S1 \Rightarrow 0\emptyword 1 \equiv 01 \\ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 00\emptyword 11 \equiv 0011 \\ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 000\emptyword 111 \equiv 000111 \\ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 0000S1111 \Rightarrow 0000\emptyword 1111 \equiv 00001111 \\ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 0000S1111 \Rightarrow 00000S11111 \Rightarrow 00000\emptyword 11111 \equiv 0000011111 \end{gather*}
例 6 ($w\mirrorim{w}$ という形をした記号列全体)
$V=\left\{ S \right\}$, $\Sigma=\left\{ 0, 1 \right\}$, $R=\left\{ S\mathgen\emptyword, S\mathgen 0S0, S\mathgen 1S1 \right\}$ とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。 この文脈自由文法によって生成される言語 $L(G)$ は $w\mirrorim{w}$ （ただし、$w\in \kleenecl{\Sigma}$）という形をした記号列全体になっている。
$w\mirrorim{w}$ という形をした記号列の導出の例をいくつかあげる。
\begin{gather*} S \Rightarrow \varepsilon \\ S \Rightarrow 0S0 \Rightarrow 0\emptyword 0 \equiv 00 \\ S \Rightarrow 1S1 \Rightarrow 1\emptyword 1 \equiv 11 \\ S \Rightarrow 0S0 \Rightarrow 00S00 \Rightarrow 00\emptyword 00 \equiv 0000 \\ S \Rightarrow 0S0 \Rightarrow 01S10 \Rightarrow 01\emptyword 10 \equiv 0110 \\ S \Rightarrow 1S1 \Rightarrow 10S01 \Rightarrow 10\emptyword 01 \equiv 1001 \\ S \Rightarrow 1S1 \Rightarrow 11S11 \Rightarrow 11\emptyword 11 \equiv 1111 \end{gather*}
Backus-Naur記法
この節ではBackus-Naur記法(Backus-Naur form)について述べる。
Backus-Naur記法の導入
\begin{align*} V&=\left\{ S, A_{1}, \dots A_{n} \right\}, \\ R&=\{ S\mathgen \alpha_{00}, \dots S\mathgen \alpha_{0m_{0}}, \\ &\phantom{=\{} A_{1}\mathgen \alpha_{10}, \dots A_{1}\mathgen \alpha_{1m_{1}}, \\ &\phantom{=\{ A_{1}\mathgen \alpha_{10}, } \vdots \\ &\phantom{=\{} A_{n}\mathgen \alpha_{n0}, \dots A_{n}\mathgen \alpha_{nm_{n}} \} \end{align*}
という、文脈自由文法 $G=(V, \Sigma, R, S)$ について、
\begin{align*} S &::= \alpha_{00} \mathrelbar \dots \mathrelbar \alpha_{0m_{0}} \\ A_{1} &::= \alpha_{10} \mathrelbar \dots \mathrelbar \alpha_{1m_{1}} \\ &\phantom{::= \alpha_{10} \mathrelbar \ldots}\vdots \\ A_{n} &::= \alpha_{n0} \mathrelbar \dots \mathrelbar \alpha_{nm_{n}} \end{align*}
という表記を $G$ のBackus-Naur記法(Backus-Naur form)という。
この記法は、論理式の定義やプログラミング言語の定義などによく使われる。
BNFの例
例 7 (二進表現された自然数同士の四則演算の式全体)
二進表現された自然数同士の四則演算の式全体を表すBNF記法は次のとおりである。
\begin{align*} S &::= M \mathrelbar S + M \mathrelbar S - M \\ M &::= P \mathrelbar M \times P \mathrelbar M \div P \\ P &::= B \mathrelbar ( S ) \\ B &::= 0 \mathrelbar 1 \mathrelbar 1B' \\ B' &::= 0 \mathrelbar 1 \mathrelbar 0B'\mathrelbar 1B' \end{align*}
参考文献
- 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、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 | 正規言語 | 有限オートマトン |
