用Python实现ax²+by的图灵机【形式语言与自动机】

用Python实现ax²+by的图灵机【形式语言与自动机】

图灵机目录

• 一、图灵机介绍
• 二、设计思想
• 三、转移函数
• 四、程序设计
• 五、运行结果

一、图灵机介绍

这里是图灵机的定义，防止有同学忘记了，就再提一下。

二、设计思想

因为我们是要求做PPT上台演讲的，所以我直接将我的PPT内容选择性地展示出来了。

三、转移函数

因为我只用了一张纸带，所以，需要用到的状态比较多，一共36个状态，手写了一遍，字迹比较潦草，不过不影响思路。

四、程序设计

然后核心就是用字典存储上面的状态转移函数，从q0开始，每次读一个就进行转移，最后计算完后，读头还必须要回到初始位置。这样就模拟出读头在纸带上的移动。

下面用图片描述一下变化状态，为了节省空间，每个字母就是代表有n个1，比如a就表示这里是a个1，以此类推

五、运行结果

计算出10000大概要花费30s，两个原因：1、Python编译速度很慢，C++实现起来肯定会快很多 2、单带计算读头移动次数太多，距离太长，可以改为多带实现，会更快。