File Format

 

A file containing a TM description must obey the following specifications.


  1. an ## begins a comment

  2. each line must have the elements separated by TABs (\t)

  3. the first line, not a comment, must have the following elements:

initial statefinal state, blank and wild-card. Note that the wildcard is not part of a

  standard TM definition, but a shortcut for writing a set of transitions:

 

  1.   (state1,wildcard,state2,wildcard,inst) for every symbol not having other  transition from state1, change to state state2, write the same symbol and move the head according to inst.

  2. (state1,wildcard,state2,symbol1,inst) the same as before, except that write symbol1 instead.

  3.    each following line represents a transition: a state, a symbol, a new state, a new symbol, a movement (instruction). A movement can be  R or L. Note that each tape symbol must be only represented by a character. Each transition can be followed by a comment (## not needed).


The following  example can be found here.


## Accepts a^n^2

##  Rogério Reis 1998

## initial state final state  blank wild-card

0       100     .       *

## Transitions

0       .       100     .       R       epsilon rules!

0       a       1       a       R      

1       *       1       *       R       go to the end

1       .       2       c       L       and there a 'c'                     

2       *       2       *       L       go to the begining

2       B       2       b       L       for a fresh comparision

2       C       2       c       L      

2       A       2       a       L      

2       .       3       .       R      

3       A       3       A       R       one 'a'->'A'

3       a       4       A       R

4       *       4       *       R       now one 'c'->'C'

4       c       5       C       L       or 'b'->'B'

4       b       5       B       L

4       .       20      .       L       next square

5       .       6       .       R       to the begining

5       A       6       A       R

5       *       5       *       L

6       a       4       A       R       'a'->'A'

6       c       90      c       L       if a 'c' or 'b' found fail

6       b       90      b       L

6       .       100     .       L       matches!

6       *       6       *       R

##      (n+1)^2 = n^2 + 2n + 1

## one copy

20      *       20      *       L       find first 'a' or 'A'

20      a       23      a       R

20      A       23      A       R

23      C       24      D       R

23      D       23      D       R

23      *       30      *       L       do another copy

24      .       20      B       L

24      *       24      *       R

## another copy

30      A       31      A       R

30      a       31      a       R

30      *       30      *       L

31      D       32      E       R

31      E       31      E       R

31      B       35      B       R

32      .       30      B       L

32      *       32      *       R


35      *       35      *       R

35      .       36      b       L

## plus 1

36      B       36      b       L

36      E       37      E       R

37      b       38      c       L

38      E       38      c       L

38      *       2       *       L 

\


A file containing a tape must contain a sequence of symbols separated by blanks. An example can be found here.