识别回文串的图灵机：设计、定义和实例

识别回文串的图灵机

1. 设计思想

图灵机识别回文串的思路如下：

将输入字符串ω复制到另一个带子上。
将复制的字符串反转。
比较两个字符串是否相等。
如果相等，接受输入；如果不相等，拒绝输入。

2. TM 定义

输入：一个字符串ω，由字符'a'和'b'组成。
状态集合：Q = {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13}
输入字母表：Σ = {'a', 'b'}
带子字母表：Γ = {'a', 'b', 'X', 'Y', 'R'}
初始状态：q0
接受状态：q13
空格符号：_
转移函数： a. q0, a -> X, R, q1 b. q0, b -> Y, R, q4 c. q1, a -> a, R, q1 d. q1, b -> b, R, q1 e. q1, _ -> _, L, q2 f. q2, X -> X, L, q2 g. q2, Y -> Y, L, q2 h. q2, a -> a, L, q3 i. q2, b -> b, L, q6 j. q3, X -> X, R, q3 k. q3, Y -> Y, R, q3 l. q3, a -> a, R, q3 m. q3, b -> b, R, q3 n. q3, _ -> _, R, q0 o. q4, a -> a, R, q4 p. q4, b -> b, R, q4 q. q4, _ -> _, L, q5 r. q5, X -> X, L, q5 s. q5, Y -> Y, L, q5 t. q5, a -> a, L, q6 u. q5, b -> b, L, q9 v. q6, X -> X, L, q6 w. q6, Y -> Y, L, q6 x. q6, a -> a, L, q7 y. q6, b -> b, L, q10 z. q7, X -> X, R, q7 aa. q7, Y -> Y, R, q7 bb. q7, a -> a, R, q7 cc. q7, b -> b, R, q7 dd. q7, _ -> _, R, q8 ee. q8, X -> X, R, q8 ff. q8, Y -> Y, R, q8 gg. q8, a -> a, R, q8 hh. q8, b -> b, R, q8 ii. q8, _ -> _, L, q2 jj. q9, X -> X, L, q9 kk. q9, Y -> Y, L, q9 ll. q9, a -> a, L, q10 mm. q9, b -> b, L, q13 nn. q10, X -> X, L, q10 oo. q10, Y -> Y, L, q10 pp. q10, a -> a, L, q11 qq. q10, b -> b, L, q13 rr. q11, X -> X, R, q11 ss. q11, Y -> Y, R, q11 tt. q11, a -> a, R, q11 uu. q11, b -> b, R, q11 vv. q11, _ -> _, R, q12 ww. q12, X -> X, R, q12 xx. q12, Y -> Y, R, q12 yy. q12, a -> a, R, q12 zz. q12, b -> b, R, q12 aaa. q12, _ -> _, L, q2 bbb. q13, _ -> _, R, q13

3. 实例识别过程

输入字符串：abba

带子：abba______ 状态：q0
带子：Xbba_____ 状态：q1
带子：XXba_____ 状态：q1
带子：XXXa_____ 状态：q1
带子：XXX_a____ 状态：q2
带子：XXXaX____ 状态：q3
带子：XXXaXX___ 状态：q3
带子：XXXaXXX__ 状态：q3
带子：XXXaXXX___ 状态：q0
带子：XXXaXXXY__ 状态：q4
带子：XXXaXXXYY_ 状态：q4
带子：XXXaXXXYYY 状态：q4
带子：XXXaXXXYYYY 状态：q5
带子：_XXXaXXXYYY_Y 状态：q5
带子：XXXaXXXYY_Y 状态：q5
带子：XXXaXXXY_Y_ 状态：q6
带子：XXXaXXX_Y__ 状态：q6
带子：XXXaXX_Y___ 状态：q7
带子：XXXaX_Y____ 状态：q7
带子：XXXa_Y_____ 状态：q7
带子：XXX_Y______ 状态：q7
带子：XX_Y_______ 状态：q8
带子：X_Y________ 状态：q8
带子：Y_________ 状态：q8
带子：Y_________ 状态：q2
带子：YY________ 状态：q9
带子：YYY_______ 状态：q9
带子：YY_a______ 状态：q10
带子：Y_a_______ 状态：q10
带子：a_________ 状态：q10
带子：a_________ 状态：q11
带子：a_________ 状态：q11
带子：a_________ 状态：q11
带子：a_________ 状态：q11
带子：a_________ 状态：q12
带子：a_________ 状态：q12
带子：a_________ 状态：q12
带子：a_________ 状态：q12
带子：a_________ 状态：q2
带子：a_________ 状态：q2
带子：a_________ 状态：q2
带子：a_________ 状态：q2
带子：a_________ 状态：q2
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13
带子：a_________ 状态：q13

最终状态：接受输入。