File Format
File Format
A file containing a TM description must obey the following specifications.
• an ## begins a comment
• each line must have the elements separated by TABs (\t)
• the first line, not a comment, must have the following elements:
initial state, final 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:
• (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.
• (state1,wildcard,state2,symbol1,inst) the same as before, except that write symbol1 instead.
• 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.