正規言語のクリーネ閉包

正規言語 L を考えます。言語 L のクリーネ閉包もまた正規言語であることを証明します。

言語のクリーネ閉包とは

言語 L のクリーネ閉包は L^∗ で表します。クリーネ閉包は、言語 L の語を有限個連接してつくれるすべての語からなります。クリーネ閉包は次のように定義できます。

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in {\mathbb{N}}_0\}$$

ここで、∘ は連接の演算を表します。クリーネ閉包には空語 ϵ も含まれます。

手順の形式化

言語の連接の場合ととてもよく似た手順で進めます。ただし、2つの異なるオートマトンをつなぐのではなく、1つのオートマトンを自分自身につなぎます。つまり、オートマトンの受理状態から、同じオートマトンの初期状態へ ε 遷移を引きます。しかし、クリーネ閉包には空語も含まれなければなりません。どうすればよいでしょうか。初期状態を受理状態にすることも考えられます。そうするとオートマトンは空語を受理しますが、それ以外の余計な語まで受理してしまうおそれがあります。そこで、代わりに新しい初期状態をつくり、この新しい初期状態からもとの初期状態へ ε 遷移を引きます。

正規言語 L₁ と、この言語を受理する次のオートマトンがあります。

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

次の条件を満たす非決定性オートマトン A = ⟨Q, Σ, δ, q_s, F⟩ をつくります。

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

遷移関数 δ は次のように定義します。

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& q\in Q_1\wedge q\notin F_1& \text{のとき}\\ {\delta }_1(q,a)& q\in F_1\wedge a\ne ϵ& \text{のとき}\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& q\in F_1\wedge a=ϵ& \text{のとき}\\ \left\{q_0\right\}& q=q_s\wedge a=ϵ& \text{のとき}\\ \mathrm{\varnothing }& q=q_s\wedge a\ne ϵ& \text{のとき}\end{array}$$

例

語00または11を受理する、次のオートマトン A₁ を考えます。

言語 L(A₁) のクリーネ閉包は、00と11をいくつか並べてできるすべての語の言語です。例えば、0000、110011、11110000などです。このクリーネ閉包を受理するオートマトンは、次のようにつくります。新しい初期状態 q_s をつくってもとの初期状態 q₀ への ε 遷移を引き、さらに状態 q₃ と q₄ から状態 q₀ への ε 遷移を加えます。

このオートマトンが語0000、110011、11110000を確かに受理し、例えば語1010は受理しないことを確かめられます。

参考文献

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools