正規言語の連接

2つの正規言語 L₁, L₂ を考えます。その連接（連結ともいいます）L = L₁ ∘ L₂ も正規言語であることを証明します。

連接とは

2つの語「010」と「1111」を連接すると、語「0101111」ができます。言語の連接は、一方の言語のすべての語を、もう一方の言語のすべての語と連接してできる新しい言語です。語の連接も言語の連接も、丸の記号 ∘ で表します。すると、言語 L₁ と L₂ の連接は次のように定義できます。

$L_{1} \circ L_{2} = {a \circ b | a \in L_{1}, b \in L_{2}}$

証明の考え方

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

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{0}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, p_{0}, F_{2} ⟩ \end{array}$

非決定性オートマトン A = ⟨Q, Σ, δ, q, F⟩ をつくり、その中にオートマトン A₁ と A₂ の両方を「含める」ことにします。基本的な考え方は次のとおりです。まず語をオートマトン A₁ で読み始め、オートマトン A₁ が受理状態に達したら、語の残りの部分をさらにオートマトン A₂ で受理できるかを試します。このオートマトンも語の残りの部分を受理すれば、オートマトン A はその語を受理します。

例

0だけからなる空でない語と、1のあとに0だけが続く語（1、10、100、…）を受理する、次のオートマトン A₁ を考えます。

また、01で終わる語を受理する、次のオートマトン A₂ も考えます。

2つのオートマトンは次のようにつなぎます。オートマトン A₁ のすべての受理状態から、オートマトン A₂ の初期状態へ ε 遷移を加え、そのあと A₁ の受理状態を非受理状態にします。新しいオートマトン全体の初期状態は、オートマトン A₁ の初期状態です。

このオートマトンはどのように動くでしょうか。まず、オートマトン A₁ の動きをシミュレートします。もとの受理状態 q₁ または q₂ に移ったら、オートマトン A₁ がこの語の前の部分を受理したことがわかります。語全体が言語 L₁ ∘ L₂ に属するには、語の残りの部分を2つ目のオートマトン A₂ が受理しなければなりません。そのため、もとの受理状態のすべてから、オートマトン A₂ のもとの初期状態へ ε 遷移が出ています。

例として、語0001を考えます。この語は2つの言語の連接に属します。語の連接 00 ∘ 01 としてできるからです。また、語の連接 0 ∘ 001 としてもできます。このオートマトンでは、どちらの手順もシミュレートできます。オートマトンは次の道筋をたどることができます。

$q_{0} \to^{0} q_{1} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

この道筋では、オートマトンはまず語の一部00を「受理」し、次に語の一部01を「受理」します。また、次の道筋をたどることもできます。

$q_{0} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

この場合、オートマトンはまず語の一部0を「受理」し、次に語の一部001を「受理」します。どちらの場合も、もちろん受理状態 p₂ にたどり着きます。

手順の形式化

もう一度まとめます。2つの正規言語 L₁, L₂ と、これらの言語を受理する次の2つのオートマトンがあります。

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{0}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, p_{0}, F_{2} ⟩ \end{array}$

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

Q = Q₁ ∪ Q₂（ただし、Q₁ ∩ Q₂ = ∅ と仮定します）
Σ= Σ₁ ∪ Σ₂
q = q₀
F = F₂

遷移関数 δ は、場合に分けて次のように定めます。

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & q \in Q_{1} \land q \notin F_{1} & のとき \\ δ_{1} (q, a) & q \in F_{1} \land a \neq ε & のとき \\ δ_{1} (q, a) \cup {p_{0}} & q \in F_{1} \land a = ε & のとき \\ δ_{2} (q, a) & q \in Q_{2} & のとき \end{cases}$

参考文献

章: 正規言語の閉包性, 正規言語の和集合, 正規言語の共通部分, 正規言語の差集合, 正規言語の補集合, 正規言語の連接, 正規言語のクリーネ閉包

« 前へ: 正規言語の補集合

次へ: 正規言語のクリーネ閉包 »