問題タブ [automata-theory]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
theory - 複数の受け入れ/失敗状態を持つ非決定論的有限オートマトン
正規表現または（明らかに同等の）決定論的有限オートマトンを使用すると簡単な状況で、NFA の受け入れ状態を作成するのに問題があります。
たとえば、最終的にどの状態も可能でない場合にのみマシンが受け入れるとしたらどうでしょうか? powerset 構造を使用して、受け入れ状態が空のセットである DFA を作成できます。NFAでこれを行うと私が考えることができる唯一の方法は、すべての状態を「受け入れ」にしてから、最後にそれを反転させて、受け入れが実際には失敗になるようにすることです。
さらに悪いことに、6 つの州があり、たとえば、{0,1,2} のすべての州に属している可能性があるが、{3,4,5} には属していない可能性があるかどうかを確認したい場合はどうでしょうか? 繰り返しますが、これは DFA を使えば簡単です。
これらのケースで NFA を微調整する簡単な方法はありますか?
ありがとう！
finite-automata - 同一の構成を持つ最終状態と非最終状態を最小限の DFA にマージできますか?
私はオートマトン理論に関するいくつかの質問を練習してきました.どこで間違ったのかを理解できない最小dfaに関する質問に出くわしました.最小dfaで4つの状態を取得していますが、私の本は答えが3.質問は、与えられた NFA を最小 DFA に変換し、後者の状態の数をカウントするように求めます。与えられた NFA (p と r はそれぞれ初期状態と最終状態) は次のとおりです。
[r]、[p]、[q、s]、[dead] の 4 つの状態を取得しています。最終状態 [r] と非最終状態 [q、s] は、同様の結果になるため、ここでマージできますか?入力 a および b を受け取る際の構成??最終状態と非最終状態が同じ等価クラスにならないことを学びました...
regex - 無限部分集合のクリーネ閉包
L = {a n | n >= 0}、ここ
で
、すべての n >= 1 について。
したがって、L は、長さ 0 のシーケンスを含む、すべての長さの a のシーケンスで構成されます。L2 を L の任意の無限サブセットとします。(L2)* を認識する DFA が常に存在することを示す必要があります。
L2 が有限部分集合である場合、L2 は DFA であり、したがってクリーネ クロージャによって L2* は DFA によって認識されるため、非常に明白です。しかし、文字列の長さが素数などの場合、L2 が DFA として表現されない可能性があるため、無限サブセットの場合は取得できません。
context-free-grammar - CFG のあいまいさを修正するアルゴリズムはありますか?
以下はあいまいな CFG です。
文字列「ba」を解析することで、文法のあいまいさを簡単に確認できます。
上記のような CFG のあいまいさを修正するアルゴリズムはありますか?
助けてくれてありがとう
automata - SCXML はどのようなオートマトンを記述しますか?
SCXML の制限は、決定論的有限オートマトン/決定論的有限ステート マシンと同じですか? それとも、SCXML の能力は他の抽象マシン/オートマトンの方がうまく捉えられますか? たとえば、SCXML は、プッシュダウン オートマトンやチューリング マシンを説明するのに十分強力であると考えられますか?