Internal representation of machines¶
Stores¶
Internally, all kinds of automata are represented in the same way. They have one or more stores, which are half-infinite tapes, but you don’t have to use them as tapes; you can use them instead as finite states or as stacks.
Transitions¶
The operation of the automaton is defined by transitions of the form:
a,b,c -> x,y,z
where the left-hand side and right-hand side must have the same number
of elements as there are stores, and each element is a symbol
annotated with a head position. The meaning of the transition is that
if the first store matches a
(relative to the current head
position), replace it with x
; if the second store matches b
,
replace it with y
; and so on.
In more detail, each element is either empty (&
) or a whitespace-separated
string of symbols, optionally preceded or followed by a caret (^
).
If the caret precedes the string, the head is one before the first symbol;
If the caret follows the string, the head is one after the last symbol;
If the caret is absent, the head is over the first symbol.
Note that ^ &
is different from & ^
, and &
is the same as & ^
.
Despite the peculiarities of this notation, it can describe all the possible moves that typical automata make:
a -> b
: write symbol and don’t movea -> b ^
: write symbol and move righta -> ^ b
: write symbol and move left& -> b
: push symbol on lefta -> &
: pop symbol on left
States and symbols¶
States and symbols can be:
A sequence of one or more letters, numbers,
_
, or.
One of the following:
|- -| # $
Tables¶
Tables are in CSV format.
The first column lists all the states, one per row. Precede the name
of the start state with >
, and precede the name of final states with
@
. These symbols are not part of the state name.
The first row lists all the possible left-hand sides of transitions, sans state.
Each interior cell contains a set of right-hand sides.
Thus, the left-hand side is formed by concatenating the row header (the state) and the column header; the right-hand side is taken from the cell.
Graphs¶
Graphs are in Trivial Graph Format (TGF).
The nodes are labeled with states, including the >
and @
flags as
described above.
The edges are labeled with transitions, minus the state on both the left-hand side and right-hand side.