算法1： ●当图灵机遇到a时，将a改写为# 向右寻找b,找到b,将b改写为# 再向左找a 直到所有a都找完。 (向左找的a是整个a串最左边的a)
算法1： l当图灵机遇到a时，将a改写为# 向右寻找b，找到b，将b改写为# 再向左找a … 直到所有a都找完。 (向左找的a是整个a串最左边的a)
指令为 ①读到一个a,用#代替它，向右找b <start,a,del b,#R> <del b,a,del b,a,R> <del b,#del b,#R>
指令为 ①读到一个a，用#代替它，向右找b <start，a，del_b，#，R> <del_b，a，del_b，a，R> <del_b，#，del_b，#，R>
②处于状态delb, 扫描到b,用#代替 它，向左寻找a, (从①重复) <del b,b,seek a,#L> <seek a,#seek a,#L> <seek a,a,delb,#,R>/最右的a
②处于状态del_b，扫描到b，用#代替 它，向左寻找a，（从①重复） <del_b，b，seek_a，#，L> <seek_a，#，seek_a，#，L> <seek_a，a，del_b，#，R> //最右的a
③seek a状态时，氵 没有再发现a(都己被 #所代替)，还需要检查是否所有的b 都已经被扫描过。 <seek_a,check, R <check,#check,#R> <check,B,accept,B,N>
③seek_a状态时，没有再发现a(都已被 #所代替)，还需要检查是否所有的b 都已经被扫描过。 <seek_a，├，check， ├ ，R> <check，#，check，#，R> <check，B，accept，B，N>
问题 该图灵机能接收ab"的所有串 但该图灵机也能接收aababb等 原因：使用#代表已扫描的a和b 没有保证a和b的顺序
问题 l该图灵机能接收a nbn的所有串 但该图灵机也能接收aababb 等 原因：使用#代表已扫描的a和b 没有保证a和b的顺序