0

ランダムな 0 と 1 のテープがあります。入力が #000111# (0 と 1 の数が等しい) のときに終了する回転機械をどのように設計しますか。

宿題。初めて質問投稿します、よろしくお願いします！

4

1 に答える 1

0

これにはチューリングマシンも必要ありません....

この文脈自由文法に相当するものをあまり多く与えずに

A => BC

B => B | 0B | 1B | empty

C => 01 | 0C1

したがって、本当に必要なのはスタックだけです (これは、2 つ以上のテープまたは 1 つのテープの興味深い管理で実装するのが非常に簡単です)。

于 2013-03-09T00:21:57.783 に答える