問題タブ [nfa]

この投稿で説明するように、非決定性有限オートマトンをシミュレートするための割り当てを行っています。この入力をファイルから読み取らせますtarea4.in：

入力の最初の行は整数Tで、プログラムを評価するケースの数を表します。各テストケースは4つの整数で始まり、最初はオートマトンの状態の数、次はオートマトンの遷移の数、3番目の数は初期状態、そして最後の状態の数です。次に、最終状態が発生します（この例では、最終状態は2と5です）。次に、Eが最終状態であることを表す整数Eを持つF行が来ます。

次に、N行（Nは遷移の数）が来ます。それぞれ2つの整数と、遷移、つまり遷移が状態iから状態Jに文字Cで進む状態を表す文字I、J、およびCがあります。この行の後には、テストする文字列の数を含む単一の整数Sが続き、次にそれぞれの文字列を含むS行が続きます。

期待される出力は次のとおりです。

私のコードに帰着する出力：

これが私のコードです：

私の質問は：なぜ私は間違った出力を得るのですか？テストケースで定義されたオートマトンの非決定性のためだと思いますが、文字列を正しく評価するにはどうすればよいですか？呼び出された関数evaluate_stringを何らかの方法で変更して、非決定論によって文字列を評価するためにオートマトンを使用できるさまざまなパスを確認するにはどうすればよいですか？

私はこれに数日間立ち往生していて、正直に言うと私はやや必死です。

数日間、非決定性有限オートマトン (NFA)、より具体的には文字列認識機能をシミュレートするプログラムを作成しようとしています。何度か失敗した後、ユーザーKonrad Rudolphのおかげで、次の疑似コードに基づいたソリューションを実装できました。

NFA では、現在の状態のセットがあり、各ステップで現在のすべての状態を調べ、それぞれについて、すべての有効な遷移を選択します。これらの結合されたセットは、新しい状態セットを形成します。

最後に、現在の状態と受け入れ状態の交差が空でないかどうかを確認します。

擬似コードでは、これは次のようになります。

これは、1 行ずつ C++ コードに変換できます。彼はこれを簡単にすることを勧めました。std::set<int> for the current and next sets

C ++での私の実装は次のとおりです。

私はこの入力を持っています：

予想される出力は次のとおりです。

ただし、私のコードは出力として生成されます。

テスト ケースの最後の文字列では、プログラムは何もせず、実行を停止しません。私の質問は、この特定の入力でプログラムがクラッシュするのはなぜですか。JFlapで同じオートマトン NFA を設計し、この最後の入力を認識します

あくどどど

.

コードの実装でどのような間違いがありますか?

特定の正規表現のセットを単一の NFA に変換していますが、いくつか問題があります。「ab.*c」(「a」、「b」、任意の数の文字、および「c」の一致を表す) などの正規表現を変換するにはどうすればよいですか?

私の最終的な目標は、単一の NFA を DFA に変換することです (そのためにサブセット構築アルゴリズムを使用しています)。

nfa から dfa に変換すると、下の画像のような結果になる場合があります...私の質問は、状態 {4} からゼロ状態になることを記述する必要があるかどうかです。{4} の入力記号 1 を表示しないと、右下の図と同じですか? それともいいえ？

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

Javaのオートマトンに対して次の操作を実装する必要があります。

• 連結
• クリーネ閉包
• 連合
• 交差点

オートマトンがNFAの場合、これらの操作は簡単です。次のリンクにある実装が気に入りました。このデータを介した有限決定性オートマトンのモデリングですが、キーの一意性の制限のため、NFAのモデリングには適していないと思います。NFAをモデル化するための回避策を教えてください。

DFAの最小化について質問があります。そのため、私は非常によく知られた手法を使用して正規表現をNFAに変換し、goto/closureアルゴリズムを使用してそれからDFAを構築しました。ここで問題は、どうすればそれを最小化できるかということです。私はここでそれについての講義を見てきました：http ：//www.youtube.com/watch？v = T9Z66NF5YRk 、そして私はまだポイントを得ることができません。DFA最小化とは何ですか？これは、IDENTICAL状態（同じ文字で同じ状態になる状態）をマージするだけですか、それとも別の状態ですか？

それで、私は次の文法から始めました：

最終的に次のDFA（JSONとして表される）になります。

では、どうすれば最小化できますか？

アップデート：

さて、これが私のアルゴリズムです。次のDFAが与えられます：

これは私がそれを最小化するために行うことです：

1. 各状態（私の例では0、1、2、3、4として番号が付けられています）について、そのような状態を識別する一意のハッシュを取得します（たとえば、state0の場合、これはfrom = 97、to = 97、shift = 1、state1の場合はthis from = 97、to = 97、shift = 3＆from = 98、to = 98、shift = 2などになります…）

2. 得られたハッシュを比較し、2つの同一のハッシュが見つかった場合は、それをマージします。私の例では、state2ハッシュはfrom = 98＆shift = 4＆to = 98になり、state4ハッシュはfrom = 98＆shift = 4＆to = 98になります。これらは同じなので、新しいstate5にマージできます。その後、DFAはこんな風に見える：

   }

3. 変更がなくなるまでこれを続けます。次のステップ（状態1と3をマージ）はDFAを次の形式に変換します。

   }

4. 同一の状態はもうありません。つまり、完了です。

2回目の更新：

さて、次の正規表現が与えられます：'a'（'ce'）*（'d' |'xa' |'AFe'）+ | 'b'（'ce'）*（'d' |'xa' |'AFe'）+'ce' +次のDFAがあります（START->開始状態、["accept"]-> so to受け入れ状態への移行と言います）：

話は同じですが、どうすれば最小化できますか？古典的なHopcroftのアルゴリズムに従って、このすべてのテーブル構造を使用し、区別できない状態を判別し、それらをマージするなどの場合、15の状態を含むDFAを取得します（このツールを使用してください：http：//regexvisualizer.apphb.com/この正規表現a（ce）（d | xa | AFe）+ | b（ce）（d | xa | AFe）+ ce +を使用して確認します）。Hopcroftのアルゴリズムを使用して縮小した後のDFAは次のようになります。

私が思いついたアルゴリズムは、Hopcroftのアルゴリズムを「再考」した後、上に表示されているものよりも小さいDFAを構築します（画質については申し訳ありませんが、なぜ小さいのかを理解するために段階的に再描画する必要がありました）。

そして、これがどのように機能するかです。「状態の同等性」に関する決定は、状態が与えられたハッシュ関数の結果に基づいています（たとえば、「START」）。その状態から開始すると、DFAから構築できる短い文字列が作成されます。 。上記のDFAとSTART状態が与えられると、次の文字列を作成できます：98-> 120、98-> 100、98-> 65、98-> 99、97-> 120、97-> 100、97-> 65 、97-> 99なので、START状態のハッシュ関数の結果とします。DFAの各状態に対してこの関数を実行すると、一部の状態でこの関数が同じ結果（ "1.2"、 "6.7"、 "2.3" AND "10"、 "13" AND"15"を与えることがわかります。 、"16" AND "11"、 "8"、 "26"、 "23" AND "12"、 "9"、 "4"、

どこかで間違っていることがわかりますが、アルゴリズムによって生成された最小化されたDFAの何が問題になっているのかわかりませんか？

いくつかの特定の条件でL（D）= L（N）となるようにDFAAとNFABを作成するように求められます。私は解決策や答えを求めているのではありません。この問題を攻撃するための正しい方法があることを確認したかっただけです。

まず、「ビルド」という言葉に少し混乱しています。彼らはオートマトンを描きたいだけですか？それは「構築された」と見なされますか？

その条件に合ったNFABを描くことを考えています。次に、図面を使用して、同等のDFAAを作成します。同等のオートマトンが同じ言語を持っているという定理がどこかにあります。したがって、L（A）= L（B）を正しく表示するために、これ以上何もする必要はありませんか？

ありがとう！

私は過去の試験を通過していて、教科書やグーグルで答えが見つからない質問に出くわしているので、助けていただければ幸いです。

私が現在問題を抱えている質問は次のとおりです。

正規表現（a | bb）*が与えられた場合、対応するNFAおよびDFAに変換するための時間内のコストの見積もりを導き出します。あなたの答えは正規表現のサイズを参照する必要があります。

別の年からの同様の質問は次のとおりです。

上記の例では、元の正規表現のサイズ|r|がわかっていると仮定します。入力文字列|x|のサイズは、同等のDFAを構築して実行するのではなく、NFAを構築して実行するための時間内のコストを計算する方法を説明します。

（a | bb）*の結果のNFAには9つの状態があり、DFAには4つの状態があります。これを知っていても、質問にどのようにアプローチするかわかりません。