問題タブ [automata]

これがプログラミングに直接関係していないことは知っていますが、次の証明に正規言語の反復補題を適用する方法を誰かが知っているかどうか疑問に思いました。

L = {（a ^ n）（b ^ n）（c ^ m）：n！=m}が文脈自由言語ではないことを示す

私はポンピング補題を適用することにかなり自信がありますが、これは本当に私を苛立たせています。どう思いますか？

一部の正規言語を同等の文脈自由文法に変換するにはどうすればよいですか? その正規表現に対応する DFA を構築する必要がありますか、またはそのような変換のための規則はありますか?

たとえば、次の正規表現を考えてみましょう

01+10(11) ^*

上記の正規表現に対応する文法はどのように記述できますか?

部分文字列を含まないs とsのすべての文字列からなる言語を定義する正規表現を作成する問題に取り組んでいます ( Hopcroft、Motwani、Ullman によるAutomata Theory, Languages and Computer の紹介から) 。01011

答えは(0+1)* - 011正しいですか？そうでない場合、これに対する正しい答えは何ですか？

私はJavaScriptゲームに取り組んでおり、ゲームの時間とスプライトアニメーションを制御するオートマトンシステムを持っているだけでなく、タイミングなどのパスファインディングシステムに手を差し伸べています。私の問題は、遅いブラウザで時間をカウントするために使用しているjavascriptループがあまり正確ではないことです。飛び回る傾向があります。ループを強制的に30fpsで一貫して実行する方法はありますか？

基本的に、オートマトンループを1/30秒で実行し続ける方法が必要です。

Automata Theory and Formal Languages で受講したコースが大好きだったので、当然のことながら、コースの基になった本が書かれてから何が起こったのかを知るためにインターウェブを調べ始めました。

私が発見したのは、私がよく知らないもののリストが非常に短いように思われるということでした. たとえば、件名のウィキペディア エントリのオートマトンのリストから、半分はコースでカバーされ、残りの半分はコースでカバーされていない 1 つの言語にほとんど関連していました。

さらに、理論の応用について調べたところ、ほぼ同じ結果が得られました。プログラミング言語の構文、コンパイラ、テキスト検索、そして....それだけです。

それで、それは本当に死んでいますか？それとも進化し続けますか？理論の新しいアプリケーションはありますか?

同じ単語セットを出力する 2 つの異なる文法を教えてください。

図：

アルファベット {0,1} に対する文法 A と B が与えられた場合、文法 A が単語 0101001 を生成できる場合、文法 B も同様に生成できます。文法 B が 0101111 を生成できる場合、文法 A も同様に生成できます。そして、文法 A が 01001 を生成できない場合、B も生成できません。

しかし、ここで重要なのは、文法 A と B が互いに異なるということです。つまり、まったく異なるアルゴリズムを使用しています。次に、それらが生成する出力のセットは、他の出力の適切なサブセットではありません。つまり、対応する出力セットは同じカーディナリティを持つ必要があります。おそらくそれらは複雑度のクラスが異なりますが、それは問題ではありません。よろしければ、古典的なチューリング マシンのように、アルファベット {0,1} に関する文法を教えていただければ幸いです。

私はこの言語を持っています：

{a ⁿ b ^m | m+nは偶数}

これに適した文法は何ですか？

上限は 2^n であり、これらが両方とも有限のマシンであることを考えると、n 状態 NFA と 2^n 以下の状態を持つ DFA の両方の交差が有効になるため、そう考えています。

私はここで間違っていますか？

NFA または DFA の遷移テーブルを記述するための標準構文はありますか?

こんにちは、

.NET（または簡単に翻訳可能）でのLevenshtein DFA（決定性有限オートマトン）の「すぐに使える」実装を知っている人はいますか？私は160000を超える異なる単語を含む非常に大きな辞書を持っています。そして、最初の単語wが与えられた場合、レーベンシュタイン距離で最大2つのwのすべての既知の単語を効率的な方法で見つけたいと思います。

もちろん、特定の単語の1つを編集距離ですべての可能な編集を計算し、それをこれらの各編集に再度適用する関数を使用すると、問題が解決します（非常に簡単な方法で）。問題は効率です---7文字の単語を考えると、これは完了するのにすでに1秒以上かかる可能性があり、可能であれば、レーベンシュタインDFAの場合のように、O（| w |）ステップ。

編集：私は少し勉強することで問題への独自のアプローチを構築できることを知っていますが、現時点ではシュルツとミホフの60ページの長さの記事を読む余裕はありません。

どうもありがとうございます。