問題タブ [nfa]

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

ありがとう。

^入力アンカー（ ）の先頭がフレックスでFSAにどのように変換されるのか常に疑問に思っていました。行末アンカー（$）は、一致する式r/\nである式と一致することを知っていrます。入力アンカーの先頭はどのように一致していますか？私が見る唯一の解決策は、開始条件を使用することです。プログラムにどのように実装できますか？

正規表現を表す文字列を受け入れるプログラムを作成しようとしています。例えば：

U はユニオン演算子で、* は Kleene スターです (暗黙の連結も見られます)。

文字列のアトムをトークン化し、演算子とオペランドに基づいてマシンを構築することを検討しました。これに似たルールで各アトムをアルゴリズム的に操作したかった: http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

このタイプの入力をインテリジェントな方法で解析して、プログラムで NFA を構築できるようにする方法がわかりません。

私のプログラムの目標は、上記の入力を取り込んで、対応する NFA を出力することです。その目標を達成するためのアドバイスは大歓迎です。

私はPrologの初心者ですが、Prologについて質問したいと思います。

私のプログラムは、非決定論的有限状態オートマトンに基づいています。

開始状態はS0で、最終状態はS3です。

図は

したがって、文字列がある場合は、次の[a,a,b,b,c,c]ようになります。

（文字列のリストがある）accepts(Ls)場合の述語がありますLs

NFAが状態Siから状態Sjに移行し、その間に状態Skがあると仮定すると、goesTo述語は次のように定義されます。

しかし、クエリ（からまでaccepts(Ls)の範囲の文字列の任意のリスト）を実行すると、チュートリアルの質問は、ほぼ確実に無限の検索に入り、スタックオーバーフローが発生することを示しています。ac

ただし、クエリが無限検索になり、スタックオーバーフローが発生する理由がわかりません。理由を教えていただければ、本当に素晴らしいです！

（編集:)正確な見積もりは次のとおりです。

「典型的なPrologユーザーは、自分のgoesToルールが、クエリaccepts（X）が上記のNFAによって受け入れられる連続した文字列を生成するようなものになることを期待するかもしれません。ほぼ確実に、特定のNFAの上記のプレゼンテーションを考えると、Prologシステムは無限の検索に入り、スタックオーバーフローが発生します。なぜそうなのかを説明してください（この問題を回避するには、どうやって回避したかを説明してください）。」

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

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

要件：

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

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

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

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

見つけた：

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

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

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

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

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

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

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

DFA与えられたのと同じ言語を受け入れる、最小を描画するための直接的で簡単なアプローチは何ですかRegular Expression(RE)。
私はそれができることを知っています：

しかし、近道はありますか？のように(a+b)*ab

私は明日の試験のために勉強していて、NFA を Regex に変換する方法を説明する多くのチュートリアルをチェックしましたが、自分の答えを確認できないようです。チュートリアルに従って、そのNFAを解決しました

私の解決策は次のとおりです。

あば_

私は正しいですか？

反復補題を使用すると、その言語が正規言語L1 = {WcW^R|W ∈ {a,b}*}ではないことを簡単に証明できます。（アルファベットは{a、b、c}です。W^ Rは逆文字列Wを表します）

ただし、文字cを"x"(x ∈ {a,b}+)たとえば、に置き換えるとL2 = {WxW^R| x, W ∈ {a,b}^+}、L2は正規言語になります。

アイデアをいただけますか？

ご存知のように、反復補題を使用すると、言語L = {WW |W∈{a、b}*}が正規言語ではないことを簡単に証明できます。

ただし、言語、L1 = {W1W2 | | W1 | = |W2|}は正規言語です。以下のようにDFAを取得できるため、

私の質問は、L = {WW |W∈{a、b} *}も文字列の長さが偶数であり（| w | = | w |、間違いなく）、Lは上記のようなdfaを持つことができます。なぜそれは正規言語ではないのですか？

ありがとう。