In [1]:
from tock import *
In [2]:
m = read_csv("examples/sipser-3-7.csv")
m.is_pushdown(), m.is_deterministic()
Out[2]:
In [3]:
to_table(m)
Out[3]:
As always, the first column lists the possible states, and the start state is marked with a > and the accept state is marked with a @.
The first row lists possible tape symbols. Use _ for the blank symbol.
In the cells, we write the destination state, the written symbol, and the move direction.
Here's the state transition diagram, which might or might not be more intuitive:
In [4]:
to_graph(m)
Sipser allows a shorthand in which there are multiple symbols to the left of the arrow. For example, the transitions from q5 to itself could be written 0,x -> L for "if the current symbol is either 0 or x, move left". We don't allow this; instead, use two transitions. He also allows you to write 0 -> L for "move left and don't write anything". Again, we don't allow this; instead, use 0 -> 0,L.
This machine recognizes the language $\{\texttt{0}^{2^n} \mid n \geq 0\}$. Here are some example runs:
In [8]:
run(m, "0 0").only_path()
Out[8]:
This run ended in the accept state, so the machine accepted the string.
In [9]:
run(m, "0 0 0").only_path()
Out[9]:
This run ended in the reject state, so the machine rejected the string.
It's possible, of course, for a run of a Turing machine to go on forever, so the run function will give up after a certain number of steps. You can control that limit using the steps option:
In [10]:
run(m, "0 0 0 0 0 0 0 0", steps=5)
The dotted edge indicates that the run continues but is not shown. In this case, you don't know whether the machine would eventually accept the string.