問題タブ [nfa]

この質問をするのが正しいかどうかはわかりませんが、確かに尋ねるべきだと感じました。もちろん、私は多くの素晴らしく有益な質問、インターネット上の記事、および StackOverflow 自体に関する記事を見ました。しかし、トピックを説明する特定のルールまたはパターンに従っているすべての質問または記事を見つけました。つまり、NFA、DFA、または正規表現について質問された場合、これらのトピックの定理/規則 (計算の理論) に従って、質問に対する解決策が提示されました。

そしてアートがあるところには直感があると感じています。これらの問題に何かを「設計」することが含まれている場合、誰もがこれらの問題を解決または攻撃する独自の方法を持っている必要があります (もちろん、定理や規則自体から外れることはありません)。これらの問題を解決するための思考プロセスを (長年の実践を通じて) 開発する必要があります。

簡単な例で質問を詳しく説明したいと思います。

問題を考えてみましょう:

また

（質問はSipserの本からのもので、私自身も解決策を見つけました）

問題を解決するための直感を開発する方法を知りたいだけです。

十分な理論的知識を持っていても、これらの問題を解決する際に困難に直面しているすべての初心者 (私のような) のスキルと思考プロセスを開発することを考慮して、この質問をしています。

「建設的な」回答は大歓迎です!! ありがとうございました。

Regex: NFA and Thompson's algorithmなどの投稿を読むと、実際には "7" や "b" などの直接文字だけでなく、

つまり、文字クラス (または範囲) です。したがって、私の質問 - 文字範囲を使用して NFA を構築する方法は? 「not A」、「何か他のもの」などのメタ文字を使用してから、重複する範囲を計算しますか? これにより、最終オートマトンを使用するときに、単なるテーブルではなく、ツリーのような構造を使用することになります。

更新:自明でないサイズ (>>256) のアルファベットを想定してください。

NFAについて質問していますが、後でNFAもDFAに変換したいと思っています。

私は、特定の言語の正規表現をアルファベットで書くことに行き詰まっています{a,b}。文字列は、部分文字列「aa」で始まるか、部分文字列「bb」で終わる場合に受け入れられます。

たとえば{aab, abb, aaba}、受け入れられますが、受け入れられ{Λ, ab, abaa}ません。

私の試みた解決策は次のとおり{aa* + ab* + bb*}ですが、私は考えていました: 文字列がb? そしたら表情がまとまらない…

どんな助けでも素晴らしいでしょう！

ちょっとした背景: 私は正規表現マッチング エンジン (NFA) を実装しており、PCRE 互換モードをサポートする必要があります (つまり、PCRE と同じオフセットで部分式をキャプチャする必要があります)。

PCRE の testinput1 には、完全には理解できないテストがあります。遅延量指定子をテストします。

したがって、正規表現は

そして文字列は

PCRE の試合は次のとおりです。

明らかに遅延量指定子を使用しています。

私が理解している限り、別の「貪欲な」方法がまったく不可能になるまで、遅延量指定子を使用しないでください。ここで可能な貪欲な一致は次のとおりです。

条件付きサブパターンの負の分岐を使用し、遅延量指定子は使用しません。

したがって、この PCRE の動作の説明、または遅延量指定子がこのテストで一致する理由の詳細/提案を探しています。ありがとう！

EDIT ： TREライブラリの仕組みも調べました。POSIX 互換の NFA エンジンです。TRE の構文に合わせて元の正規表現を少し変更しました。

出力 (終了オフセットの代わりに長さを使用) は次のとおりです。

したがって、PCRE のバックトラッキング固有の動作に関する提案は、おそらく間違っています...

正規表現についてかなり基本的な質問があります。行末までマッチするなどと考えず
に表現を使っています。.*これは機能します。
しかし、なぜかこの表現について考えるようになりました。ウィキペディアをチェックする (私の強調)

では、この定義によれば、が文字列の最初の文字を 0 回以上一致させよ.*うとせず、代わりに文字列の各文字に一致を適用しようとするのはなぜでしょうか? 私が持っているなら、それを正しく一致させようとする必要がありますか？ しかし、それはしません:
abca,aa,aaa etc

DFA では、2 つのオートマトンの状態の外積を計算し、両方の初期オートマトンで受け入れている状態を受け入れることで、2 つのオートマトンの交差を行うことができます。合体も同様に行う。イプシロン遷移を使用してNFAで簡単にユニオンを実行できますが、どのように交差を行うのですか?

NFA を正規表現に変換する方法がわかりません。開始状態が最終状態でもある NFA があり、何をすべきかわかりません。これは私のNFAがどのように見えるかです:

ここのようにオンラインで見つけたガイドラインに従おうとしました： http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf

この Web サイトの手順に従って、この NFA を次のように分割しました。

ここから、もう少し詳しく説明します (これはステップ 4 に対応すると思います)。

この時点で、どのように進めればよいのかよくわかりません。クラスでは GNFA についてまったく話さなかったので、この時点で特に迷っています。この時点からどのように進めるべきかについての指針はありますか?

ここに表示されているのは、「少なくとも 1 つの 01 の後に 0 個以上の 0 または 1 が続く」ということです。

私はこれを単純化しすぎているのでしょうか、それとも、表現が描かれた機械よりもはるかに複雑に見えることに偏執的であるだけですか?