Palindromes over the alphabet {a,b} for an even number

• A string is called palindrome if reading the string from left to right gives the same result as reading the string from right to left.
• An even palindrome has an even number of symbols.
• Some of the examples for even palindrome over the alphabet {a,b} are abba, abaaba, and aabbaa.

Turing machine for all palindromes over the alphabet {a,b} for an even number:

A Turing machine (TM) is a 7 - tuple

$$(Q,\ ∑,\ Γ,\ δ,\ q0,\ qaccept,\ qreject)$$

Where,

Q is a finite set of states.

∑ is the input alphabet that does not contain the blank symbol t.

Γ is the tape alphabet, where t ∈ Γ and ∑ ⊆ Γ.

δ: (Q × Γ) → (Q × Γ × {L, R}) is the transition function.

q0 ∈ Q is the start state.

qaccept ∈ Q is the accept state.

qreject ∈ Q is the reject state, where qreject ≠ qaccept.

For accepting even-length palindrome over the alphabet {a,b}, need to follow the Algorithm Steps given below:

Step 1 -

If there is no input, reach the final state and halt.

Step 2 -

Match the first and last elements and erase them and go on doing the same.

Step 3 -

Once reach epsilon without any mismatch then the string is an even-length palindrome.

Step 4 -

For an even-length palindrome, a TM is defined after the machine runs and erases the first and last element without encountering a mismatch.

Step 5 -

Later on, the Turing machine accepts the string and the string is an even-length palindrome.

Let's take the one example of the string to be like - aabbaa

This string can encounter three cases, as follows:

Case 1 − If starting and ending matches and then erase the first and last one

After erasing − abba

Case 2 − If starting and ending matches and then erase the first and last one

After erasing − bb

Case 3 − If starting and ending matches and then erase the first and last b

After erasing remains − epsilon

This is a Turing machine constructed which accepts an even-length palindrome.

The schematic diagram for TM accepting the even-palindrome is as follows: