Turing machine for language L={a^m b^n a^m b^n ∣ m,n≥0}

Question

I am having trouble making a Turing machine for language L={a^m b^n a^m b^n ∣ m,n≥0}

What I have thought so far is:

If we start with a blank, the string is empty and it should accept, if not, start reading as and I thought to mark the a's with X and the b's with Y would be OK

Answer 1

You could use this algorithm:

If there is no (more) input: accept.

If the input starts with a "b", then remove it, and look for the first non-"b", keeping track of whether the number "b" read is even or odd:

• if it is a blank:
  • if the input size is even: accept.
  • Otherwise, reject.
• if it is a "#", look for the next non-"#":
  • if it is a "b", then replace it with "#" and return to the start of the input and repeat.
  • Otherwise, reject.
• Otherwise, reject.

If the input starts with an "a", then remove it and look for the first non-"a", keeping track of whether the number "b" read is even or odd:

• if it is a blank:
  • if the input size is even: accept.
  • Otherwise, reject.
• If it is a "b", then look for the first symbol that is not "b" nor "#".
  • If it is an "a", then replace it with "#" and return to the start of the input and repeat.
  • Otherwise, reject.
• Otherwise, reject.

If the input starts with a "#", then look for the first non-"#":

• If it is a blank, accept.
• Otherwise, reject.

Here is a transition table for that approach. "_" is blank. There are 11 states including an accept and reject state, although the latter should not be required, as a TM that halts in a non-accept state is considered as not accepting the input:

state	read	write	move head	next state
start	_		right	accept
start	a	_	right	findABAodd
start	b	_	right	find#Bodd
start	#	_	right	clean
findABA	a		right	findABAodd
findABA	_		right	accept
findABA	b		right	findBA
findABAodd	a		right	findABA
findABAodd	_		right	reject
findABAodd	b		right	findBA
findBA	b or #		right	findBA
findBA	a	#	left	repeat
findBA	_		right	reject
find#B	_		right	accept
find#B	a		right	reject
find#B	b		right	find#Bodd
find#B	#		right	findB
find#Bodd	a or _		right	reject
find#Bodd	b		right	find#B
find#Bodd	#		right	findB
findB	#		right	findB
findB	a or _		right	reject
findB	b	#	left	repeat
repeat	a, b or #		left	repeat
repeat	_		right	start
clean	#	_	right	clean
clean	_		right	accept
clean	a or b		right	reject

Here is a runnable snippet to test it with your own input:

createTuring ({
    transitions: [
        { state: "start",      read: "_",             move: "R", nextState: "accept"    },
        { state: "start",      read: "a", write: "_", move: "R", nextState: "findABAodd"},
        { state: "start",      read: "b", write: "_", move: "R", nextState: "find#Bodd" },
        { state: "start",      read: "#", write: "_", move: "R", nextState: "clean"     },
        { state: "findABA",    read: "a",             move: "R", nextState: "findABAodd"},
        { state: "findABA",    read: "_",             move: "R", nextState: "accept"    },
        { state: "findABA",    read: "b",             move: "R", nextState: "findBA"    },
        { state: "findABAodd", read: "a",             move: "R", nextState: "findABA"   },
        { state: "findABAodd", read: "_",             move: "R", nextState: "reject"    },
        { state: "findABAodd", read: "b",             move: "R", nextState: "findBA"    },
        { state: "findBA",     read: "b#",            move: "R", nextState: "findBA"    },
        { state: "findBA",     read: "a", write: "#", move: "L", nextState: "repeat"    },
        { state: "findBA",     read: "_",             move: "R", nextState: "reject"    },
        { state: "find#B",     read: "_",             move: "R", nextState: "accept"    },
        { state: "find#B",     read: "a",             move: "R", nextState: "reject"    },
        { state: "find#B",     read: "b",             move: "R", nextState: "find#Bodd" },
        { state: "find#B",     read: "#",             move: "R", nextState: "findB"     },
        { state: "find#Bodd",  read: "_a",            move: "R", nextState: "reject"    },
        { state: "find#Bodd",  read: "b",             move: "R", nextState: "find#B"    },
        { state: "find#Bodd",  read: "#",             move: "R", nextState: "findB"     },
        { state: "findB",      read: "#",             move: "R", nextState: "findB"     },
        { state: "findB",      read: "a_",            move: "R", nextState: "reject"    },
        { state: "findB",      read: "b", write: "#", move: "L", nextState: "repeat"    },
        { state: "repeat",     read: "ab#",           move: "L", nextState: "repeat"    },
        { state: "repeat",     read: "_",             move: "R", nextState: "start"     },
        { state: "clean",      read: "#", write: "_", move: "R", nextState: "clean"     },
        { state: "clean",      read: "_",             move: "R", nextState: "accept"    },
        { state: "clean",      read: "ab",            move: "R", nextState: "reject"    },
    ],
    initState: "start",
    tape: "aaabbbaaabbb",
});

<script src="https://trincot.github.io/turing.js"></script>

Answer 2

There are 4 cases in this question:

1. Blank String can be straight away accepted.
2. List contains only a's so if their total number is even we accept the string.
3. Like point 2 if the input contains only b's.
4. The input is a combination of both a and b's.

I will mark the first set of a's as X and second set of a's as Z and the first set of b's as U and second set of b's as V.

The Turing machine designed is:

Here the states {q0,q10} deals with the first case, {q0, q1, q11, q12, q13, q14} deals with the second case, {q0, q4, q15, q16, q17, q18} deals with the third case and {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9} deals with the final case.

I have also designed the corresponding code in python for this Turing machine.

#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)

You can check any states which are not clear from the figure or test it against any inputs. Output for some inputs:

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 3

A high-level strategy for designing a TM for this is the following:

1. Check to see whether you're looking at a string of the form a^2k or b^2k (including the empty string). In any of these cases, halt-accept. Otherwise, continue to step 2.
2. Cross off pairs of a, one each from the first and third sections, respectively, until one of the sections runs out of a. If one runs out while the other still has a, halt-reject. Otherwise, continue to step 3.
3. Cross off pairs of b, one each from the second and fourth sections, respectively, until one of the sections runs out of b. If one runs out while the other still has b, halt-reject. Otherwise, halt-accept.