問題タブ [turing-machines]

既存の写真[いくつかのオートマトン（DFA、NFA、チューリングマシン）を表示]を撮影し、何らかの方法でそれらをフォーマットに変換する必要があるタスクがあります。これにより、データを使用してオートマトンとして表現することができます。それをいくつかのグラフィカル表現にコンパイルします。以前に似たようなことをした人はいますか？いくつかのオートマトンデータをグラフィカルに表示できるPythonライブラリ/フレームワークはありますか？

私は一連の文字xxxxxx（x ^kおよびk>0）を持っています。私の目標は、この文をオランダの旗に変換することです。つまり、次のようになります。

xxxxx-> RRWWBB xxxx-> RWBB

R <= W<=Bの場合

私が見つけたすべてのソリューションは、非常に複雑です。1本のテープと1本のヘッド/カーソルだけを使用してチューリングマシンを構築するのに役立つヒント/手がかりはありますか？

この問題を解決するのに丸 1 か月かかりました。これは演習の本から得たもので、チューリング マシンでこれを記述する方法を知りたいです。私は本当にこれを学びたいです。誰でも助けてもらえますか？

ログインの最後の 2 文字を考慮してください (両方の文字が同じ場合は、ラテン アルファベットの次の文字を 2 番目の記号として選択してください)。言語 Stretch(x+1) を認識するチューリング マシンを作成します。これは、2 つの文字が連続して出現し、その後に '*' が続き、その後に別の文字列が続き、各文字が x+1 回出現し、最初の文字列で 1 回出現する文字列を含むすべての文字列の言語です。文字の。ここで、x = 1 です。マシンへの入力は、a、b、* の非 null 文字列です。例として、文字が 'a' と 'b' (および x=1) の場合、aba*aabbaa、bb*bbbb、および baab*bbaaaabb は言語にありますが、abb*abbb はありません。

お役に立てれば幸いです。

私の知る限り、計算可能な数値のチューリングは、チューリング マシンによって i 番目のインデックスを返すことができる数値です。したがって、計算不可能な数値は、他のプログラムが他の入力で停止した場合などに小数点が決定される数値のようなものになります。ただし、PI は実数であり、TM によって列挙できないため、計算されますか？では、どの学派が正しいのでしょうか？

たとえば、入力の最後にいて左にシフトしている場合、テープの最初にいることをどのように知ることができますか? もっと |_| ある場合 入力の前に、私が再び最初にいると言うのは簡単ですが、何かあるかどうかはわかりません. これは宿題の質問ではありません。答えは明らかだと思います。そのため、入力の左側にあるテープについてオンラインで何も見つけることができません。ありがとう。

アルファベット：a、b、c私は受け入れるPDAを定義しようとしています

受け入れられる文字列は次のとおりです。＃abc＃; ＃aabbcc＃; ＃aaabbbccc＃; ＃abbccc＃; ＃aaabbc＃などa、b、cの数は必ずしも同じではありません。

一番右の黒いスペースでプッシュダウンオートマトンの頭を開始します。

通常、私はPDAを列に書き込みます。

等々...

アルファベット：0、1

各文字を反転する反転を考えてみましょう: 0 -> 1; 1 -> 0 したがって、w = 0011 の場合、w-flip = 1100

逆順は逆順の文字であると考えてください。したがって、w = 01101 の場合、w-reverse = 10110 です。

今、私は文字列 w を受け取り、w を印刷する PDA を作成しようとしています (w-flip-reversed)

したがって、これは次のように出力されます: "011001"

# はブランク文字と見なしてください。したがって、文字列は #011# で始まります

遷移表は次のようになります。

等々

何か案は？

言語 0^k1^k (k>=0) の列挙子を描画することになっています。それがこの言語のチューリング マシン状態図の作成とどのように違うのかわかりません。チューリングをシミュレートして、{0,1} より上のすべての文字列を指定して、前述の言語を認識する列挙子を作成する必要があると理解しています。文字列 i のこの言語を i ステップで認識する機械で、状態図を使用して行う方法が思いつかなかったのですが、列挙子とチューリング マシンの同等性を証明する方法がこれだと先生に指摘されたので、私たちがしなければならないことは、ダイアグラムを 0^k1^k を認識するチューリング マシンに似たものにする列挙子用に定義された遷移関数を使用することであると考えました。拒否する必要がある入力については、イプシロン? を出力します。しかし、アルファベット {0,1} の上に無数の文字列を作成するにはどうすればよいでしょうか? 初期状態ではワークテープとプリントテープは空です。誰かが私のためにこれらの点を明確にすることができますか? 多分私は誤解しています。

チューリング マシンは、スペース (テープ上のメモリ スペース) と時間の両方で複雑さを考慮することができます。

PSPACE や EXPSPACE などのクラスがあります。

さらに、間違いなく PSPACE にあるアルゴリズムを提示できます。

http://www.springerlink.com/content/3hqtq11mqjbqfj2g/

しかし、実際にプログラムをコーディングすると、他のプログラムよりも高速に実行されるプログラムもあれば、メモリ (RAM) フットプリントが他のプログラムよりも小さいプログラムもあります。

おそらく、問題 X を解決するために PSPACE アルゴリズムをコーディングし、同じ問題を解決するために EXPSPACE アルゴリズムもコーディングする場合、EXPSPACE プログラムは PSPACE コードよりもはるかに多くの RAM を使用する必要があります。

開始アルゴリズムの理論上の評価に基づいて、RAM の使用量を見積もる方法はありますか?

チューリングマシンや有限状態オートマトンのような抽象マシンを実装するプログラミング言語を知っていますか?

つまり、次の入力を処理します。

• 5 タプル (形式言語 101 の悪名高い ⟨Q,Σ,δ,q0,F⟩ )、チューリング マシンまたは抽象マシンのその他の形式表現の7 タプル。
• 入力単語。

そして、入力された単語が受け入れ単語かどうかを教えてください。

ありがとう、

アダム