問題タブ [automata-theory]

非決定性オートマトンは、オートマトンの状態と入力文字列のどこまで到達したかを追跡するだけで、入力文字列で簡単にシミュレートできます。しかし、非決定論的なトランスデューサ (もちろん、トランスデューサは入力シンボルを出力シンボルに変換し、ブール値だけでなく文字列を出力として与えることができます) をどのようにシミュレートできますか? 非決定性のために多数になる可能性がある出力文字列を何らかの方法で追跡する必要があるため、これはより複雑なようです。

質問がありますが、まだ答えを見つけることができません。シングルヘッド テープを使用した 2 ヘッド テープ チューリング マシンのオンライン シミュレーションを実行する必要があります。この問題には 1 つのシングルヘッド テープでは不十分であり、2 つのシングルヘッド テープを使用してシミュレーションを実行する必要があるという事実に関するオンライン記事をいくつか見つけましたが、2 つの正確なシミュレーションを提示することはできませんでした。 -head TM これらのシングルヘッド テープを使用します。そうする方法について何か考えはありますか？ありがとう、

DFAはループでシミュレートでき、NFAは再帰的方法でシミュレートできると聞きました。それがどのように機能するのかわかりません。誰か私に例を教えてもらえますか？

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

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

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

。

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

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

よろしくお願いします。

LR(1) - アイテムの先読みの原則を理解するのに苦労しています。先読みセットを計算するにはどうすればよいですか?

例として、次の文法があるとします。

次に、最初の状態は次のようになります。

先読みとは何かは知っていますが、それらを計算する方法がわかりません。グーグルで答えを探しましたが、これを簡単に説明しているウェブページが見つかりませんでした。

前もって感謝します

それについて肯定的なものを見つけることができません。そして、イプシロン遷移を伴うNFAはイプシロン-NFAですか？ありがとう。

チューリング マシンの拡張機能 (双方向無限テープ、RAM、複数の読み取り/書き込みヘッド、非決定性など) のうち、以前は決定できなかった問題を TM が決定できるものはありますか?

私の本では、「決定不可能な言語がある」と書かれており、その証拠は次のとおりです。

すべてのアルゴリズムは単語です。次に、可算アルゴリズムのみがあります。しかし、無数の言語が存在するため、アルゴリズム以上のものがあります。

すべてのアルゴリズムが単語であると言われるのはなぜですか? 単語は記号、アルファベットの要素の連結ですが、単語とアルゴリズムの関係は何ですか? 誰か私にそれを説明できますか？