turing-machines

2熱

2答えて

任意の数のテープ記号を含むチューリングマシンMは、{0,1、B}（B =ブランク）という3つのテープ記号だけを含む1つのM 'によってシミュレートすることができる。 Mは{1、B}と言う？

0熱

2答えて

私は、jflapに大きく依存しているコースでオートマトンテストを勉強しています。問題があります。多くのドキュメントがなく、thisとthisのようなjlapで見つかったサンプルオートマトンは、今後のテストの準備には不十分です。どこでもっと見つけることができますか？遷移を持つグラフとして表示されたサンプルチューリングマシンを備えた他のリソースも役立ちます。

0熱

1答えて

JFLAPチューリングマシンショートカットの問題

JFLAPには、チューリングマシンの遷移のためのいくつかのショートカットがあります。これらのショートカットの1つは、現在のテープ記号が指示された記号でない限り、遷移することができます。たとえば、トランジション！g、x; Rは、基本的に「現在のテープ記号がgでなければ、この遷移をとる」と言う。これまでのところ、とても良いです。しかし、私が望む移行は、基本的に「現在の記号が文字列の終わり（空のセル）

11熱

2答えて

言語が再帰的か再帰的に列挙可能かどうかを判断するには？

言語（例えば、L = {a^nb^mc^s | 0 < = n < = m < = s}）は、規則的、文脈自由、再帰的、再帰的に列挙可能かどうかを判断する必要があります。言語が正規であるか（動作するDFAまたは正規表現を見つけるか）文脈自由（PDAまたは文脈自由文法が動作するかどうか）を判断する方法は知っています。再帰的言語には、常に停止するチューリングマシンがあり、再帰的に数え切れないほどの言

5熱

3答えて

マシンがチューリングマシンであるかどうかを確認する方法

私はウィキペディアの記事a list of Turing machine equivalentsを見つけました。しかし、与えられたマシンが同等のチューリングマシンであるかどうかを判断する方法を教えているわけではありません。チューリングマシンの定義を使ってそれを証明する必要がありますか？例を挙げていただけますか？ありがとうございました。

3熱

3答えて

0を数え、2進数がどれくらいあるかを計算するチューリングマシンアルゴリズム

0の文字列を読み取ってバイナリにいくつあったかを記録するチューリングマシンのアルゴリズムが必要になります。私は、実際にはマシンが実際に0をカウントしないことを認識していますが、それを行う方法についてはかなり困惑しています。まず、2進数がXか何かで始まる場所に印を付ける必要があります。そして、最下位ビットがaであれば、最初の0と次の0のそれぞれに1を書きます。 0の場合は1になりますが、1の場合

2熱

2答えて

オートマトンプログラミング言語

チューリングマシンや有限状態オートマトンなどの抽象機械を実装するプログラミング言語をご存知ですか？、次の入力処理である。 5タプル（The notorious ⟨Q,Σ,δ,q0,F⟩ from formal languages 101）、チューリングマシンまたは抽象機械の任意の他の形式的な表現のため7-tuple。入力語。入力単語が受け入れられた単語かどうかを教えてください。おかげで、