Машина Тьюринга для языка L={a^m b^n a^m b^n ∣ m,n≥0}

Стратегия высокого уровня для разработки TM для этого заключается в следующем:

1. Проверьте, видите ли вы строку вида a^2k или b^2k (включая пустую строку). В любом из этих случаев приостановите принятие. В противном случае перейдите к шагу 2.
2. Вычеркивайте пары a, по одной из первой и третьей секций соответственно, пока в одной из секций не закончатся a. Если у одного заканчивается, а у другого еще есть a, остановите отказ. В противном случае перейдите к шагу 3.
3. Вычеркивайте пары b, по одной из второй и четвертой секций соответственно, пока в одной из секций не закончатся b. Если у одного заканчивается, а у другого еще есть b, остановите отказ. В противном случае приостановите принятие.

В этом вопросе 4 случая:

1. Пустая строка может быть принята сразу.
2. Список содержит только a, поэтому, если их общее количество четно, мы принимаем строку.
3. Как пункт 2, если вход содержит только b.
4. Вход представляет собой комбинацию a и b.

Я обозначу первый набор а как X, второй набор а как Z, первый набор Ь как U и второй набор Ь как 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