問題タブ [automata]

PythonでIME(Input Method Editor)シミュレーターを作っています。入力が来て、出力がpythonプログラムの結果を示すとき、それは有限状態マシンのようなものです。一つ一つの結果表示がわからないので、コマンドライン風に表示する方法を教えていただきたいです。

質問は2つのことです。

1. ひとつひとつの結果をどう表現するか。
2. 「スペース」または「バックスペース」を実装する方法は?

3. 「del（バックスペース）キー」入力時にこのコードを使用してもよろしいですか？

   /li>

有限のオートメーションを指定して正規表現を生成するプログラムを作成する方法を誰かが知っているか、またはプログラム (できれば c) が既に存在するかどうかに興味があります。

物事を簡単にするために、状態の数を約 4 に制限したいと思います。FA は最小形式であり、FA には 1 つの FinalState と 1 つの StartState のみがあると仮定します。

私はしばらくそれについて考えてきましたが、最初にすべきことは、FA の遷移表を作成することだと思います。

したがって、FA は次のようになります。

これにより、正規表現が生成されます: b + (ab*a(a + b))

私は何時間も頭を悩ませてきましたが、これをどのように行うかについて困惑しています. どんなアイデアでも大歓迎です。

「hello」、「hello world」、「staytogether」という単語を受け入れるnfaの設計に支援が必要です。アルファベットには、英語のアルファベット、数字、記号が含まれています。始めるのに助けが必要です。誰か提案がありますか？

次の言語の文脈自由文法を構築するにはどうすればよいですか。

私は次のことを試みることから始めました：

そしてA=何か他のもの...しかし私はこれを機能させることができませんでした。

。

ノーのために何個のcのシャッドが増加したかをどうやって思い出すことができるのだろうかと思っていました。bの増加？
例えば：

線形時相論理を使用してこれらのオートマトンをどのようにモデル化したかを理解するのに苦労しています。このリンクの写真にあるケースについて、誰かが私にこれを説明してください。または、例でこれを説明しているソースを教えてください。

よろしくお願いします。

フォーマル言語のチョムスキー分類では、Non-Linear, Unambiguous and also Non-DeterministicContext-Free-Language(N-CFL) の例が必要ですか?

1. 線形言語:線形文法が可能なもの ( ⊆ CFG) 例:
   L ₁ = {a ⁿ b ⁿ | n ≥ 0 }

2. Deterministic Context Free Language(D-CFG) : Deterministic Push-Down-Automata(D-PDA) が可能な言語 (例:
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0 }
   L ₂は明確です。

線形でないCF 文法は非線形です。
L _nl = {w: n _a (w) = n _b (w)} も非線形 CFGです。

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能な例
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃も Linear CFG です。

--4. あいまいな CFL : only ambiguous CFG is possible
L ₄ = { a ⁿ b ^{n cm} | n ≥ 0, m ≥ 0 } U { a ⁿ b ^{m cm} | n ≥ 0, m ≥ 0 }
L ₄は非線形かつ曖昧な CFG であり、すべての曖昧な CFL \subseteq N-CFL.

私の質問は次のとおりです:
すべての非線形、非決定論的 CFL は曖昧ですか? そうでない場合は、非線形で非決定論的な CFL であり、明確な例が必要ですか?

以下にベン図を示します。

ここでも質問

NFAとイプシロンNFAのリアルタイムの例、つまりコンパイラの設計に使用される以外の実際の例は何ですか?

ポンピング補題の問題について助けが必要です。

これは私がこれまでに得たものです：

y = abbc^n とし、n はポンピング補題からの長さです。a:s の数が b:s の数よりも少なく、b:s の数が c:s の数よりも少ないため、y は L にあります。

u = a、v = bb、w = c^n とします。|紫外線| < y、ポンピング補題で述べたとおり。「ポンプ」(bb)^2 すると、次のようになります。

これは正しいですか ？私は「正しい道」を進んでいますか？

ありがとう

これを確認できますか：https ：//dl.dropbox.com/u/25439537/finite%20automata.png

これはチェックされた宿題ですので、心配しないでください。先生が間違っているとマークしているので、私の答えが正しいかどうかを明確にしたいだけです。

私の答えは（（a + b）（a + b））* aです。最初の（a + b）は上の矢印を意味します。2番目（a + b）は、下の矢印を示します。最後の「a」は、常に「a」で終わる必要があることを示しています。

先生に渡すことができるように、たくさんの専門家からの証拠を記録したいだけです。

Hopcroft アルゴリズムを使用して、DFA から最小 DFA への変換を行いました。このリンクhttp://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm でウィキペディアから疑似コードを見つけ、Pythonコードを作成してdfaを変換しました。

私のDFAは5つの指標で構成されています

このアルゴリズムがコードで機能しない理由がわかりません。コードに問題はありますか?