問題タブ [finite-automata]

私はいくつかの研究を行っており、1を処理するときにこの小さな非決定論的アルゴリズムについて少し混乱しています。0または1がリダイレクトされるため、q1のブランドに分割され、q2への出口矢印があることを理解していますは 1 ですが、なぜ q3 に分割されるのでしょうか? (0,空の文字列) を読み間違えているように感じます。

すべての状態を一連の状態として入力として受け取るプログラムがあります。次に取得される入力は、一連の状態の最初の状態であり、次に一連の最終状態です。

次は、状態間で私がとる遷移のセットです。

例えば：q0,1,q1

これは、入力 1 で q0 から q1 への遷移があることを意味します。

状態ごとに遷移が入力されます。

しかし、ここで私が直面しているのは、参照がランダムな方法でジャンプアップできることです。つまり、トランジションは、重複しない文字のトランジションの数になる可能性があるため、この原因は、各状態のハッシュマップオブジェクトを動的に維持したいということです。

どうすればこれを達成できますか？

次の言語を受け入れる決定論的有限オートマトンを構築したいと考えています。

{w ∈ {a,b}* : w の各 a の直前に ab がある}

これまでのところ >⨀ ---b---> O ---a---> O.

'>' = 初期状態

⨀ = 最終状態

ダイアグラムの形で決定論的有限オートマトンを構築するためのルールは何ですか? 私の教授は例を挙げて説明してくれましたが、すべての図がどの規則に従わなければならないのか正確にはわかりません。どんな助けでも大歓迎です、ありがとう！

与えられた：

受け入れられている言語が何であるかわかりません。

それを見ると、いくつかの最終結果を得ることができます。

有限状態オートマトンについて議論するトピックはいくつかありますが、実世界のアプリケーションについて詳しく説明しているものは見たことがありません。実際の有限状態オートマトンの具体例は何ですか?

次の正規表現を有限オートマトンに変更するにはどうすればよいですか?

注: この場合、U は結合を意味します

NFAを設計し、JFLAPを使用してDFAに変換したシナリオがあります。

Javaでコーディングする方法を知る必要がありますか？

基本的に、Javaでこれらの状態遷移を実装する方法。switchステートメントとifステートメントを使用してこれを行う例をいくつか見てきましたが、DFA / NFAの設計と、それを使用してJavaで実装する方法との関係はわかりません。

計算理論クラスの宿題をしていて、2 つの DFA を組み合わせる方法が少しわかりません。そのために「交差構造」を使っていると本には書いてありますが、それが何なのかはわかりません。以下に 2 つの例を示します。

Automata と JFLAP の初心者です。私はアクション 有限オートマトン を持っています。これは、言語の任意の文字で、別の状態に移動する必要があることを示しています。これを JLAP に実装するにはどうすればよいですか。
ありがとう