Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
ランダムな 0 と 1 のテープがあります。入力が #000111# (0 と 1 の数が等しい) のときに終了する回転機械をどのように設計しますか。
宿題。初めて質問投稿します、よろしくお願いします!
これにはチューリングマシンも必要ありません....
この文脈自由文法に相当するものをあまり多く与えずに
A => BC B => B | 0B | 1B | empty C => 01 | 0C1
したがって、本当に必要なのはスタックだけです (これは、2 つ以上のテープまたは 1 つのテープの興味深い管理で実装するのが非常に簡単です)。