形式言語

2022年8月27日

概要

あるオートマトンによって受理することのできる言語である。

自然言語は多くのあいまいな表現を含むことを許していて、どの品詞における語でも複数の意味や解釈を持ったまま使われている。原則として表現が目指すところは発信者の意図を受け取り手と共有することである。しかし現実的な人間の社会生活では 100% の正確さで伝わる必要性は薄く、重要でない部分は相手に解釈をゆだねたり、すでに特定の文脈を共有しているという前提を持つことで、ある程度の厳密さ以上では簡便性が優先されている。

概要
導入
1. 生成規則
2. 言語
正規言語
文脈自由文法
LL 構文
参考文献

導入

形式言語を表現する最小単位を記号 (symbol) または文字 (letter) と呼び、すべての記号からなる有限集合をアルファベット $\Sigma$ で表す。記号の一連の列は単語 (word) または文字列 (string) と呼ぶ (ただしどちらも "文字" を強く想起させる言葉であるため、紛らわしさを避けるためこの記事では記号列と表記する)。

生成規則

ある記号列 $S$ に含まれている記号列 $w$ を $\alpha$ に書き換える規則を生成規則 (derivation rule) または書き換え規則 (rewriting rule) と呼び $p:w\to\alpha$ と表す。また $w$ を含む記号列 $S=w_0\,w\,w_1$ を $p$ が適用可能であるという。記号列 $S$ に生成規則 $p$ を適用した結果の $S'=w_0\,\alpha\,w_1$ は  $p$ により $S$ から $\alpha$ を導出 (derivation) したという見方ができる。

$p:w\to\alpha$ による導出を生成規則の適用 $\Rightarrow^p$ を使って $S \Rightarrow^p S'$ や式 ( $\ref{derivation}$ ) のように表す。 $\begin{equation} w_0\,w\,w_1 \Rightarrow^p w_0\,\alpha\,w_1 \label{derivation} \end{equation}$

$w_0$ , $w_1$ も記号列であることから、 $S$ が $w$ を複数含んでいたとしても $p$ を繰り返し適用することですべての $w$ を導出することができる。これは生成規則の適用の繰り返しを $\Rightarrow^*$ として $S \Rightarrow^* S'$ や式 ( $\ref{derivation_repeat}$ ) のように表す。 $\begin{equation} w_0\,w\,w_1\ldots\,w_{n-1}\,w\,w_n \Rightarrow^* w_0\,\alpha\,w_1\ldots\,w_{n-1}\,\alpha\,w_n \label{derivation_repeat} \end{equation}$

$\alpha$ は $\alpha=w$ であるような記号列であっても良い点に注意。これは $w$ という意味のない記号の列を $\alpha$ という意味にマークアップ (タグ付け) するという操作に相当する。

形式言語はオートマトンと逆の操作でも生成することができる。内部状態 $i$ を持つオートマトンが記号 $\alpha$ の入力によって状態 $j$ に遷移するとき、記号列 $S_i$ から $\alpha$ を導出して $S_j$ が残るという見方をすると式 ( $\ref{gen_rule}$ ) のような生成規則 $p_j$ を考えることができる。 $\begin{equation} S_i \Rightarrow^{p_j} \alpha\,S_j \label{gen_rule} \end{equation}$ これは式 ( $\ref{derivation}$ ) で $w_0=\epsilon$ とした生成規則と同じ形である。

例1. 言語 $L = \{a^2b\}$ を受理するオートマトンの一連の状態遷移は $S_0$ $\Rightarrow$ $a S_1$ $\Rightarrow$ $aaS_2$ $\Rightarrow$ $aab$ または $S_0$ $\Rightarrow^*$ $aab$ の一連の導出と考えることができる。

生成規則において、それ以上に他の記号を導出できない記号 (つまりアルファベット $\Sigma$ に含まれる 1 つの記号) を終端記号 (terminal symbol) と呼び、他の記号を導出できると定義されている記号を非終端記号 (non-terminal symbol) と呼ぶ。例1では $S_0,$ $S_1,$ $S_2$ が非終端記号、 $a,$ $b$ が終端記号に相当する。

例えば以下の EBNF 構文では記号 $\Sigma=\{{\tt 0x}, 0, 1, \ldots, 9, A, B, \ldots, F\}$ が終端文字で DIGIT, HEX, HEXINT は非終端文字に相当する。

DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
HEX = "A" | "B" | "C" | "D" | "E" | "F";
HEXINT = "0x" {DIGIT | HEX};

この構文に 0x2C を入力すると Fig 1 のような一連の導出が行われ、結果的に HEXINT はこの文字列を受理できるため HEXINT 上の語とみなせる。

終端記号の集合 $\Sigma$ と非終端記号の集合 $N$ それぞれのすべての要素で構成される有限集合を $V = N \cup \Sigma$ とし、 $V$ に含まれる任意の要素を使って生成可能なすべての記号列の無限集合を $V^*$ とする¹。また $V^*$ から空語を除いた無限集合を $V^+=V^*\,\backslash\,\{\epsilon\}$ とする。

記号列 $x$ を記号列 $y$ に変換する生成規則を $p:(x,y)$ と表すと、 $p$ は $x$ と $y$ の直積 $\{x\}\times\{y\}$ によって表現できる集合の要素の一つと考えることができる。つまり、生成規則の有限集合 $P$ は、一部が非終端記号で構成される任意の記号列の集合　 $V^*\,N\,V^*$ と、記号列の集合 $V^*$ の直積の部分集合 $P$ $\subset$ $V^*\,N\,V^*$ $\times$ $V^*$ として表すことができる。

¹例えば $S=\{0,1\}$ に対して $S^*=\{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, \ldots\}$ 。これは $S$ の要素を任意に連結して生成しうるすべての列を意味する。

言語

言語 $L$ を生成する文法 (grammar) は形式的に式 ( $\ref{grammar}$ ) のように表すことができる。 $\begin{equation} G = \langle N, \Sigma, P, S \rangle \label{grammar} \end{equation}$ ここで $N$ は非終端記号の有限集合、 $\Sigma$ は終端記号の有限集合、 $P$ は生成規則の有限集合、 $S$ は初期記号である。

初期記号 $S$ から 0 回以上の導出を行って得られる、終端記号のみで構成される記号列 $S'$ を $S$ $\Rightarrow^*$ $S'$ , $S'$ $\in$ $\Sigma^*$ のように表し、 $S'$ を文法 $G$ で生成される語という。同様に文法 $G$ で生成される語 $S'$ の集合 $L(G)$ $=$ $\{S'$ $\in$ $\Sigma^*$ $|$ $S \Rightarrow^*$ $S'\}$ を文法 $G$ で生成される言語という。

文法 $G$ の生成規則 $p:(x,y)$ について以下のように分類する。

句構造文法 (phrase structure grammar): 生成規則に特に制約を持たない文法。
文脈依存文法 (context-sensitive grammar): $p:(w_0\,A\,w_1,w_0\,\alpha\,w_1)$ 、ここで $A \in N$ , $\alpha \in V^+$ , $w_0, w_1 \in V^*$ となる生成規則を持つ文法。
文脈自由文法 (context-free grammar): $p:(A,w)$ 、ここで $A \in N$ , $w \in V^*$ となるような生成規則を持つ文法。
正規文法 (regular grammar): $p:(A,aB)$ または $p:(A,a)$ 、ここで $A,B\in N$ , $a\in\Sigma$ となるような生成規則を持つ文法。

自由文脈文法以外の生成規則 $p:(x,y)$ において $y\ne\epsilon$ である。

それぞれの文法から生成される言語の言語クラスは部分集合の関係にある。 $\begin{equation} \mathcal{L}({\it rg}) \subseteq \mathcal{L}({\it cfg}) \subseteq \mathcal{L}({\it csg}) \subseteq \mathcal{L}({\it psg}) \end{equation}$ したがって、文脈自由文法は文脈依存文法であるとも言えるし、一見して正規文法の形をしているが生成規則の結果に $\epsilon$ を含む文法は文脈自由文法であるといった考え方ができる。

例2. 言語 $\{a^n\,b^n\,|\,n\ge0\}$ は非終端記号 $N$ $=$ $\{S\}$ 、終端記号 $\Sigma$ $=$ $\{a,$ $b\}$ 、生成規則 $P$ $=$ $\{(S,$ $\epsilon),$ $(S,$ $aSb),$ $(S,$ $ab)\}$ 、初期記号 $S$ で構成される文脈自由文法によって生成できることから文脈自由言語である。

例えば $n=3$ の記号列は式 ( $\ref{cfg_n3}$ ) のように生成することができる。 $\begin{equation} S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaabbb \label{cfg_n3} \end{equation}$

例3. 言語 $L=\{a^n\,b^n\,a^n\,|\,n\ge1\}$ は非終端記号 $N$ $=$ $\{S,$ $A,$ $B,$ $T\}$ 、終端記号 $\Sigma$ $=$ $\{a,$ $b\}$ 、生成規則 $P$ $=$ $\{(S,$ $aba),$ $(S,$ $aBTa),$ $(T,$ $ABTa),$ $(T,$ $ABa),$ $(BA,$ $AB),$ $(aA,$ $aa),$ $(Ba,$ $ba),$ $(Bb,$ $bb)\}$ 、初期記号 $S$ で構成される文法 $G$ によって生成できる。

ここで $(S,\cdot)$ , $(T,\cdot)$ は文脈自由文法の生成規則、 $(BA,AB)$ は句構造文法の生成規則、 $(aA,$ $aa),$ $(Ba,$ $ba),$ $(Bb,$ $bb)$ は文脈依存文法の生成規則であることから、文法 $G$ は句構造文法、言語 $L$ は句構造言語と考えることができる。

しかし $(BA,AB)$ の形をした規則は $\{(BA,$ $BX),$ $(BX,$ $AX),$ $(AX,$ $AB)\}$ の文脈依存文法の生成規則に展開することができる。したがって文法 $G$ は文脈依存文法で、それから生成される言語 $L$ は文脈依存言語である。

例えば言語 $L$ 上の $n=3$ の記号列は式 ( $\ref{cfg_n3_2}$ ) のように生成することができる。 $\begin{equation} \def\gen#1{\overset{\tiny #1}{\Longrightarrow}} \begin{array}{lllllll} S & \gen{(S,aBTa)} & aBTa & \gen{(T,ABTa)} & aBABTaa & \gen{(T,ABa)} & aBABABaaa \\ & \gen{(BA,AB)}^* & aAABBBaaa & \gen{(aA,aa)}^* & aaaBBBaaa & \gen{(Ba,ba)} & aaaBBbaaa \\ & \gen{(Bb,bb)}^* & aaabbbaaa \end{array} \label{cfg_n3_2} \end{equation}$

それぞれの文法の表現力は、それを受理できる抽象機械と対応している。

Table 1. Chomsky の標準形に基づく階層。 $A,B\in N$ を非終端記号、 $a\in\Sigma$ を終端記号、 $\alpha\in V^+$ , $w,w_0,w_1\in V^*$ とする。
文法	生成規則	抽象機械	適用例
句構造文法	制限なし	チューリングマシン	自然言語
文脈依存文法	$(w_0\,A\,w_1,w_0\,\alpha\,w_1)$	線形拘束オートマトン	プログラミング言語
文脈自由文法	$(A,w)$	プッシュダウンオートマトン	プログラミング言語
正規文法	$(A,aB)$ または $(A,a)$	有限オートマトン	正規表現

正規言語

正規文法は有限オートマトンで受理される文法、正規言語は正規文法によって生成される言語である。

正規言語 $L$ 上の長さ $n$ 以上のすべての記号列 $z$ は $z = u v w$ , $0 \lt |v| \lt n$ となるように分解できる。この性質は繰り返し定理 (iteration theorem) またはポンピング定理 (pumping theorem) と呼ばれ式 ( $\ref{iter}$ ) のように表される。 $\begin{equation} \forall i \ge 0, \ u\,v^i\,w \in L \label{iter} \end{equation}$ この定数 $n$ は $L$ を受理する有限オートマトンの状態数である。

文脈自由文法

生成規則は $(A, w)$ で表される。この LHS (左要素) の $A\in N$ は単一の非終端文字 (つまりコンテキストを含まない) であり、RHS (右要素) の $w \in V^*$ は任意の終端記号/非終端記号の混合列である。

LL 構文

LL 構文 (LL parser) 再帰下降パーサー (recursive-decent parser) 列の前方の $k$ 個の記号を読み込んで

参考文献

オートマトン・言語理論の基礎 (2003) 近代科学社