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 回答