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

冷不防 2023-10-02 17:09 5阅读 0赞

![在这里插入图片描述][7aeaba7aee6f41f28a90c7caeadf7a5f.png]

#### 图灵机目录 ####

*  一、图灵机介绍
 *  二、设计思想
 *  三、转移函数
 *  四、程序设计
 *  五、运行结果
 *  六、实现源码

## 一、图灵机介绍 ##

这里是图灵机的定义，防止有同学忘记了，就再提一下。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16]

## 二、设计思想 ##

因为我们是要求做PPT上台演讲的，所以我直接将我的PPT内容选择性地展示出来了。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 三、转移函数 ##

因为我只用了一张纸带，所以，需要用到的状态比较多，一共36个状态，手写了一遍，字迹比较潦草，不过不影响思路。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

## 四、程序设计 ##

然后核心就是用字典存储上面的状态转移函数，从q0开始，每次读一个就进行转移，最后计算完后，读头还必须要回到初始位置。这样就模拟出读头在纸带上的移动。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
下面用图片描述一下变化状态，为了节省空间，每个字母就是代表有n个1，比如a就表示这里是a个1，以此类推  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## 五、运行结果 ##

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

## 六、实现源码 ##

#纸袋初始状态为：@a0x0b0y0000
    #输入需要计算的a、x、b、y
    a=input('请输入a的值:')
    x=input('请输入x的值:')
    b=input('请输入b的值:')
    y=input('请输入y的值:')
    #开始将空格@和1还有0写上纸带，纸袋假设无限长
    list=['@']
    for i in range(int(a)):
          list.append('1')
    list.append('0')
    for i in range(int(x)):
          list.append('1')
    list.append('0')
    for i in range(int(b)):
          list.append('1')
    list.append('0')
    for i in range(int(y)):
          list.append('1')
    for i in range(4):
          list.append('0')
    for i in range(10000):
          list.append('@')
    #转移函数，用字典存储
    dict={
        'q0,1':'q1,a,R','q1,1':'q1,1,R','q1,0':'q2,0,R','q2,1':'q3,x,R',
          'q3,1':'q3,1,R','q3,0':'q4,0,R','q4,1':'q4,1,R','q4,0':'q5,0,R',
          'q5,1':'q5,1,R','q5,0':'q6,0,R','q6,0':'q7,1,R','q7,0':'q7,0,R',
          'q7,@':'q8,0,L','q8,1':'q8,1,L','q8,0':'q8,0,L','q8,x':'q2,x,R',
          'q6,1':'q6,1,R','q2,0':'q9,0,L','q9,x':'q9,1,L','q9,0':'q9,0,L',
          'q9,1':'q9,1,L','q9,a':'q0,a,R','q0,0':'q10,0,R',#a*x已完成
          'q10,1':'q11,x,R','q11,1':'q11,1,R','q11,0':'q12,0,R','q12,1':'q12,1,R',
          'q12,0':'q13,0,R','q13,1':'q13,1,R','q13,0':'q14,0,R','q14,1':'q15,c,R',
          'q15,1':'q15,1,R','q15,0':'q16,0,R','q16,0':'q17,1,R','q17,0':'q17,0,R',
          'q17,@':'q18,0,L','q18,0':'q18,0,L','q18,1':'q18,1,L','q18,c':'q14,c,R',
          'q16,1':'q16,1,R','q14,0':'q19,0,L','q19,c':'q19,1,L','q19,0':'q19,0,L',
          'q19,1':'q19,1,L','q19,x':'q10,x,R','q10,0':'q20,0,R',#a*x*x已完成
          'q20,1':'q21,b,R','q21,1':'q21,1,R','q21,0':'q22,0,R','q22,1':'q23,y,R',
          'q23,1':'q23,1,R','q23,0':'q24,0,R','q24,1':'q24,1,R','q24,0':'q25,0,R',
          'q25,1':'q25,1,R','q25,0':'q26,0,R','q26,0':'q27,1,R','q27,@':'q28,0,L',
          'q28,1':'q28,1,L','q28,0':'q28,0,L','q28,y':'q22,y,R','q26,1':'q26,1,R',
          'q22,0':'q29,0,L','q29,y':'q29,1,L','q29,0':'q29,0,L','q29,1':'q29,1,L',
          'q29,b':'q20,b,R','q20,0':'q30,0,R',#b*y已完成
          'q30,1':'q30,1,R','q30,0':'q31,0,R','q31,1':'q31,1,R','q31,0':'q32,0,R',
          'q32,1':'q32,1,R','q32,0':'q33,1,R','q33,1':'q33,1,R','q33,0':'q34,0,L',
          'q34,1':'q35,0,L','q35,1':'q35,1,L','q35,0':'q35,0,L','q35,b':'q35,1,L',
          'q35,x':'q35,1,L','q35,a':'q35,1,L','q35,@':'q36,@,R'#a*x*x+b*y已完成
          }
    state='q0'
    point=1
    while(state!='q36'):
          #(q0,1)
          state=state+','+list[point]
          #1->a
          list[point]=dict[state].split(',')[1]
          #L or R
          direction=dict[state].split(',')[2]
          if direction=='R':
                point=point+1
          else:
                point=point-1
          #q0->q1
          state=dict[state].split(',')[0]
    count=0
    last_index=0
    first_index=0
    num=0
    while(count<6):
          last_index = last_index + 1
          if(list[last_index]=='0'):
                count=count+1
                if(count==5):
                      first_index=last_index
    num=last_index-first_index-1
    print("结果为:",num)

> 只有十分努力，才能看起来毫不费力。

[7aeaba7aee6f41f28a90c7caeadf7a5f.png]: https://img-blog.csdnimg.cn/7aeaba7aee6f41f28a90c7caeadf7a5f.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/fdd34a7c9f1c411d999251264329a801.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/d193f5ca26e442189f68cdf3bc088843.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/744f5e5aa0ea441dbd70eed347263b99.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/9775c1d553e642f3a806dd0d09810dbb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/f83320f61dfc44a79ab2f63ef7a86f64.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/32540b9ba521415c9075be8016b1bffa.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/8b000a50adf5429fb7ad587538463d1a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/8524af4fb8a547ec8690488881119baa.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: https://img-blog.csdnimg.cn/cba489b9890d44a9ab30259758d9b555.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: https://img-blog.csdnimg.cn/92f990f3a16d4e3883317592bc7daf38.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oyv5Y2OT1BQTw==,size_20,color_FFFFFF,t_70,g_se,x_16