语言L={a^m ^n a^m ^n\ m，n≥0}的图灵机

Question

我在为语言L={a^m ^n^m^ b^n \ m，n≥0}制作图灵机时遇到困难。

到目前为止，我的想法是：

如果我们从空开始，字符串是空的，如果不是，它应该接受，开始读取，我想用X标记a，用Y标记b就可以了

Answer 1

这个问题有四个案例：

1. 空格字符串可以立即被接受。
2. 列表只包含a's，所以如果它们的总数甚至是我们接受的字符串。如果输入只包含b‘s，则与
3. 类似。
4. 输入是a和b’s.

G 29的组合。

我将把第一组a作为X，第二组a作为Z，第一组b作为U，第二组b作为V。

图灵机的设计如下：

​

​

在这里，州{q0,q10}处理第一个案例，{q0, q1, q11, q12, q13, q14}处理第二个案例，{q0, q4, q15, q16, q17, q18}处理第三个案例，{q0, q1, q2, q3, q4, q5, q6, q7, q8, q9}处理最后一个案例。

我还为这个图灵机器设计了相应的python代码。

#function to perform action of states
def action(inp, rep, move):
    global tapehead
    if tape[tapehead] == inp:
        tape[tapehead] = rep
        if move == 'L':
            tapehead -= 1
        else:
            tapehead += 1
        return True
    return False

tape = ['B']*50 
string = input("Enter String: ")
i = 5
tapehead = 5
for s in string: #loop to place string in tape
    tape[i] = s
    i += 1

state = 0
a, b, X, Z, U, V, R, L, B = 'a', 'b', 'X', 'Z', 'U', 'V', 'R', 'L', 'B'
oldtapehead = -1
accept = False
while(oldtapehead != tapehead): #if tapehead not moving that means terminate Turing machine
    oldtapehead = tapehead

    if state == 0:
        if action(a, X, R):
            state = 1
        elif action(B, B, R):
            state = 10
        elif action(Z, Z, R):
            state = 7
        elif action(b, U, R):
            state = 4

    elif state == 1:
        if action(a, a, R):
            state = 1
        elif action(b, b, R):
            state = 2
        elif action(B, B, L):
            state = 11

    elif state == 2:
        if action(b, b, R) or action(Z, Z, R):
            state = 2
        elif action(a, Z, L):
            state = 3

    elif state == 3:
        if action(b, b, L) or action(Z, Z, L) or action(a, a, L):
            state = 3
        elif action(X, X, R):
            state = 0

    elif state == 4:
        if action(b, b, R):
            state = 4
        elif action(Z, Z, R):
            state = 5
        elif action(B, B, L):
            state = 15

    elif state == 5:
        if action(Z, Z, R) or action(V, V, R):
            state = 5
        elif action(b, V, L):
            state = 6

    elif state == 6:
        if action(Z, Z, L) or action(V, V, L) or action(b, b, L):
            state = 6
        elif action(U, U, R):
            state = 0

    elif state == 7:
        if action(Z, Z, R):
            state = 7
        elif action(V, V, R):
            state = 8

    elif state == 8:
        if action(V, V, R):
            state = 8
        elif action(B, B, R):
            state = 9

    elif state == 11:
        if action(a, a, L):
            state = 11
        elif action(X, X, R):
            state = 12

    elif state == 12:
        if action(a, Z, R):
            state = 13

    elif state == 13:
        if action(a, X, R):
            state = 12
        elif action(B, B, R):
            state = 14

    elif state == 15:
        if action(b, b, L):
            state = 15
        elif action(U, U, R):
            state = 16

    elif state == 16:
        if action(b, V, R):
            state = 17

    elif state == 17:
        if action(b, U, R):
            state = 16
        elif action(B, B, R):
            state = 18

    else:
        accept = True


if accept:
    print("String accepted on state = ", state)
else:
    print("String not accepted on state = ", state)

您可以检查图中不清楚的任何状态，也可以对任何输入进行测试。一些投入的产出：

Enter String: aaaaabbaaaaabb
String accepted on state =  9

Enter String: aaaaaa
String accepted on state =  14

Enter String: 
String accepted on state =  10

Enter String: aaabaaa
String not accepted on state =  5

Enter String: bbb
String not accepted on state =  16

Answer 2

为此设计TM的高级别策略如下：

1. 检查是否正在查看表单a^2k或b^2k的字符串(包括空字符串)。在任何一种情况下，停止接受。否则，继续执行步骤2。
2. 从第一节和第三节分别交叉了一对a，直到其中一个区段用完a为止。如果其中一个在另一个仍然有a的情况下耗尽，则停止-拒绝。否则，继续执行步骤3。
3. 从第二节和第四节分别交叉了一对b，直到其中一个区段用完b为止。如果其中一个在另一个仍然有b的情况下耗尽，则停止-拒绝。否则，halt-accept.