ANML Documentation

Automata Versus Traditional State Machines

Figure 1 shows an example of a traditional state machine that processes text. The machine detects if a string of characters ends in a, b, or c. (The end of the string is denoted by a # character.)

Figure 1. Traditional State Machine
Overview state machine

This state machine contains seven states: start, 1, 2, 3, a, b, and c. The machine starts on the start state. It receives input with the set of characters [a,b,c,#] and transitions on a, b, c, or #. The three final states are a, b, and c.

The process of creating an equivalent automaton starts with Figure 2, which shows the states of the automaton.

Figure 2. Example State Machine as an Automaton
Automata state machine automata labeled

This automaton contains six state transition elements (STEs). In automata computing, the STE is the entity that stores the state of the machine.

One STE exists for each state. (Note the start state does not have its own STE; start and final states are defined differently in automata and are explained in more detail later in this section.)

STEs are programmed to recognize specific symbols and are connected to each other by transitions, which denote activation connections and transition paths. In Figure 3, symbol assignments have been made to the STEs and transitions have been added.

Figure 3. Automaton with Symbol Assignments and Transitions
Automata state machine automata 2

The transitions emanating from an STE indicate the nodes that will be activated for processing the next character, if the source STE matches the current input symbol.

Automata do not have start and final states in the traditional sense, but they do have equivalent constructs (start and report indicators). When these constructs are added, the automaton appears as follows:

Figure 4. Automaton with Start and Final Indicators
Automata state machine automata 3

STEs 1, 2, and 3 each contain an indicator in the top left corner containing the number 1. Similar to the start state in traditional state machines, this indicates each of these nodes will process the first symbol in the data stream. It is assumed the input sequence will start with either a, b, or c, and one of these three nodes will match the first symbol.

STEs a, b, and c each contain an indicator in their lower right corner with the character R. This is the report indicator (similar to the final state in a traditional state machine). When one of these nodes matches a symbol in the input, the node will generate a report event. This report event will contain the identifier of the node that generated it. Given the identifier from the report event, one can determine which symbol was at the end of the sequence of symbols.

Figure 5. State Machine vs. Automaton Network
Automata comparison

Table 1. State Machine Functions vs. Automata Functions
Traditional State Machine Automata
State State transition element (STE)
Start states STE start indicators
Transitions Activation connections and STE recognition symbols
Final states Reporting elements