問題タブ [dfa]

ご存知のように、DFA を使用して通常の言語で文字列を検証できます。

例 1. L=ac(b)*bcb|ad(b)*bb. 文字列「acbbbcb」は、DFA によって正しいと検証できます。

また、正規言語をCFGで表現できる場合もあります。

例 2。

• S -> "a" A "b"
• A -> "c" B "c" | "d" B
• B -> "b" B | 「ば」

上記の CFG によって生成される言語は、例 1 の正規表現にすぎません。

つまり、DFA を使用して、この CFG によって生成された (通常の) 文字列を検証できます。しかし、どうすれば対応する構文木を生成できるでしょうか?

私は現在、Haskell で実装したい 2 つのオートマトン学習アルゴリズムのニーズに適合するデータ構造を考え出そうとしています: RPNIとEDSM。

直観的には、ツリーに対するジッパーに近いものが理想的です。これらのアルゴリズムは、状態に対するある種の焦点 (ブルー フリンジ) を維持する状態マージ アルゴリズムであるため、興味深いポイントにすばやく到達するためにある種のジッパーが役立ちます。しかし、DFA (Determinist Finite Automaton) はツリーのような構造よりもグラフのような構造であるため、私はちょっと迷っています。遷移によって構造に戻ることができますが、ジッパーが正常に動作しない可能性があります。

私の質問は次のとおりです。高速な方法で操作できるように、DFA (または少なくともその遷移) をどのように表現しますか?

オートマトン理論の割り当てを行っています。これは、決定論的有限オートマトンの遷移関数によって単語が受け入れられるかどうかを判断する必要があります

私はこの入力ファイルを持っています:

入力は 4 つの整数で始まり、最初はオートマトンの状態の数、次はオートマトンの遷移の数、3 番目の数は初期状態、そして最終状態の数です。次に、最終状態が続きます (この例では、最終状態は 2 と 5 です)。

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

このプログラムの出力は次のようになります。

文字列が受け入れられたか拒否されたかを示す必要があります。これまでのところ、入力を使用して作業をコーディングしただけです。

オートマトンを表現するのに最も便利な方法がわかりません。単純に配列を使用する必要がありますか? 配列にどのようなロジックを適用しますか? オートマトンのアルファベットを事前に知らずにそれを行う方法はありますか? オートマトンを表現するためにデータ構造が必要ですか?. 私はこの割り当てに少し行き詰まっており、いくつかのアイデア、いくつかの疑似コード、またはそれを行うためのアイデアが欲しいです。コードは別の言語ですか？私は自分の課題をやりたいので、解決策を望んでいませんが、何か助けがあれば

if-elseアプローチとグラフアプローチを使用してDFAを実装できることは知っていますが、それらを実装する他の方法はありますか？実際、私は正規表現用のJavaCode Generatorを作成しています。これまで、2つの可能なアプローチ（if-elseとグラフアプローチ）を実行しましたが、より多くの可能な方法を提供したいと思います。トランジションのセットまたはマップとしていくつかのデータ構造を使用して実装できると思います。

この投稿に示されているように、状態遷移を格納しているマップを使用して、非決定性有限オートマトンをシミュレートするために数日間試みています。

問題は、非決定論的な遷移、つまり同じシンボルによって私を異なる状態に導く遷移が欠落していることです。これが私のコードです：

マップの内容全体を印刷すると、次のようになります。

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

私は何を間違っているのですか。別の質問では、非決定性有限オートマトンの遷移をシミュレートする最良の方法はマップを使用することですが、マップを使用することはこのタイプの問題に適切であるか、または何らかの方法で解決できると答えました。なぜこれらの値が失われるのですか？

マップ構造を変更すると便利ですか？すなわち：

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

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

単純な Perl インタープリターのように、正規表現を処理できる Unix 用の C プログラムを作成したいと考えています。個人的に正規表現エンジンを作成する必要がありますか?

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

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

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

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

私はリファクタリングして、似たような見た目のひどい Java クラスをたくさん維持しなければなりません。多くは次の実装パターンを持っています

そして、これからグラフを生成したいと思います（Graphvizとを使用dot）-「静的呼び出しグラフ」のようなものですが、正確ではありません。

Perl や Python を使って自分で Java コードを解析する以外に、これを自動的に行う方法を考えています。

私が本当にしたいのは、Abstract Syntax Tree (AST) か、ナビゲートできるクラスに似たものを用意し、その間にdot-code を出力することです。

• ここでトラバース可能な AST を生成するにはどうすればよいですか? その場合、トラバースはJavaで行われると思いますが、出力がテキスト表現であれば問題ありません（gprofここで思い浮かびます）。
• ASTを使用しない他のアプローチはありますか? 多分私は目が見えないだけで、より良い、より簡単な方法があります。