nfa - REをNFAに変換する

Question

REユニオン0+1を表示する正しい方法はどれですか？私はこれを2つの方法で見ましたが、どちらも正しいと思います。両方が正しい場合、なぜ物事を複雑にするのですか？

Answer 1

あなたが言ったように、どちらも正しいです。

最初のものは、一連の標準ルールを使用して生成されたように見えます。この場合、やり過ぎです (そして、ばかげているように見えます)。しかし、より複雑なケースでは、すべてを頭の中で保持するよりも簡単なルールに従う方が簡単です。同等の NFA をゼロから作成します。

一般に、NFA は 1 つの最終状態を持つように書き換えることができます (明らかに、開始状態は 1 つしかありません)。

次に、この形式の 2 つの NFA を、組み合わせたときに受け入れる言語が、個別に受け入れる言語の和集合になるように組み合わせることができます。これ+は、正規表現の or ( ) に対応します。このように NFA を組み合わせるには、開始状態として機能する新しいノードを作成し、2 つの NFA の開始状態への ε 遷移で接続するだけです。

次に、単一の最終状態で NFA をきちんと終了するために (必要に応じて、この NFA を他の共用体に再帰的に使用できるようにするため)、統合された最終状態として機能する追加のノードを作成し、古い最終状態を ε 接続します。状態 (最終的なステータスを失う) をそれに追加します。

上記の一般的なルールを使用すると、最初の図 (2 つの NFA を結合したもの、最初の一致0、もう一方の1) にたどり着くのは簡単です。

Answer 2

最初のコンストラクトは、一般的な NFA クラスの拡張である e-moves を使用した NFA のクラスに属します。e-moves を使用すると、入力を必要とせずにトランジションを行うことができます。遷移関数の場合、e-transitions のみを使用して、特定の状態から到達可能な状態のセットを計算することが重要です。明らかに、e-moves を追加しても、NFA は非正規言語を受け入れることができないため、NFA と最終的には DFA と同等です。

e-moves を使用した NFA は、トンプソンの構築アルゴリズムによって使用され、任意の正規表現からオートマトンを構築します。構築を自動化すると便利な場合に、正規表現からオートマトンを構築する標準的な方法を提供します。