問題タブ [dfa]

一連のルールを決定論的有限オートマトンに変換するツールまたはソフトウェアを探しています。実際、英語用のポーター ステマーのようなステマーを開発しています。語幹を離れる用語から接尾辞や接頭辞を削除する一連のルールがあります。このルールを手動で DFA に変換することはできますが、これはその場しのぎの解決策であり、柔軟性の問題が生じます。

どんな助けでも感謝します。

ありがとう！

Context Free Grammar 用の LR(0) DFA の作成について助けが必要です。

これは私が持っているものです:

州

次に、次のラベルの付いた矢印がありaます。

州

そして、この状態から、次のラベルが付いた矢印a:

州：

これが私の問題の始まりです。ご覧のとおりB、この状態からラベルが付けられた 2 つの矢印が表示されます。

私は何を間違えましたか？

私はいくつかの研究プロジェクトのために決定論的有限オートマトンの実装を書いていますが、同じ状態につながるアークがいくつかあります。私は State に対してこのクラスを書きましたが、なぜコードが Stackoverflow を生成するのか不思議です:

驚いたことに、「addTransition」呼び出しの 1 つを削除してもエラーは発生しません。

Java のバージョンは JDK 1.6.37、オペレーティング システムは Ubuntu Linux 12.04 です。

* UPD: *スタック トレースは次のとおりです。

コメントはありますか？

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

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

私は DFA を持っていますが、州を受け入れているかどうかわかりません。私はそれが受け入れる正規表現しか知りません。状態を受け入れているかどうかを調べようとしているので、DFA の各状態を調べて、受け入れている正規表現と現在の状態によって生成された単語を比較したいと思います。

そのため、単語を正規表現と比較して一致するかどうかを教えてくれるものを探しているので、DFA のこの状態を承認済みの状態としてマークし、別の状態に移ることができます。私はいくつかのアルゴリズムを実装しようとしていましたが、それは私にとって非常に複雑な問題であることが判明しました. これについて教えてもらえますか？ありがとう！

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

正規表現の例: ab.(a|c)*

それについて肯定的なものを見つけることができません。そして、イプシロン遷移を伴うNFAはイプシロン-NFAですか？ありがとう。

DFAを検討してください：

δ（A、01）は何に等しくなりますか？ オプション：

正解はオプションB）ですが、方法がわかりません。誰かがそれを解決するための手順を説明してください。また、一般的に、DFAと移行のためにどのように解決するのですか？

ありがとう。

LR（1）アイテムの先読みを計算する方法を理解するのに問題があります。

私がこの文法を持っているとしましょう：

LR（1）アイテムは、先読みのあるLR（0）アイテムです。したがって、状態0の次のLR（0）アイテムを取得します。

状態：1

誰かが先読みを計算する方法を説明できますか？一般的なアプローチは何ですか？

前もって感謝します

これは私が描いたDFAです-

それが正しいか？の規則に違反する同じ入力シンボルに対して状態の遷移が異なる
ため、私は混乱していますが、他の解決策は考えられません。q42DFA

(コンパイラの書き方を学んでいるところなので、間違った主張があれば訂正してください)

単純に正規表現を使用できるのに、コード (goto ステートメント、テーブル駆動型の実装) で DFA を実装する人がいるでしょうか? 私が理解している限り、字句解析器は文字列を取り込み、言語の文法定義では端末であるトークンのリストを大量に生成し、それらを正規表現で記述できるようにします。正規表現の束をループして、一致が見つかった場合にループから抜け出す方が簡単ではないでしょうか?