問題タブ [dfa]

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の何が問題になっているのかわかりませんか？

文法のコメント ブロックに問題があります。構文は問題ありませんが、ステップ 3 DFA スキャナーは、私が行っている方法について不平を言っています。

解析しようとしている言語は次のようになります。

{ステートメント}{ステートメント} など

各ステートメント内には、いくつかの異なるタイプのコメントを含めることができます。

これは、私が直面している問題を表示する単純化された文法です。

ステップ 3 は、<Statements> の } と字句グループの End の } について不平を言っています。

必要なことを達成する方法を知っている人はいますか?

[編集]
REM 部分を次のように動作させました。

Remarks は私にとって必ずしもノイズではないので、これは実際には理想的です。

コメント字句グループにはまだ問題があります。同じように解いていきます。

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

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

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

ありがとう！

DFAを生成できるプログラムを作成しました。しかし、DFAはわずかに正しくありません。つまり、正しい文字列を受け入れられない場合があります。

私の質問は、DFAを修正して、指定された正しい文字列を受け入れることができるアルゴリズムはありますか？

より正式には、

DFADが文字列strを受け入れないとします。

アルゴリズムが必要A、st D'= A（D、str）およびD'はstrを受け入れます

タイトルが示すように、NFAからDFAへの変換のコーディングを誰かに手伝ってもらいたいです。擬似コードのみが必要です。Googleを使用して検索してみましたが、ソースコード全体も見つかりましたが、変換のための形式手法（画像ではなく、書面による）を提供するのに役立つリソースはほとんどありませんでした。これは宿題の問題で、私はすでに期日を過ぎているので、ここで利他主義が本当に必要です。

ありがとう。

質問：

5 つの連続する位置のすべてのブロックに少なくとも 2 つの 0 が含まれるように、{0,1} を超えるすべての文字列を受け入れる DFA を定義します。質問をよく読んでください。これにより、e (イプシロン (空の文字列)) を受け入れることができるでしょうか? 0101はどうですか？このような英語の説明はさまざまな本に見られるので、読み方と解釈方法を知っておいてもらいたいと思います。

講師へのヒント: 「「5 ブロック」の DFA は、プログラムで問題なく生成できます。私は両方の方法で (手動とプログラムで) 作成しました。私は Emacs とキーボード マクロが得意なので、「手動」でも作成できました' 機械的かつ非常に高速ですが、プログラムはエラーが発生しにくく、コンパクトです。"

私はこのことを描いていますが、制御不能になっているので、間違っていると思います。

Pythonで作成する前のDFAのスケッチ：

ただし、インデックス 2、3、4、5、および 6 は 5 つの連続した位置のブロックを構成するため、これは正しくありません。そのため、少なくとも 2 つのゼロを考慮する必要があります。2 つの 0 ではなく 2 つの 1 が必要だと思っていました。私はこれを完全に間違った方法で行っていますか? 私が考えているように、これには膨大な量の状態があるからです。

(この大きな DFA の描画に戻ります)

同上。Java または C# が最適ですが、命令型言語であれば何でも構いません。

データ ストリームで動作する正規表現マッチングの実装を探しています。つまり、ユーザーが一度に 1 文字ずつ渡して、文字ストリームで一致が見つかったときにレポートできる API を備えています。これまでに見た。非常に基本的な (古典的な) 正規表現のみが必要なので、DFA/NFA ベースの実装が問題に適しているようです。

単一の線形スイープで DFA/NFA を使用して正規表現マッチングを実行できるという事実に基づいて、ストリーミングの実装が可能であるように思われます。

要件：

• ライブラリは、一致を実行する前に文字列全体が読み取られるまで待機しようとすべきではありません。私が実際に持っているデータはストリーミングです。どのくらいのデータが到着するかを知る方法はありません。前方または後方にシークすることはできません。

• ユーザーがどのようなパターンを探しているかは事前にわからないため、いくつかの特殊なケースに特定のストリーム マッチングを実装することはできません。

• 言語: C/C++から使用可能

興味深いことに、私の使用例は次のとおりです。完全なシステム エミュレータ内でメモリ書き込みをインターセプトするシステムがあり、正規表現に一致するメモリ書き込みを識別する方法が必要です (たとえば、これを使用してURL がメモリに書き込まれるシステム内のポイントを見つけます)。

見つけた：

ストリームに正規表現を適用しますか?

Java I/O ストリームへの正規表現の適用

Code Guru - .NET Framework を使用した正規表現ストリーム検索の構築

ただし、これらはすべて、最初にストリームを文字列に変換してから、標準の正規表現ライブラリを使用しようとします。

もう 1 つの考えは、RE2 ライブラリを変更することでしたが、著者によると、文字列全体が同時にメモリ内にあるという前提に基づいて設計されています。

何も利用できない場合は、自分のニーズに合わせてこの車輪を再発明するという不幸な道を歩み始めることができますが、それを避けることができれば、本当にしたくありません. どんな助けでも大歓迎です！

「hello」、「hello world」、「staytogether」という単語を受け入れるnfaの設計に支援が必要です。アルファベットには、英語のアルファベット、数字、記号が含まれています。始めるのに助けが必要です。誰か提案がありますか？

例：以下のシンボルシーケンスが与えられた場合、

それを受け入れることができる最も単純なDFAは、17の状態のチェーンです。

以下の正規表現は上記のシーケンスを導き出すことができますが、

また、対応する最小DFAには8つの状態があります。

さらに、正規表現a ((b c)* (d)*)* eには、4つの状態を持つさらに小さい最小DFAがあります。そして、それはサンプルシーケンスを受け入れることができます。

上記の例では、*演算子のみを考慮しています。より一般的には、オペレーター|はDFAサイズを縮小することも考えられます。

したがって、一般的な質問は次のとおりです。

一連のシンボルが与えられた場合、それを受け入れることができる最小のDFAを見つける方法は？