圖靈機在輸入結束時結束000111

Question

我們有一個隨機的0和1的磁帶，如何設計一個車牀，當輸入像＃000111＃那樣結束時，其中0和1的數字是相等的。作業。

作業。第一次發佈問題，謝謝！

Answer 1

你甚至都不需要爲這個圖靈機..​​..

沒有讓步太多這相當於上下文無關文法

A => BC 

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

C => 01 | 0C1 

所以，你真正需要的是一個棧（使用2個以上的磁帶或1個磁帶的有趣管理非常容易實現）。