問題タブ [automaton]

このオートマトンシミュレーターで状態から次の状態に移動するために、このメソッドを使用しています。

}

ここ：

私は何か間違ったことをしているかもしれませんが、私はそれを理解していません。

StringBuilderは正しく処理されていますが、オートマトンは常に状態0でスタックします。なぜですか？

完全なコードは次のとおりです。

入力ファイルは次のとおりです。

編集：ここでは、この入力ファイルの形式について説明します

最初の行は、テストケースの数を表しています。

各テストケースは3つの整数で始まり、最初はオートマトンの状態の数、次はアルファベットの記号の数、次に最終状態の数です。

次の行はアルファベットです。シンボルは一緒に表示されます。

次に、遷移関数を説明する状態の数に等しい行数があります。この行グループの最初の行は、オートマトン（qo）の最初の状態の遷移関数を表し、最初の要素は、アルファベットの最初の記号がこの状態になったときに到達した状態を表します。元の問題ステートメントからこれを理解するのに苦労しました。これは私がそれを見に来た最も簡単な方法です：

台詞：

同等：

次に、オートマトンの最終状態を示す行があります。

次に、初期状態と入力文字列の数を示す行が表示されます。

次に、入力文字列の行が表示されます。

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

C

太字で書かれているすべての行が間違っています。

私が得ている：

私のオートマトンはすべてを受け入れて状態0でスタックしています、なぜですか？

Stateオブジェクト（KeyとしてCharacter、ValueとしてStateを持つHas​​hMapsをallStatesという名前のArrayListに配置したい。ここでequalsメソッドとhashCodeメソッドをオーバーライドする必要がありますか？なぜですか？どのように？

このコードは、これまでに作成したAutomatonクラスとStateクラス用です。

Java や C++ などの OOP 言語で有限状態オートマトンを使用するプログラムを実装することを考えています。

優れたソフトウェア設計に関して、管理可能な量の利用可能な状態でこれを実装する最良の方法は何だと思いますか?

状態ごとに独自のクラスを実装するのは良いことですか? はいの場合、2 つの状態の間の橋渡しを行うにはどうすればよいですか?

コメントありがとうございます！

私は現在、解析しなければならない特に不快な文字列形式に苦労しています。文字列には、解決する必要がある変数プロパティを示す部分文字列を含めることができます。のようなものを想像してみてください"ThisExampleStringContainsA[VARIABLE_PROPERTY]"。また、これらのプロパティは任意にネストすることができ、コンテキストに応じて異なる意味を持つこともできます。が実際に変数の有効な名前ではない場合[VARIABLE_PROPERTY](もちろん実行時に決定する必要があります)、それは文字列全体の通常の部分になり、変更されずそのまま残ります。次に、左角括弧の数が右角括弧の数と一致する必要がないため、無効な文字列はありません。This]Is[A[Valid]]][ExampleToo!. ルールは他にもありますが、これでアイデアが得られます。

そのため、現時点では、これにどのようにアプローチするかはわかりません。私の最初の試行は、if と else の信じられないほどの混乱で終わり、ソリューションには何らかの状態概念を適切に組み込む必要があることにますます気づきました。今、私はこれを行うためにオートマトンを使用することをますます考えています. しかし、私はオートマトンを純粋な理論的構築物としてしか見たことがありません。実際の実装に出くわしたことはありません。さらに、オートマトンは伝統的に単語を検証するために使用されます。つまり、正式に定義された言語に属しているかどうかを判断します。言うまでもなく、その言語を正式に定義することは私には困難です。

これにどのようにアプローチしますか？実際にオートマトンを実装することは健全なアプローチだと思いますか? オブジェクト指向設計の観点からこれをどのようにモデル化しますか? それが違いを生む場合、プロジェクトはC＃にあります。まったく違うものを提案しますか？

/編集：私の説明は少し誤解を招く可能性があります。ここにいくつかの詳細があります：私にとっての問題は、プロパティを正しい順序（最も内側から最も外側へ）で見つけることです。解決する次のプロパティを特定したら、その最終値での実際の置換は比較的簡単です。

上記の例を取り上げて、何が起こるべきかを段階的に示します。完全な入力文字列は次This]Is[A[Valid]]][ExampleToo! のとおりです。最初の閉じ括弧と最後の開き括弧は、何も囲まれていないため、通常の文字です。同じことが、対応するブラケット ペアの間にないすべての文字にも当てはまります。残りは の部分[A[Valid]]]です。最も内側のプロパティを最初に解決する必要があります[Valid]。角かっこは、プロパティを識別する文字列を囲んでいるだけなので、Valid解決しようとしているプロパティの名前です。たとえば、この文字列は実際にはプロパティを識別し、実際の値に置き換えられますFoo。ブラケットを含む識別文字列が置き換えられるため、 に[Valid]なりFooます。今、私たちは見なければなりません[AFoo]]. AFooがプロパティを識別しないふりをしてみましょう。これにより、部分文字列は変更されません (括弧を含む)。最後に、2 番目の右括弧の後AFooに対応する左括弧がないため、これも単なる文字です。処理が完了すると、文字列全体が次のようになります。This]Is[AFoo]][ExampleToo!

この例が物事をもう少し明確にすることを願っています。ここでは文字列形式を簡略化していることに注意してください。これは、私がどのような困難に直面しているかを示すためのものです。問題にアプローチする方法についてのアイデアを提供してくれる答えを探しています。この解析は何千もの文字列に対して実行する必要があるため、ソリューションにはある程度妥当なパフォーマンスが必要です。

私の目標は、状態を入力し、文字が正のブール式（trueとfalseを含む）を返す遷移関数をOCamlに実装することです。つまり、\ delta（q0、a）= q1および（q2またはq3）

私の問題は、ocamlでブール式を表現する方法と、この特定の遷移関数を実装する方法です。

キーフレーズのデータ​​ベース（ウィキペディアの記事のタイトルから抽出）から、テキストドキュメントでキーフレーズの出現を検索したいと思います。（つまり、ドキュメントがあれば、対応するウィキペディアの記事があるフレーズがあるかどうかを調べたい）Aho-Corasickアルゴリズムについて知りました。何百万ものエントリの辞書用にAho-Corasickオートマトンを構築することが効率的でスケーラブルかどうかを知りたいです。

55行14セルのルール110の使い方を考えていました。次に、それをLEDマトリックスディスプレイに表示する必要があります。

とにかく私の質問は、どうすればそのようなオートマトンを実装できますか？

どこから始めればいいのかよくわかりません。誰かがこの問題にどのように取り組むことができるかについて光を当ててください。

私が従わなければならない特定の方法はありますか？

ありがとう

-使用されるプログラムは->C

編集

それは理にかなっていますか ？？orgはoriginalの略です

アルファベット {a,b} でパターン P="abaabba" を検索するオートマトンを作成するにはどうすればよいですか?

DFA を最小化するために Brzozowski のアルゴリズムを実装しようとしています。以下は同じアルゴリズムです。

ここでr()は NFA の反転であり、D()NFA を DFA に変換します。

r()しかし、Googleで検索してもあまり情報が得られないという意味がわかりません。

誰でもr()NFAとは何か説明してもらえますか?

利用可能な他の単純なアルゴリズムまたは C++ 実装があれば、リンクを教えてください。

Peg solitaire / Senkuのゲームのソルバーをプログラムする必要があります ここに
既に質問がありますが、提案された答えはバックトラッキングを使用したブルート フォース アルゴリズムであり、これは私が探しているソリューションではありません。 A* アルゴリズムを適用するには、ヒューリスティックを見つける必要があります。残りのペグは、すべての移動で 1 つのペグが破棄されるため、コストが常に均一になるため、適切なヒューリスティックではありません。 何か案は？