正規言語

[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{\inverse}[1]{{#1}^{-1}} \newcommand{\interpret}[1]{[\![#1]\!]} \newcommand{\mathautomaton}[1]{\mathcal{#1}} \newcommand{\mathnat}{\mathbb{N}} \newcommand{\mathcountfunc}{\mathop{\#}} \newcommand{\qed}{\blacksquare} [/math]

正規言語（regular language）とは右線形文法(right linear grammar)または左線形文法(left linear grammar)によって定められる形式言語である。

右線形文法は句構造文法の一種であるから、 右線形言語は句構造言語の一種である。

また、右線形文法は文脈自由文法の一種であるから、 右線形言語は文脈自由言語の一種である。

以下、項目形式言語、句構造言語において定められている言語上の演算や文法の等価性の定義などについては特に断らず用いる。

正規言語の導入

この節では正規言語を定義する。

定義 1 (右線形文法)

右線形文法（right linear grammar）とは

1. 記号集合 $\Sigma$
2. $\Sigma$ と互いに素な変数記号（variable）の空でない有限集合 $V$
3. 生成規則（production rule）と呼ばれる有限集合 $R \subseteq V \times ((\kleenecl{\Sigma}V)\cup \kleenecl{\Sigma})$
4. 開始記号(start symbol)または初期記号と呼ばれる $S\in V$

の４つ組$(V, \Sigma, R, S)$である。

これは、 句構造文法の一種である。また、 文脈自由文法の一種である。

句構造言語のときと同様、$\Sigma$ の元を終端記号(terminal)、$V$ の元を非終端記号(non-terminal)と呼ぶことも多い。

以下では、元$(A, \alpha)\in R$ のことを$A\mathgen\alpha$と書く。

導出、 生成される言語などは 句構造言語と同様に定義される。

正規言語とは何らかの右線形文法によって生成される言語のことを言う。

正規言語の例

この節では正規言語の例を紹介する。

例 2 ($0$ と $1$ からなる有限記号列全体)

$V=\left\{ S \right\}$, $\Sigma=\left\{ 0, 1 \right\}$, $R=\left\{ S\mathgen\emptyword, S\mathgen 0S, S\mathgen 1S \right\}$ とすると、$G=(V, \Sigma, R, S)$ は右線形文法である。

この文法によって生成される言語は $0$ と $1$ からなる有限記号列全体である。

すなわち、$0$ と $1$ からなる有限記号列全体は正規言語である。

上記の文法による導出の例をいくつかあげる。

\begin{gather*} S \Rightarrow \emptyword \\ S \Rightarrow 0S \Rightarrow 0\emptyword = 0 \\ S \Rightarrow 1S \Rightarrow 1\emptyword = 1 \\ S \Rightarrow 0S \Rightarrow 00S \Rightarrow 00\emptyword = 00 \\ S \Rightarrow 0S \Rightarrow 01S \Rightarrow 01\emptyword = 01 \\ S \Rightarrow 1S \Rightarrow 10S \Rightarrow 10\emptyword = 10 \\ S \Rightarrow 1S \Rightarrow 11S \Rightarrow 11\emptyword = 11 \\ S \Rightarrow 0S \Rightarrow 00S \Rightarrow 000S \Rightarrow 000\emptyword = 000 \\ S \Rightarrow 0S \Rightarrow 00S \Rightarrow 001S \Rightarrow 001\emptyword = 001 \\ S \Rightarrow 0S \Rightarrow 01S \Rightarrow 010S \Rightarrow 010\emptyword = 010 \\ S \Rightarrow 0S \Rightarrow 01S \Rightarrow 011S \Rightarrow 011\emptyword = 011 \\ S \Rightarrow 1S \Rightarrow 10S \Rightarrow 100S \Rightarrow 100\emptyword = 100 \\ S \Rightarrow 1S \Rightarrow 10S \Rightarrow 101S \Rightarrow 101\emptyword = 101 \\ S \Rightarrow 1S \Rightarrow 11S \Rightarrow 110S \Rightarrow 110\emptyword = 110 \\ S \Rightarrow 1S \Rightarrow 11S \Rightarrow 111S \Rightarrow 111\emptyword = 111 \end{gather*}

例 3 ($0$ と $1$ からなる有限記号列のうち、$1$をちょうど3個含む記号列全体)

$V=\left\{ S, A_{1}, A_{2}, A_{3} \right\}$, $\Sigma=\left\{ 0, 1 \right\}$, $R=\left\{ S\mathgen 0S, S\mathgen 1A_{1}, A_{1}\mathgen 0A_{1}, A_{1}\mathgen 1A_{2}, A_{2}\mathgen 0A_{2}, A_{2}\mathgen 1A_{3}, A_{3}\mathgen 0A_{3}, A_{3}\mathgen \emptyword \right\}$ とすると、$G=(V, \Sigma, R, S)$ は右線形文法である。

この文法によって生成される言語は $0$ と $1$ からなる有限記号列のうち、$1$をちょうど3個含む記号列全体である。

すなわち、$0$ と $1$ からなる有限記号列のうち、$1$をちょうど3個含む記号列全体は正規言語である。

上記の文法による導出の例をいくつかあげる

\begin{align*} S &\Rightarrow 1A_{1} \Rightarrow 11A_{2} \Rightarrow 111A_{3} \Rightarrow 111\emptyword = 111 \\ S &\Rightarrow 0S \\ &\Rightarrow 01A_{1} \Rightarrow 010A_{1} \Rightarrow 0100A_{1} \\ &\Rightarrow 01001A_{2} \Rightarrow 010010A_{2} \Rightarrow 0100100A_{2} \Rightarrow 01001000A_{2} \\ &\Rightarrow 010010001A_{3} \Rightarrow 0100100010A_{3} \Rightarrow 01001000100A_{3} \Rightarrow 010010001000A_{3} \Rightarrow 0100100010000A_{3} \Rightarrow 0100100010000\emptyword =0100100010000 \end{align*}

例 4 (自然数の二進表現全体)

$V=\left\{ S, A_{1} \right\}$, $\Sigma=\left\{ 0, 1 \right\}$, $R=\left\{ S\mathgen 0, S\mathgen 1A_{1}, A_{1}\mathgen 0A_{1}, A_{1}\mathgen 1A_{1}, A_{1}\mathgen \emptyword \right\}$ とすると、$G=(V, \Sigma, R, S)$ は右線形文法である。

この文法によって生成される言語は 自然数の二進表現全体である。

すなわち、自然数の二進表現全体は正規言語である。

上記の文法による導出の例をいくつかあげる

\begin{gather*} S \Rightarrow 0 \\ S \Rightarrow 1A_{1} \Rightarrow 1\emptyword = 1 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 10\emptyword = 10 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 11\emptyword = 11 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 100A_{1} \Rightarrow 100\emptyword = 100 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 101A_{1} \Rightarrow 101\emptyword = 101 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 110A_{1} \Rightarrow 100\emptyword = 110 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 111A_{1} \Rightarrow 111\emptyword = 111 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 100A_{1} \Rightarrow 1000A_{1} \Rightarrow 1000\emptyword = 1000 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 100A_{1} \Rightarrow 1001A_{1} \Rightarrow 1001\emptyword = 1001 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 101A_{1} \Rightarrow 1010A_{1} \Rightarrow 1010\emptyword = 1010 \\ S \Rightarrow 1A_{1} \Rightarrow 10A_{1} \Rightarrow 101A_{1} \Rightarrow 1011A_{1} \Rightarrow 1011\emptyword = 1011 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 110A_{1} \Rightarrow 1100A_{1} \Rightarrow 1100\emptyword = 1100 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 110A_{1} \Rightarrow 1101A_{1} \Rightarrow 1101\emptyword = 1101 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 111A_{1} \Rightarrow 1110A_{1} \Rightarrow 1110\emptyword = 1110 \\ S \Rightarrow 1A_{1} \Rightarrow 11A_{1} \Rightarrow 111A_{1} \Rightarrow 1111A_{1} \Rightarrow 1111\emptyword = 1111 \end{gather*}

正規言語のクラスの閉包性 その１

この節では正規言語のクラスが 連接 、和集合演算、 Kleene閉包 によって閉じていることを述べる。

命題 5 (正規言語のクラスの閉包性 その１)

1. 形式言語 $L_{1}$, $L_{2}$ が正規言語であるならば $L_{1}L_{2}$ も正規言語である。
2. 形式言語 $L_{1}$, $L_{2}$ が正規言語であるならば $L_{1}\cup L_{2}$ も正規言語である。
3. 形式言語 $L$ が正規言語であるならば $\kleenecl{L}$ も正規言語である。

Proof.

1. 形式言語 $L_{1}$, $L_{2}$ が正規言語であると仮定する。

このとき $L_{1}$, $L_{2}$ を生成する右線形文法がそれぞれ存在する。 $L_{1}$ を生成する右線形文法を $G=(V_{1}, \Sigma, R_{1}, S_{1})$、 $L_{2}$ を生成する右線形文法を $G=(V_{2}, \Sigma, R_{2}, S_{2})$ とする。 このとき、$V_{1}\cap V_{2}=\emptyset$ と仮定しても 一般性を失わない（必要であれば、変数記号を適切に置き換えれば良い）。

さて、

\begin{align*} R_{1}^{(V)}&=\mathsetintension{A\mathgen \gamma \in R_{1}}{\gamma \in \kleenecl{\Sigma}V} \\ R_{1}^{(0)}&=\mathsetintension{A\mathgen \gamma \in R_{1}}{\gamma \in \kleenecl{\Sigma}} \end{align*}

とすると、$R_{1}=R_{1}^{(V)}\cup R_{1}^{(0)}$, $R_{1}^{(V)}\cap R_{1}^{(0)}=\emptyset$ である。

\[ R_{1}^{(S_{2})}:=\mathsetintension{A\mathgen \gamma S_{2}}{A\mathgen \gamma \in R_{1}^{(0)}} \] とすると、 $G=(V_{1}\cup V_{2}, \Sigma, R_{1}^{V}\cup R_{1}^{(S_{2})}\cup R_{2}, S_{1})$ は $L_{1}L_{2}$ を生成する右線形文法である。

2. 形式言語 $L_{1}$, $L_{2}$ が正規言語であると仮定する。

このとき $L_{1}$, $L_{2}$ を生成する右線形文法がそれぞれ存在する。 $L_{1}$ を生成する右線形文法を $G=(V_{1}, \Sigma, R_{1}, S_{1})$、 $L_{2}$ を生成する右線形文法を $G=(V_{2}, \Sigma, R_{2}, S_{2})$ とする （ただし、$V_{1}\cap V_{2}=\emptyset$ とする）。

このとき、右線形文法 $G=(V_{1}\cup V_{2}\cup \mathsetextension{S}, \Sigma, R_{1}\cup R_{2}\cup \mathsetextension{S\mathgen S_{1}, S\mathgen S_{2}}, S)$ （ただし、$S\notin V_{1}\cup V_{2}$）は $L_{1}\cup L_{2}$ を生成する。

3. 形式言語 $L$ が正規言語であると仮定する。

このとき $L$ を生成する右線形文法がそれぞれ存在する。 $L$ を生成する右線形文法を $G=(V, \Sigma, R, S)$ とする。

さて、

\begin{align*} R^{(V)}&=\mathsetintension{A\mathgen \gamma \in R}{\gamma \in \kleenecl{\Sigma}V} \\ R^{(0)}&=\mathsetintension{A\mathgen \gamma \in R}{\gamma \in \kleenecl{\Sigma}} \end{align*}

とすると、$R=R^{(V)}\cup R^{(0)}$, $R^{(V)}\cap R^{(0)}=\emptyset$ である。

\[R^{(S)}:=\mathsetintension{A\mathgen \gamma S}{A\mathgen \gamma \in R, \gamma \in \kleenecl{\Sigma}}\] とすると、右線形文法 $G=(V, \Sigma, R^{(V)}\cup R^{(S)}\cup \{S\mathgen \emptyword\}, S)$ は $\kleenecl{L}$ を生成する。

□

正規表現、有限オートマトンとの関係

この節では正規言語、正規表現および有限オートマトンとの関係を述べる。以下では正規表現と有限オートマトンの定義などは既知とする。

定理 6

言語 $L$ について以下は同値である。

1. $L$ は正規言語である。
2. $L=\interpret{\alpha}$ なる正規表現 $\alpha$ が存在する。
3. $L$ を受理する有限オートマトンが存在する。

この節ではこの定理を証明する。

補題 7

正規言語 $G=(V, \Sigma, R, S)$ に対して、 $G$ と 等価 であって、 すべての生成規則の右辺が $(\Sigma \cup\{\emptyword\})(V \cup\{\emptyword\})$ の元である右線形文法が存在する。

Proof.

正規言語 $G=(V, \Sigma, R, S)$ について、 $R=\{A_{0}\mathgen \alpha_{0}, \ldots, A_{n}\mathgen \alpha_{n}\}$ （ただし $n\in\mathnat$） とする。

$G_{i}=(V_{i}, \Sigma, R_{i}, S)$ （ただし $n=0, \ldots, n+1$） を次のように定義する。

• $G_{0}=G$
• $\alpha_{i}\in (\Sigma \cup\{\emptyword\})(V \cup\{\emptyword\})$

のとき、$G_{i+1}:=G_{i}$ とする。

• $\alpha_{i}\in \kleenecl{\Sigma} \setminus (\Sigma \cup\{\emptyword\})$ のとき、$\alpha_{i}=a_{0}\ldots a_{m}$ （ただし、$m$ は $1$ 以上の自然数であって、$a_{j}\in \Sigma$ for $j\in \mathnat$）とする。
  • $V_{i+1}:=V_{i}\cup \{B_{0}, \ldots, B_{m}\}$ （ただし、各 $B_{j}$ は $B_{j}\notin V_{i}\cup \Sigma$ を満たす変数記号）。
  • $R_{i+1}:=R_{i}\setminus \{A_{i}\mathgen \alpha_{i}\}\cup \{A_{i} \mathgen a_{0}B_{0}, B_{0} \mathgen a_{1}B_{1}, \ldots, B_{m-1} \mathgen a_{m}B_{m}, B_{m}\mathgen \emptyword\}$。
• $\alpha_{i}\in \kleenecl{\Sigma}V\setminus (\Sigma \cup\{\emptyword\})V$ のとき、$\alpha_{i}=a_{0}\ldots a_{m} A'_{i}$ （ただし、$m$ は $1$ 以上の自然数であって、$a_{j}\in \Sigma$ for $j\in \mathnat$）とする。
  • $V_{i+1}:=V_{i}\cup \{B_{0}, \ldots, B_{m}\}$ （ただし、各 $B_{j}$ は $B_{j}\notin V_{i}\cup \Sigma$ を満たす変数記号）。
  • $R_{i+1}:=R_{i}\setminus \{A_{i}\mathgen \alpha_{i}\}\cup \{A_{i} \mathgen a_{0}B_{0}, B_{0} \mathgen a_{1}B_{1}, \ldots, B_{m-1} \mathgen a_{m}B_{m}, B_{m}\mathgen A'_{i}\}$。

各 $i$ に対して、 $L(G_{i})=L(G_{i+1})$ に注意すると $G_{n+1}$ が求める文法であることがわかる。

□

Proof of 定理 6.

(2. $\Rightarrow$ 1.) $L=\interpret{\alpha}$ なる正規表現 $\alpha$ が存在するとき、 $L$ を生成する右線形文法が存在する（つまり $L$ は正規言語である）ことを言えば良い。

正規表現の構成についての帰納法により示す。

Case 1. $L=\interpret{\emptyset}=\emptyset$ のとき、 $L$ を生成する右線形文法として $G=(\{S\}, \Sigma, \emptyset, S)$ が存在する。

Case 2. $L=\interpret{\emptyword}=\{\emptyword\}$ のとき、 $L$ を生成する右線形文法として $G=(\{S\}, \Sigma, \{S \mathgen \emptyword\}, S)$ が存在する。

Case 3. $L=\interpret{a}=\{a\}$ (ただし、$a\in \Sigma$) のとき、 $L$ を生成する右線形文法として $G=(\{S\}, \Sigma, \{S \mathgen a\}, S)$ が存在する。

Case 4. $L=\interpret{\alpha\beta}=\interpret{\alpha}\cdot\interpret{\beta}$ （ただし、$\alpha$, $\beta$ は正規表現）とする。

帰納法の仮定から $\interpret{\alpha}$, $\interpret{\beta}$ は正規言語である。 命題 5 の 1. より、 $\interpret{\alpha}\cdot\interpret{\beta}$ は正規言語である。

Case 5. $L=\interpret{\alpha +\beta}=\interpret{\alpha}\cup \interpret{\beta}$ （ただし、$\alpha$, $\beta$ は正規表現）とする。

帰納法の仮定から $\interpret{\alpha}$, $\interpret{\beta}$ は正規言語である。 命題 5 の 2. より、 $\interpret{\alpha}\cup \interpret{\beta}$ は正規言語である。

Case 6. $L=\interpret{\kleenecl{\alpha}}=\kleenecl{\interpret{\alpha}}$ （ただし、$\alpha$ は正規表現）とする。

帰納法の仮定から $\interpret{\alpha}$ は正規言語である。 命題 5 の 3. より、 $\kleenecl{\interpret{\alpha}}$ は正規言語である。

以上、Case 1-6 より(2. $\Rightarrow$ 1.) は示された。

(1. $\Rightarrow$ 3.) $L$ が正規言語であるとき、補題 7から すべての生成規則の右辺が $(\Sigma \cup\{\emptyword\})(V \cup\{\emptyword\})$ の元である$L$ を生成する右線形文法が存在する。 この文法を $G=(V, \Sigma, R, S)$ とする。

まず、有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \delta, q_{I}, F)$ を次のように定義する。

• $Q=V \cup \{f\}$ （ただし、$f\notin V$）
• $q_{I}=S$
• $\Delta = \{(A, a, A') | A, A'\in V, a\in \Sigma\cup\{\emptyword\}, A \mathgen aA'\in R \} \cup \{ (A, a, f) | A\in V, a\in \Sigma\cup\{\emptyword\}, A \mathgen a\in R\} \}$
• $F=\{f\}$

次に、$wA\in \kleenecl{\Sigma}V$ に対して以下の２条件は同値であることを示す。

(a) $S$ から始まる \[ (S=)\alpha_{0} \Rightarrow_{G} \alpha_{1} \Rightarrow_{G}\cdots \Rightarrow_{G} \alpha_{n}(=wA)\] (ただし、$\alpha_{i}=w_{i}A_{i}$ for $1\leq i\leq n$) という導出列が存在する。

(b) 記号列 $w$ による $S$ から $A$ への$\mathautomaton{A}$ の状態遷移 \[ A_{0}, A_{1}, \ldots, A_{n}\] （ただし、$A_{0}=S$, $A_{n}=A$）が存在する。

(a) $\Rightarrow$ (b) を $n$ についての帰納法により示す。

$n=1$ のとき、 $w=a$ なる $a\in\Sigma\cup\{\emptyword\}$が存在し、 $S\mathgen aA \in R$ であるはずである。 このとき、$\mathautomaton{A}$ の定義から $(S, a, A)\in \Delta$である。 ゆえに、記号列 $w$ による $S$ から $A$ への$\mathautomaton{A}$ の状態遷移 \[ S, A \] が存在する。

$n>1$ のとき、 $w=w'a$ （ただし、$a\in \Sigma\cup\{\emptyword\}$）とおく。 このとき、$G$ の生成規則の形から $w_{n-1}=w'$, $A_{n-1}\mathgen aA \in R$ である。 このとき、帰納法の仮定から 記号列 $w'$ による $S$ から $A_{n-1}$ への$\mathautomaton{A}$ の状態遷移 \[S, A_{1}, \ldots, A_{n-1} \] が存在する。 $A_{n-1}\mathgen aA \in R$ であるから、 $(A_{n-1}, a, A)\in \Delta$であることに注意すると 記号列 $w$ による $S$ から $A$ への$\mathautomaton{A}$ の状態遷移 \[ S, A_{1}, \ldots, A_{n-1}, A \] が存在する。

(b) $\Rightarrow$ (a) を $n$ についての帰納法により示す。

$n=1$ のとき、 $w=a$ なる $a\in\Sigma\cup\{\emptyword\}$が存在し、 $(S, a, A)\in \Delta$ のはずである。 このとき、$\mathautomaton{A}$ の定義から $S\mathgen aA \in R$ である。ゆえに \[ S \Rightarrow_{G} aA \] である。

$n>1$ のとき、 記号列 $w$ による $S$ から $A$ への$\mathautomaton{A}$ の状態遷移 \[A_{0}, A_{1}, \ldots, A_{n-1}A_{n} \] （ただし、$A_{0}=S$, $A_{n}=A$）が存在すると仮定する。 すると、 $w=w'a$, $(A_{n-1}, a, A)\in \Delta$ を満たす $a\in\Sigma\cup\{\emptyword\}$, $w'\in\kleenecl{\Sigma}$ が存在する。 すると、記号列 $w'$ による $S$ から $A_{n-1}$ への$\mathautomaton{A}$ の状態遷移 \[A_{0}, A_{1}, \ldots, A_{n-1} \] が存在する。 帰納法の仮定から \[ (S=)\alpha_{0} \Rightarrow_{G} \alpha_{1} \Rightarrow_{G} \cdots \Rightarrow_{G} \alpha_{n-1}(=w'A_{n-1})\] という導出列が存在する。 $(A_{n-1}, a, A)\in \Delta$ であるから、 $A_{n-1} \mathgen aA\in R$ であるので、 \[ (S=)\alpha_{0} \Rightarrow_{G} \alpha_{1} \Rightarrow_{G} \cdots \Rightarrow_{G} w'A_{n-1} \Rightarrow_{G} w'aA(=wA) \] という導出列が存在する。

最後に $L=L(\mathautomaton{A})$ を示す。

$w\in L$ を仮定する。 すると、導出列 \[ S \Rightarrow_{G} \alpha_{0} \Rightarrow_{G} \cdots \Rightarrow_{G} \alpha_{n} \Rightarrow_{G} w\] が存在する。 $G$ の生成規則の形から $w=w'a$, $\alpha_{n}=w'A_{n}$, $A_{n}\mathgen a \in R$ を満たす $A_{n}\in V$, $a\in \Sigma\cup\{\emptyword\}$, $w'\in \kleenecl{\Sigma}$ が存在する。 このとき、 記号列 $w'$ による $S$ から $A_{n}$ への $\mathautomaton{A}$ の状態遷移 \[ S, A_{0}, A_{1}, \ldots, A_{n} \] が存在する。 $A_{n}\mathgen a \in R$ であるから、 $(A_{n}, a, f)\in \Delta$ に注意すると、 記号列 $w'a=w$ による $S$ から $f$ への$\mathautomaton{A}$ の状態遷移 \[ S, A_{0}, \ldots, A_{n}, f \] が存在する。 ゆえに $w\in L(\mathautomaton{A})$ である。

逆に、$w\in L(\mathautomaton{A})$ とする。 すると、 記号列 $w$ による $S$ から $f$ への$\mathautomaton{A}$ の状態遷移 \[ S, A_{0}, A_{1}, \ldots, A_{n}, f\] が存在する。 すると、 $w=w'a$, $(A_{n}, a, f) \in \Delta$ を満たす $a\in \Sigma\cup\{\emptyword\}$, $w'\in \kleenecl{\Sigma}$ が存在する。 また、 記号列 $w'$ による $S$ から $A_{n}$ への$\mathautomaton{A}$ の状態遷移 \[ S, A_{0}, \ldots, A_{n} \] が存在する。 よって、導出列 \[ S \Rightarrow_{G} \alpha_{0} \Rightarrow_{G} \cdots \Rightarrow_{G} \alpha_{n} (=w'A_{n})\] が存在する。 $(A_{n}, a, f) \in \Delta$ から $A_{n}\mathgen a$ であるので、 $w$ の導出列 \[ S \Rightarrow_{G} \alpha_{0} \Rightarrow_{G} \cdots \Rightarrow_{G} \alpha_{n} \Rightarrow_{G} w (=w'a)\] が存在する。

以上より(1. $\Rightarrow$ 3.)は示された。

(3. $\Rightarrow$ 2.) $L$ を受理する有限オートマトンを $\mathautomaton{A}=(\{q_{1}, q_{2}, \ldots, q_{n}\}, \Sigma, \Delta, q_{1}, \{q_{F_{0}}, q_{F_{1}}, \ldots, q_{F_{m}}\})$ とおく。

簡単のため、以下

\begin{align*} \sum_{\alpha \in A} \alpha &= (\alpha_{0}+ \cdots + \alpha_{k}) \quad \text{（ただし、A は正規表現の空でない有限集合であって、A=\{a_{0}, \ldots, a_{k}\}）}, \\ Q_{ij}&=\{a\in \Sigma\cup\{\emptyword\} | (q_{i}, a, q_{j})\in \Delta\} \end{align*}

という略記を用いる。

正規表現 $\alpha^{(l)}_{ij}$ （ただし、$1\leq i, j \leq n$, $0\leq l \leq n$）を次のように帰納的に定める。

\begin{align*} \alpha^{(0)}_{ij}&= \begin{cases} \emptyset, & \text{if Q_{ij}=\emptyset}, \\ \sum_{a\in Q_{ij}}a, & \text{if Q_{ij}\neq \emptyset, i\neq j}; \\ \kleenecl{\left(\sum_{a\in Q_{ij}}a\right)}, & \text{if Q_{ij}\neq \emptyset, i=j}; \end{cases}\\ \alpha^{(l)}_{ij}&=\alpha^{(l-1)}_{ij} + \alpha^{(l-1)}_{il}\left(\kleenecl{\alpha^{(l-1)}_{ll}}\right)\alpha^{(l-1)}_{lj}, \quad \text{（ただし、1\leq l）}. \end{align*}

$w\in \interpret{\alpha^{(l)}_{ij}}$ であるとき、 記号列 $w$ による $q_{i}$ から $q_{j}$ への$\mathautomaton{A}$ の状態遷移 \[ q_{k_{0}}, q_{k_{1}}, \ldots, q_{k_{p}} \] （ただし、$k_{0}=i$, $k_{p}=j$, $1\leq q\leq p-1$ のとき $1\leq k_{q} \leq l$）が存在することを $l$ についての帰納法により示す。

$l=0$ については明らか。

$l>0$ のとき、$w\in \interpret{\alpha^{(l)}_{ij}}$ であるとすると、 $w\in \interpret{\alpha^{(l-1)}_{ij}}$ または $w\in \interpret{\alpha^{(l-1)}_{il}\left(\kleenecl{\alpha^{(l-1)}_{ll}}\right)\alpha^{(l-1)}_{lj}}$ である。 $w\in \interpret{\alpha^{(l-1)}_{ij}}$ のときは帰納法の仮定より明らか。

$w\in \interpret{ \alpha^{(l-1)}_{il}\left(\kleenecl{\alpha^{(l-1)}_{ll}}\right)\alpha^{(l-1)}_{lj}}$ とする。すると $w_{1}\in \interpret{\alpha^{(l-1)}_{il}}$, $w_{2}\in \interpret{\alpha^{(l-1)}_{ll}}$, $w_{3}\in \interpret{\alpha^{(l-1)}_{lj}}$, $w=w_{1}(w_{2})^{s}w_{3}$ （ただし、$s\in \mathnat$） を満たす記号列 $w_{1}$, $w_{2}$, $w_{3}$ が存在する。

帰納法の仮定から、 記号列 $w_{t}$ （$t=1, 2, 3$）による$\mathautomaton{A}$ の状態遷移 \[ q_{k_{t0}}, q_{k_{t1}}, \ldots, q_{k_{tp}} \] （ただし、$k_{10}=i$, $k_{1p}=k_{20}=k_{2p}=k_{30}=l$, $k_{3p}=j$, $1\leq q\leq p-1$ のとき $1\leq k_{q} \leq l-1$）が存在する。 すると、 記号列 $w$ による $q_{i}$ から $q_{j}$ への$\mathautomaton{A}$ の状態遷移 \[ q_{k_{10}}, q_{k_{11}}, \ldots, q_{k_{1p}}, \overbrace{q_{k_{21}}, \ldots, q_{k_{2p}}}^{s}, q_{k_{31}}, \ldots, q_{k_{3p}} \] が存在することがわかる。

以上のことに注意すると、 \[ \alpha^{(n)}_{1F_{0}}+\alpha^{(n)}_{1F_{1}}+ \cdots + \alpha^{(n)}_{1F_{m}}\] は $\mathautomaton{A}$ が受理する記号列全体である。

以上より(3. $\Rightarrow$ 2.)は示された。

□

Myhill-Nerodeの定理

この節ではMyhill-Nerodeの定理について述べる。 この定理は正規言語の左商による定式化とみなせる。

定理 8 (Myhill-Nerodeの定理)

$\Sigma$ 上の形式言語 $L$ について以下は同値である。

1. $L$ は正規言語である。
2. $\inverse{\kleenecl{\Sigma}}L$ は有限集合。

Proof.

(1. $\Rightarrow$ 2.) 形式言語 $L$ は正規言語であると仮定する。

定理 6 より、$L$ を受理する有限オートマトンが存在する。 よって、 $L$ を受理する決定性有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が存在する。

$\mathautomaton{A}$ は決定性有限オートマトンなので、任意の記号列 $w\in \kleenecl{\Sigma}$ に対して、次のいずれかが成り立つことに注意する。

1. 記号列 $w\in \kleenecl{\Sigma}$ による $q_{I}$ から始まる $\mathautomaton{A}$ の状態遷移は存在しない。
2. 記号列 $w\in \kleenecl{\Sigma}$ による $q_{I}$ から $q_{w} への$ $\mathautomaton{A}$ の状態遷移が存在し、$q_{w}$ は一意。

前者のとき、$\inverse{w}L$ は空集合である。 後者のとき、決定性有限オートマトン $\mathautomaton{A}_{w}=(Q, \Sigma, \Delta, q_{w}, F)$ は $\inverse{w}L$ を受理する。

$Q$ は有限集合であり、$q_{w} = q_{w'}$ ならば $\mathautomaton{A}_{w} = \mathautomaton{A}_{w'}$ に注意すると、 $\inverse{\kleenecl{\Sigma}}L$ の濃度は高々 $\mathcountfunc{Q} + 1$ である （ただし、$\#$ は有限集合を受け取りそこに所属する元の個数を返す関数）。

(2. $\Rightarrow$ 1.) $\Sigma$ 上の形式言語 $L$ について $\inverse{\kleenecl{\Sigma}}L$ は有限集合と仮定する。

集合 $\Delta_{L}$ と $F_{L}$ を次のように定義する。 \begin{align*} \Delta_{L} &:= \mathsetintension{(\inverse{w}L, a, \inverse{(wa)}L)}{w\in\kleenecl{\Sigma}} \\ F_{L} &:= \mathsetintension{L'\in \inverse{\kleenecl{\Sigma}}L}{\emptyword\in L'} \end{align*}

$\inverse{\kleenecl{\Sigma}}L$ は有限集合であることから、 $\mathautomaton{A}_{L}=(\inverse{\kleenecl{\Sigma}}L, \Sigma, \Delta_{L}, L, F_{L})$ は有限オートマトンである。

$\mathautomaton{A}_{L}$ が受理する言語が $L$ であることを示す。

$w\in L$ を仮定してする。$w$ が $\mathautomaton{A}_{L}$ に受理されることを示す。

このとき、記号列 $w$ による $L$ から $\inverse{w}L$ への $\mathautomaton{A}_{L}$ の状態遷移が存在する。 $w\in L$ であるから、$\emptyword\in \inverse{w}L$。よって $\inverse{w}L\in F_{L}$。 ゆえに $w$ は $\mathautomaton{A}_{L}$ に受理される。

$w$ が $\mathautomaton{A}_{L}$ に受理されることを仮定する。$w\in L$ を示す。

$w$ が $\mathautomaton{A}_{L}$ に受理されることから 記号列 $w$ による $L$ から $\inverse{w}L$ への $\mathautomaton{A}_{L}$ の状態遷移が存在し、 $\inverse{w}L\in F_{L}$ である。よって $\emptyword\in \inverse{w}L$。これは $w\in L$ を意味する。

以上より $\mathautomaton{A}_{L}$ が受理する言語は $L$ である。

□

正規言語のクラスの閉包性 その２

この節では正規言語のクラスが補集合演算、共通部分演算、鏡像、左商、右商によって閉じていることを述べる。

命題 9

1. $\kleenecl{\Sigma}$ 上の形式言語 $L$ が正規言語であるならば $\kleenecl{\Sigma}\setminus L$ も正規言語である。
2. 形式言語 $L_{1}$, $L_{2}$ が正規言語であるならば $L_{1}\cap L_{2}$ も正規言語である。
3. 形式言語 $L$ が正規言語であるならば $\mirrorim{L}=\mathsetintension{\mirrorim{w}}{w\in L}$ も正規言語である。
4. $\kleenecl{\Sigma}$ 上の形式言語 $L$ が正規言語であるならば $w\in\kleenecl{\Sigma}$ による左商 $\inverse{w}L$ および右商 $L\inverse{w}$ はいずれも正規言語である。

Proof.

1. 形式言語 $L$ は正規言語であると仮定する。

定理 6 より、$L$ を受理する有限オートマトンが存在する。 よって、 $L$ を受理する決定性有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が存在する。

$q_{\infty}\notin Q$ とする。また、 \[ \Delta_{\infty}=\mathsetintension{(q,a,q_{\infty})}{\text{任意の$q'$に対して}(q,a,q')\notin \Delta} \cup \mathsetintension{(q_{\infty}, a, q_{\infty})}{a\in\Sigma} \] とする。

すると決定性有限オートマトン $\mathautomaton{A}_{\infty}=(Q\cup\mathsetextension{q_{\infty}}, \Sigma, \Delta\cup\Delta_{\infty}, q_{I}, F)$ は $L$ を受理し、 任意の記号列にたいして、状態遷移を持つ。 このとき、$\mathautomaton{A}'=(Q\cup\mathsetextension{q_{\infty}}, \Sigma, \Delta\cup\Delta_{\infty}, q_{I}, {Q\cup\mathsetextension{q_{\infty}}\setminus F})$ は $\kleenecl{\Sigma}\setminus L$ を受理する決定性有限オートマトンである。よって、$\kleenecl{\Sigma}\setminus L$ は正規言語。

2. $L_{1}$, $L_{2}$ を正規言語とする。 このとき、 $\kleenecl{\Sigma}\setminus L_{1}$, $\kleenecl{\Sigma}\setminus L_{2}$ もまた正規言語である。 命題 5 の 2. より $L_{1}\cap L_{2} = \left(\kleenecl{\Sigma}\setminus L_{1}\right)\cup\left(\kleenecl{\Sigma}\setminus L_{2}\right)$ は正規言語である。

3. $L$ を正規言語とする。定理 6 より、 $L$ を受理する有限オートマトン $\mathautomaton{A}=\left(Q, \Sigma, \Delta, q_{0}, F\right)$ が存在する。

このとき、集合 $\mirrorim{\Delta}$ を次のように定義する。 \[\mirrorim{\Delta} = \mathsetintension{ \left(q_{1}, a, q_{0} \right) }{\left(q_{0}, a, q_{1} \right) \in \Delta} \]

$q\in F$ について、 $\mathautomaton{A}_{q}=\left(Q, \Sigma, \mirrorim{\Delta}, q, \mathsetextension{q_{0}}\right)$ とおく。このとき、$L\left(\mathautomaton{A}_{q}\right)$ は正規言語である。また、

\[\mirrorim{L} = \bigcup_{q\in F} L\left(\mathautomaton{A}_{q}\right)\]

である。命題 5 の 2. より $\mirrorim{L}$ は正規言語である。

4. 形式言語 $L$ は正規言語であると仮定する。

定理 6 より、$L$ を受理する有限オートマトンが存在する。 よって、 $L$ を受理する決定性有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が存在する。

$\mathautomaton{A}$ は決定性有限オートマトンなので、任意の記号列 $w\in \kleenecl{\Sigma}$ に対して、次のいずれかが成り立つことに注意する。

1. 記号列 $w\in \kleenecl{\Sigma}$ による $q_{I}$ から始まる $\mathautomaton{A}$ の状態遷移は存在しない。
2. 記号列 $w\in \kleenecl{\Sigma}$ による $q_{I}$ から $q_{w} への$ $\mathautomaton{A}$ の状態遷移が存在し、$q_{w}$ は一意。

前者のとき、$\inverse{w}L$ は空集合である。このとき、$\inverse{w}L$ は正規言語である。

後者のとき、決定性有限オートマトン $\mathautomaton{A}_{w}=(Q, \Sigma, \Delta, q_{w}, F)$ は $\inverse{w}L$ を受理する。 よって、$\inverse{w}L$ は正規言語である。

さて、 \[L\inverse{w}=\mirrorim{\mirrorim{L\inverse{w}}}=\mirrorim{\mirrorim{\inverse{w}}\mirrorim{L}}\] であるから、$L\inverse{w}$ も正規言語である。

□

正規言語と左線形文法

この節では正規言語と左線形文法との関係を述べる。

定義 10 (左線形文法)

左線形文法（left linear grammar）とは

1. 記号集合 $\Sigma$
2. $\Sigma$ と互いに素な変数記号（variable）の有限集合 $V$
3. 生成規則（production rule）と呼ばれる有限集合 $R \subseteq V \times (V(\kleenecl{\Sigma})\cup \kleenecl{\Sigma})$
4. 開始記号(start symbol)または初期記号と呼ばれる $S\in V$

の４つ組$(V, \Sigma, R, S)$である。

これは、 句構造文法の一種である。また、 文脈自由文法の一種である。

命題 11

言語 $L$ について以下は同値である。

1. $L$ は正規言語である。
2. $L$ を生成する左線形文法が存在する。

補題 12

$L$ が正規言語であるとき、$\mirrorim{L}$ を生成する左線形文法が存在する。

Proof.

$L$ を正規言語とすると、$L$ を生成する右線形文法 $(V, \Sigma, R, S)$ が存在する。 \[\mirrorim{R}=\mathsetintension{A\mathgen \mirrorim{\alpha}}{A\mathgen \alpha \in R}\] とすると、$(V, \Sigma, \mirrorim{R}, S)$は$\mirrorim{L}$ を生成する左線形文法である。

□

補題 13

$L$ を生成する左線形文法が存在するとき、$\mirrorim{L}$ は正規言語。

Proof.

$L$ を生成する左線形文法 $(V, \Sigma, R, S)$ が存在すると仮定する。 \[\mirrorim{R}=\mathsetintension{A\mathgen \mirrorim{\alpha}}{A\mathgen \alpha \in R}\] とすると、$(V, \Sigma, \mirrorim{R}, S)$は$\mirrorim{L}$ を生成する右線形文法である。 よって、$\mirrorim{L}$ は正規言語。

□

Proof of 命題 11

(1. $\Rightarrow$ 2.) $L$ を正規言語とする。 命題 9 より $\mirrorim{L}$ は正規言語である。 補題 12 より $L=\mirrorim{\mirrorim{L}}$ を生成する左線形文法が存在する。

(2. $\Rightarrow$ 1.) $L$ を生成する左線形文法が存在すると仮定する。 補題 13 より $\mirrorim{L}$ は正規言語。 命題 9 より $L$ は正規言語である。

□

正規言語ではない形式言語の例

この節では正規言語ではない形式言語の例を紹介する。

そのような例が存在すること自体は右線形文法が 高々可算個しかないことと形式言語の濃度が 非加算であることに注意すると、明らかである。 しかし、その具体例を構成し、正規言語ではないことを示すことはそれほど簡単ではない。このとき強力な武器となるのが 反復補題である。

反復補題 については当該項目を参照せよ。

例 14 ($0^{n}1^{n}$ という形をした記号列全体)

$0^{n}1^{n}$ （ただし、$n\in\mathnat$）という形の記号列全体は正規言語ではない。しかしながら文脈自由言語ではある。この記号列全体を生成する 文脈自由文法は この例を参照せよ。

$0^{n}1^{n}$ という形の記号列全体が正規言語ではないことの証明

背理法により示す。

$0^{n}1^{n}$ という形の記号列全体 $L$ が正規言語であると仮定する。 定理 6より、$L=L(\mathautomaton{A})$ を満たす 有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が存在する。

$n_{0}=|Q|$ とする。仮定より $\mathautomaton{A}$ は $w=0^{n_{0}}1^{n_{0}}$ を受理する。 すると$\left|w\right|>n_{0}$ であるから 反復補題 より 次の四条件を満たす記号列 $x$, $y$, $z$ が存在する。

1. $w=xyz$。
2. $\left|y\right|>0$。
3. 任意の$m\in\mathnat$に対して、記号列 $xy^{m}z$ は

$\mathautomaton{A}$ に受理される。

1. $|xy|\leq n_{0}$。

このとき、 $xy=0^{k}$ （ただし、$0\lt k\leq n_{0}$） であることに注意する。 すると、 $x=0^{k_{0}}$, $y=0^{k_{1}}$ （ただし、$0\leq k_{0}\leq k$, $0\lt k_{1}\leq k$, $k=k_{0}+k_{1}$） を満たす自然数 $k_{0}$, $k_{1}$ が存在する。

さて、$\mathautomaton{A}$ は 反復補題の条件から、 記号列 $xz$ を受理するはずである。 しかし、$xz=0^{n_{0}-k_{1}}b^{n_{0}}$, $n_{0}-k_{1}\lt n_{0}$ であるから $xz\notin L$ である。 これは $L=L(\mathautomaton{A})$ に矛盾する。

□

例 15 ($w\mirrorim{w}$ という形をした記号列全体)

$w\mirrorim{w}$（ただし、$n\in\mathnat$）という形の記号列全体は正規言語ではない。しかしながら文脈自由言語ではある。この記号列全体を生成する 文脈自由文法は この例を参照せよ。

$w\mirrorim{w}$ という形の記号列全体が正規言語ではないことの証明

背理法により示す。

$w\mirrorim{w}$ という形の記号列全体 $L$ が正規言語であると仮定する。 定理 6より、 $L=L(\mathautomaton{A})$ を満たす 有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が存在する。

$n_{0}=|Q|$ とする。以下 $w_{0}=0^{n_{0}}1$ とする。 仮定より $\mathautomaton{A}$ は $w_{0}\mirrorim{w_{0}}$ を受理する。 すると $\left|w_{0}\mirrorim{w_{0}}\right|>n_{0}$ であるから 反復補題 より 次の四条件を満たす記号列 $x$, $y$, $z$ が存在する。

1. $w_{0}\mirrorim{w_{0}}=xyz$。
2. $\left|y\right|>0$。
3. 任意の$m\in\mathnat$に対して、記号列 $xy^{m}z$ は

$\mathautomaton{A}$ に受理される。

1. $|xy|\leq n_{0}$。

このとき、 $xy=0^{k}$ （ただし、$0\lt k\leq n_{0}$） であることに注意する。 すると、 $x=0^{k_{0}}$, $y=0^{k_{1}}$ （ただし、$0\leq k_{0}\leq k$, $0\lt k_{1}\leq k$, $k=k_{0}+k_{1}$） を満たす自然数 $k_{0}$, $k_{1}$ が存在する。

さて、$\mathautomaton{A}$ は 反復補題 の条件から、 記号列 $xz$ を受理するはずである。 しかし、$xz=0^{n_{0}-k_{1}}1\mirrorim{w_{0}}=0^{n_{0}-k_{1}}110^{n_{0}}$, $n_{0}-k_{1}\lt n_{0}$ であるから $xz\notin L$ である。 これは $L=L(\mathautomaton{A})$ に矛盾する。

□

参考文献

1. 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、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
2. 五十嵐喜英他、『数理情報科学シリーズ ２４ オートマトンと形式言語の基礎』、牧野書店、2011

関連項目

• 形式言語
• 正規表現

Chomsky階層

文法のタイプ	言語のクラス	計算モデル
タイプ0	句構造言語	Turingマシン
タイプ1	文脈依存言語	線形有界オートマトン
タイプ2	文脈自由言語	プッシュダウン・オートマトン
タイプ3	正規言語	有限オートマトン