計算理論学習ノート - 正規言語と正規演算

---

この記事は「計算理論の基礎(共立出版)」の読書ノートです

---

ある有限オートマトンで認識される言語を正規言語という。正規言語に対して以下の演算が定義できる。

$${A, B}$$を正規言語とする。$${A, B}$$に対して$${A \cup B \equiv \{x: x\in A または x \in B\}}$$を和集合演算、$${A \circ B \equiv \{xy: x \in A, y \in B\}}$$を連結演算、$${A^* \equiv \{x_1x_2 \cdots x_k: k \ge 0, x_i \in A\}}$$をスター演算という。これら三つの演算を合わせて正規演算と呼ぶ。

正規演算

スター演算は$${k = 0}$$の場合も含むため、空文字列$${\varepsilon}$$は常にスター演算後の言語に含まれる。

ところで正規演算の結果が再び正規言語になるかどうか、すなわち認識する有限オートマトンが存在するかどうかは自明な事実ではない。しかし、実際には正規演算は正規言語の中で閉じている。このことを証明することが当面の目標となる。

まずは和集合演算について考えることにしよう。証明したい定理は以下だ。

$${A, B}$$を正規言語とする。$${A \cup B}$$は再び正規言語となる。

さて、今$${A}$$を認識する有限オートマトンを$${M_A}$$、$${B}$$を認識する有限オートマトンを$${M_B}$$とし、それぞれの定義を以下のようにする。

$$
M_A \equiv (Q_A, \Sigma_A, \delta_A, q_A, F_A),\ M_B \equiv (Q_B, \Sigma_B, \delta_B, q_B, F_B)
$$

ここから$${A \cup B}$$を認識する有限オートマトン$${M \equiv (Q,\Sigma, \delta, q, F)}$$を構成する。次のように定義しよう。

• $${Q \equiv Q_A \times Q_B = \{(r_A, r_B): r_A \in A, r_B \in B\}}$$

• $${\Sigma \equiv \Sigma_A \cup \Sigma_B}$$

• $${\delta((r_A, r_B), s) \equiv (\delta_A(r_A, s), \delta_B(r_B, s))}$$。ただし、$${s \notin \Sigma_A}$$のとき$${\delta((r_A, r_B), s) \equiv (r_A, \delta_B(r_B, s))}$$、$${s \notin \Sigma_B}$$のとき$${\delta((r_A, r_B), s) \equiv (\delta_A(r_A, s), r_B)}$$とする

• $${q\equiv (q_A, q_B)}$$

• $${F \equiv (F_A \times Q_B)\cup (Q_A \times F_B) = \{(r_A, r_B) \in Q_A \times Q_B: r_A \in F_A または r_B \in F_B\}}$$

このように定義すると、$${s \in A}$$である文字列が来た時、最後の状態はある$${f_A \in F_A}$$と$${r_B \in Q_B}$$が存在して、$${(f_A, r_B) \in F}$$となる。同様に$${s \in B}$$である文字列が来た時、最後の状態はある$${r_A \in Q_A}$$と$${f_B \in F_B}$$が存在して、$${(r_A, f_B) \in F}$$となる。このことから$${A\cup B}$$は$${M}$$の言語であるため、和集合演算は正規言語で閉じることになる。

次回は連結演算が同様に正規言語で閉じていることと、非決定性について議論することにする。