Turing Machine for Even Palindromes

A palindrome is a sequence of symbols that reads the same backward as forward (i.e., aba).  If a palindrome contains an even length, it is also called an even palindrome (i.e., abaaba). Let’s see the Turing Machine for even palindromes, 

Let us construct a Turing machine for even palindromes language (L= abaaba). The Input String will become as under,

Turing Machine For Even Palindromes - Input tape

Algorithm for Even Palindromes

  • Step 01: Replace the first, leftmost symbol with the Blank symbol “$”.
  • Step 02: Replace the rightmost symbol with the Blank symbol “$”.
  • Step 03: repeat above both steps (1&2) until all symbols are replaced with “$”

Input Tape For Even Palindromes

Read/Write Head movement on the Input tape is explained under various steps in the diagram

Input tape For Even Palindromes

Turing Machine for Even Palindromes

Turing Machine for Even palindromes is explained under

Turing Machine For Even Palindromes