🤖
NFAを用いてスター演算の状態遷移図を作る構築法について

2026/01/01に公開
非決定的有限オートマトン（以下NFA）を導入することで、正規言語（ここでは決定的有限オートマトンによって認識される言語と定義しています。）がスター演算に閉じていることを簡潔に証明できます。その際の構築方法として有名なものは、計算理論の基礎 1.オートマトンと言語(共立出版)に載っている以下のような方法だと思います。
ここでは、以下のNFAが認識する言語にスター演算を作用させたものを考えます。

具体的に状態遷移図が構築できて、

が所望の状態遷移図になります。

方法としては、開始状態となるようなものを新たに追加（ q_0 ）し、それを受理状態とします。

q_0 から元々のNFAの開始状態へ \varepsilon の辺をはります。最後に任意の元のNFAの受理状態から元のNFAの開始状態へ \varepsilon の辺をはります。
よくある間違いとして、以下の図のようにしてしまうことだと思います。

開始状態を受理状態にして、受理状態から開始状態へ \varepsilon の辺をはることです。
これがスター演算にならないようなケースを探しているといくつかの事実に気づいたので、それを記事にまとめておきます。証明に誤りなどがあれば、コメントやTwitter(@_chiaoi)まで教えてください。基本的には証明をきちんとは書きません。アイデアのみを記載しておきます。

 定義まずは、証明の中で使用する定義をしていきます。

 非決定有限オートマトン非決定性有限オートマトンは、 5 個組 (Q, \Sigma, \delta, q_0, F) です。

Q は状態の有限集合

\Sigma は有限のアルファベット

\delta: Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q) は遷移関数

q_0 \in Q は開始状態

F \subset Q は受理状態の集合

 スター演算言語 A のスター演算 A^* は、 A^* = \lbrace x_1 x_2 \dots x_k \mid k \ge 0 \land (\forall x_i, x_i \in A) \rbrace と定義されます。

 タスー演算（造語です）言語 A のタスー演算 A^- は、以下のNFAによって認識される言語です。まず、 A を認識する非決定有限オートマトンを M = (Q, \Sigma, \delta, q_0, F) とします。

\delta^-: Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q) を q \in Q, \sigma \in \Sigma_{\varepsilon} に対して、

\delta^-(q, \sigma) = \begin{cases}
  \delta(q, \sigma) \cup \lbrace q_0 \rbrace & q \in F, \sigma = \varepsilon \\
  \delta(q, \sigma) & \text{otherwise}
\end{cases}
と定義します。

M^- = (Q, \Sigma, \delta^-, q_0, F \cup \lbrace q_0 \rbrace) が認識する言語を A^- とします。これは、上の間違いの図になるような操作をすることを意味します。

 気づいた命題
 命題1：開始状態に戻るような辺が存在しない場合はスター演算とタスー演算の結果は等しい\forall q \in Q, \forall \sigma \in \Sigma_{\varepsilon}, q_0 \notin \delta(q, \sigma) のとき、 A^- = A^* が成り立ちます。

 説明状態遷移図を用いて考えるとわかりやすいです。ここでは上の図にある変数などを使用して説明します。

スター演算をした際の開始状態 q_0 から元の開始状態 q_1 に対する \varepsilon の辺は、 q_1 に入る辺がないときに縮約（ q_0, q_1 をまとめる操作）ができます。なぜなら、 q_1 に入るような辺が q_0 しかないので q_1 を受理状態にしてしまっても、 q_0 が受理状態であることより元と同じ言語を認識するからです。

 命題2：命題1の条件は受理状態から開始状態に戻る辺を無視できる\forall q \in Q - F, \forall \sigma \in \Sigma_{\varepsilon}, q_0 \notin \delta(q, \sigma) のとき、 A^- = A^* が成り立ちます。

 説明状態遷移図を用いて考えるとわかりやすいです。ここでは上の図にある変数などを使用して説明します。

命題1が正しいとします。追加する辺として、 \lbrace q \to q_1 \mid q \in F \rbrace があります。これが元からあっても縮約ができます。つまり、タスー演算で追加される \varepsilon 辺と、スター演算で追加される \varepsilon 辺は、 q_0 から q_1 への \varepsilon 辺で繋がっているため、認識する言語に直接影響しません。

 命題3：命題1の条件は使わない辺に関しては無視できるこれは、ほとんど自明です。使わない辺によって、言語が変わることはありません。

 予想4：命題1の条件を強めすぎると成り立たないさて、命題3の条件をさらに強めると、「 \forall w \in A に対して q_1, \dots, q_k が存在して開始状態に戻るような辺を一度も使わないような表現方法が存在する」となります。

同じ文字列に対して 2 つの受理するような表現がある場合にそのような表現の途中部分が邪魔をする可能性があります。つまり成り立たないと思います。反例の構築は気が向いたらやります。

 考え中なことこれらを考えている中で縮約という表現をしました。これはある性質の良い同値類が存在していることを表していそうです。例えば、認識する言語が等しいようなオートマトンの同値類を考えることができます。NFAにおいてそのような縮約表現のうち、最も良いものが存在するのかを考えています。
使用する状態の数が最も少ない
使用する辺の数が最も少ない

など良さの基準はたくさんあると思いますが、それらを形式的に得る方法が難しそうです。
また、このような条件が成り立つクラス（ A^* = A^- が成り立つクラス）を考えることに意味があるのかも考えています。調べてみた限りだと名前はなさそうで、状態が一つ省略できるだけなので実用的な嬉しさはなさそうに感じました。
正規表現をNFAとして表現する際も、なるべく簡単なものを書こうとすると正規表現の表す意味自体を考察して書くのが個人的には良さそうだと思いました。機械的な方法だとかなり無駄な状態（無駄とは？）があり、直接見づらいです。NFAを簡単に表現する研究自体は進められており、最悪ケースがPSPACE完全であることも知られています。ここ最近の研究を調べてみるとIncremental NFA minimizationやIncremental NFA Minimizationなどが見つかりました。具体的な構成方法のアルゴリズムですね。

 終わりに非決定性有限オートマトンのスター演算を考えていて思ったことをまとめました。まとめると、ある程度の条件を満たせば間違った構成でも正しい言語を認識します。

かなり昔に作られた概念ですが、現在のアルゴリズムの研究などがされており、面白い分野だなと思いました。さらに面白い議論や論文などがあれば教えていただけるとありがたいです。