Important Comments

There are several differences between JFLAP's Turing machines and the Turing machines in the Martin textbook.

1. The blank character.

   • JFLAP uses the character B as the blank symbol.
   • Martin uses the triangle character as the blank symbol.
   • To correct for this, use B instead of triangle.
     • Note this can cause some problem in translating Martin's TM examples into JFLAP since he sometimes uses the character B such as in example 9.3 on pages 264 and 265.

2. Turing machine tape.

   • JFLAP's TMs are 2-way infinite.
   • Martin's TMs are 1-way infinite.

3. The initial configuration.

   • The initial configuration of JFLAP TMs begin with the tape head pointing to the first character of input.
   • The initial configuration of Martin's TMs begin with the tape head pointing to the leftmost square of the tape which holds a blank character.
     The input occupies the next n tape cells.
   • To correct for this, make the input to the JFLAP TM Bx rather than x.
   • For example, if you want to input the string aaa, enter the input as Baaa.

JFLAP TM examples

1. Turing machine which adds unary numbers.
   • That is, 11111+1111 becomes 111111111 and the tape head points to the first 1.
2. Search example 1. This Turing machine searches for the right end of a string of a's.
3. Search example 2. This Turing machine searches for the right end of a string of a's and b's.
4. Example 9.1. This Turing machine accepts any string which contains the pattern aba.
5. Example 9.2. This Turing machine accepts any string over the alphabet {a,b} which is a palindrome.
6. Example 9.3 (divided into 2 parts)
   • Part 1. This Turing machine identifies the middle of the input string over the alphabet {a,c}.
     • Note we use c rather than b.
     • If the string has odd length, it will crash.
     • If the string has even length, it converts the second half of the string into capital letters.
     • At the end of processing an even length string, the returns to point at the first tape cell containing a blank.
     • The only thing this TM does not contain is the transition from state q₁ to state h.
   • Part 2. This Turing machine verifies the two halves of an even length string over the alphabet {a,c} are identical, assuming the string has been processed by the first Turing machine.
     • Note state q₀ is really state q₅.
     • All other states are as they are numbered except state h which is state q₁₀.