正規言語

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

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

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

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

$\global\def\mathderiv{\mathrel{\mathop{\Rightarrow}}^{*}}$ $\global\def\mathgen{\rightsquigarrow}$ $\global\def\emptyword{\varepsilon}$ $\global\def\kleenecl#1{{#1}^{*}}$ $\global\def\interpret#1{[\![#1]\!]}$ $\global\def\mathnat{\mathbb{N}}$ $\global\def\mathautomaton#1{\mathcal{#1}}$ $\global\def\mirrorim#1{\overleftarrow{#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$

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

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

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

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

導出

句構造言語導出の節を参照。

正規言語の定義

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

正規言語の例

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

$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$ からなる有限記号列全体は正規言語である。

$0$ と $1$ からなる有限記号列の導出の例

上記の文法による $0$ と $1$ からなる有限記号列の導出の例をいくつかあげる。

$$ 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$$

$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個含む記号列全体は正規言語である。

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

上記の文法による $0$ と $1$ からなる有限記号列のうち、$1$をちょうど3個含む記号列の導出の例をいくつかあげる

$$ 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$$

自然数の二進表現全体

$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)$ は右線形文法である。

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

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

自然数の二進表現の導出の例

上記の文法による自然数の二進表現の導出の例をいくつかあげる

$$ 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$$

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

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

定理 1

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

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

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

補題 2

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

補題 2の証明

正規言語 $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}$ が求める文法であることがわかる。 $\blacksquare$

定理 1の証明

(2. $\Rightarrow$ 1.) $L=\interpret{\alpha}$ なる正規表現 $\alpha$ が存在するとき、 $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}$ を生成する右線形文法がそれぞれ存在する。 $\interpret{\alpha}$ を生成する右線形文法を $G=(V_{\alpha}, \Sigma, R_{\alpha}, S_{\alpha})$、 $\interpret{\beta}$ を生成する右線形文法を $G=(V_{\beta}, \Sigma, R_{\beta}, S_{\beta})$ とする。 このとき、$V_{\alpha}\cap V_{\beta}=\emptyset$ と仮定しても 一般性を失わない(必要であれば、変数記号を適切に置き換えれば良い)。

さて、 $$R_{\alpha}^{(V)}=\{ A\mathgen \gamma \in R_{\alpha} | \gamma \in \kleenecl{\Sigma}V \}$$ $$R_{\alpha}^{(0)}=\{ A\mathgen \gamma \in R_{\alpha} | \gamma \in \kleenecl{\Sigma} \}$$ とすると、$R_{\alpha}=R_{\alpha}^{(V)}\cup R_{\alpha}^{(0)}$, $R_{\alpha}^{(V)}\cap R_{\alpha}^{(0)}=\emptyset$ である。 $$R_{\alpha}^{(S_{\beta})}:=\{ A\mathgen \gamma S_{\beta} | A\mathgen \gamma \in R_{\alpha}, \gamma \in \kleenecl{\Sigma} \}$$ とすると、 $G=(V_{\alpha}\cup V_{\beta}, \Sigma, R_{\alpha}^{V}\cup R_{\alpha}^{(S_{\beta})}\cup R_{\beta}, S_{\alpha})$ は$\interpret{\alpha}\cdot\interpret{\beta}$ を生成する右線形文法である。

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

帰納法の仮定から $\interpret{\alpha}$, $\interpret{\beta}$ を生成する右線形文法がそれぞれ存在する。 $\interpret{\alpha}$ を生成する右線形文法を $G=(V_{\alpha}, \Sigma, R_{\alpha}, S_{\alpha})$、 $\interpret{\beta}$ を生成する右線形文法を $G=(V_{\beta}, \Sigma, R_{\beta}, S_{\beta})$ とおく (ただし、$V_{\alpha}\cap V_{\beta}=\emptyset$ とする)。

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

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

帰納法の仮定から $\interpret{\alpha}$ を生成する右線形文法がそれぞれ存在する。 $\interpret{\alpha}$ を生成する右線形文法を $G=(V, \Sigma, R, S)$ とする。

さて、 $$R^{(V)}=\{ A\mathgen \gamma \in R | \gamma \in \kleenecl{\Sigma}V \}$$ $$R^{(0)}=\{ A\mathgen \gamma \in R | \gamma \in \kleenecl{\Sigma} \}$$ とすると、$R=R^{(V)}\cup R^{(0)}$, $R^{(V)}\cap R^{(0)}=\emptyset$ である。

$$R^{(S)}:=\{ 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{\interpret{\alpha}}$ を生成する。

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

(1. $\Rightarrow$ 3.) $L$ が正規言語であるとき、補題 2から すべての生成規則の右辺が $(\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$ に対して以下の2条件は同値であることを示す。

(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}}\})$ とおく。

簡単のため、以下 $$\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\}$$ という略記を用いる。

正規表現 $\alpha^{(l)}_{ij}$ (ただし、$1\leq i, j \leq n$, $0\leq l \leq n$)を次のように帰納的に定める。 $$\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$)}.$$

$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.)は示された。 $\blacksquare$

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

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

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

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

$0^{n}1^{n}$ という形の記号列全体

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

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

背理法により示す。

$0^{n}1^{n}$ という形の記号列全体 $L$ が正規言語であると仮定する。 定理 1より、 $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}$ に受理される。
  4. $|xy|\leq n_{0}$。

このとき、 $xy=0^{k}$ (ただし、$0< k\leq n_{0}$) であることに注意する。 すると、 $x=0^{k_{0}}$, $y=0^{k_{1}}$ (ただし、$0\leq k_{0}\leq k$, $0< 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}<n_{0}$ であるから $xz\notin L$ である。 これは $L=L(\mathautomaton{A})$ に矛盾する。$\blacksquare$

$w\mirrorim{w}$ という形の記号列全体

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

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

背理法により示す。

$w\mirrorim{w}$ という形の記号列全体 $L$ が正規言語であると仮定する。 定理 1より、 $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}$ に受理される。
  4. $|xy|\leq n_{0}$。

このとき、 $xy=0^{k}$ (ただし、$0< k\leq n_{0}$) であることに注意する。 すると、 $x=0^{k_{0}}$, $y=0^{k_{1}}$ (ただし、$0\leq k_{0}\leq k$, $0< 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}<n_{0}$ であるから $xz\notin L$ である。 これは $L=L(\mathautomaton{A})$ に矛盾する。$\blacksquare$

正規言語と左線形文法

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

左線形文法

左線形文法(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$

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

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

定理 3

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

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

参考文献

  1. 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
  2. 五十嵐喜英他、『数理情報科学シリーズ 24 オートマトンと形式言語の基礎?』、牧野書店、2011

関連項目

Chomsky 階層

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


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2020-12-26 (土) 02:18:16 (26d)