問題タブ [nfa]

C++ での Brzozowski アルゴリズムの実装に取り​​組んでいます。このアルゴリズムを理解するのに問題はありませんが、C++ で全体を記述する方法がわかりません。どのように機能するかはわかりますが、プログラミングのスキルはありません。

誰か助けてくれませんか？マトリックスを作成したり、マトリックスから情報を取得したりするなど、アドバイスが必要です。配列を行列に入れることは可能ですか。誰かがアルゴリズムのノードを逆にする方法を知っているかもしれませんし、C++ で Brzozowski アルゴリズムの断片を持っているかもしれません。

タイトルが示すように、DFA と NFA は正規表現とどのように関連していますか? DFA と NFA を学ぶことは、正規表現をよりよく理解するのに役立ちますか?

正規表現を対応する NFA に変換するために Python で使用できるモジュールはありますか、またはコードを最初から作成する必要がありますか (正規表現をインフィックスからポストフィックスに変換し、トンプソンのアルゴリズムを実装して対応する NFA を取得します)?

Python で遷移テーブルから NFA の状態図を取得することは可能ですか?

私のnfaにこの移行がある場合

アルファベット {a,b}

nfaが状態q1にあるときにbまたはaのいずれかが入力として読み取られると、q1からq2への遷移があるということですか? または、入力 a および b で q1 から q2 への遷移が定義されていません。

与えられたアルファベットを単語内のの出現回数として{a, b}定義し、同様にを定義します。次のセットオーバーが正則であることを示せ。Na(w)awNb(w){a, b}

A = {xy | Na(x) = Nb(y)}

この問題の解決をどこから開始すればよいかを理解するのに苦労しています。どんな情報でも大歓迎です。

L = w : (na(w) - nb(w)) mod 3 /= 0

この言語の正規表現を見つけるにはどうすればよいですか?

As の数から B の数を引いた値が 3 の倍数にならないということは理解しています。つまり、a - b は 3、6、9、12 などにはなりません

しかし、私はまだそれを正規表現に入れるのに苦労しています。最初にDFAかNFAにしてみましたが、それもできませんでした。

どんな助けでも大歓迎です！

入力に正規表現または文字列があり、それを NFA に変換してから DFA に変換し、対応する最終 DFA の遷移表を実際に出力するアルゴリズムを探していました。

したがって、それを行うアルゴリズムまたは C または Python ライブラリが既に存在するかどうか、または使用するアルゴリズムの提案があれば、それを実装できるかどうか疑問に思っています。

ありがとうございました。

このウェブサイトで同じ質問を見つけました。その答えは、NFA を正規表現に変換する方法を説明した PDFでした。ただし、この方法にはいくつかの条件があるため、これは機能しません。

1. 初期状態から他のすべての状態への遷移があり、初期状態への遷移はありません。
2. 入ってくる遷移のみを持つ (出て行く遷移がない) 単一の受け入れ状態があります。
3. 受け入れ状態は、初期状態とは異なります。
4. 初期状態と受け入れ状態を除いて、他のすべての状態は遷移を介して他のすべての状態に接続されます。特に、各状態にはそれ自体への遷移があります。

そして、私の例では、開始状態は次の状態に行くだけで、すべての状態に行くわけではなく (たとえば、q0 は q1 に行くが、q2、q3 には行かない)、開始状態への遷移があります。

では、NFA を正規表現に変換する最も簡単な方法は何でしょうか? 開始状態がすべての状態に接続されていないこの種の DFA に出くわしたため、具体的なものがないため、NFA の例を挙げていません。これは一般的な質問です。開始状態。

この種の NFA を変換する一般的なアルゴリズムが必要です。