ANML Documentation

Deterministic and Non-Deterministic Finite Automata

As discussed earlier, automata are non-deterministic, meaning multiple states can be active at the same time.

To illustrate this principle, the figures in this section compare an automaton network (built in the AP workbench) with a classical non-deterministic automata and a deterministic automata.

The example automata identify words I, ice, it, in, and to.

Figure 1. ANML Example
Ste abblnfa

Figure 2. NFA Example
Ste abbnfa

Figure 3. DFA Example
Ste abbdfa

Converting From NFA to ANML

In classical NFA, each edge transition

# Write all transitions in the following form f(source_state, input_symbol)!destination_state

If source_state is a start state enclose it in parentheses, (source_state) If destination_state is an accept state enclose it in parentheses, destination_state)

# Combine all transition statements where f(source_state, input_symbol) is identical and destination_states are of the same type (either not accept state or accept state) into a single statement with multiple destination_states. If f(source_state, input_symbol) is identical but one transition statement points to an accept state and another to a not accept state, the transitions statements should not be combined and an additional source_state will be added in the next step. For example, the following three statements are combined into a single statement:

f(source_state, input_symbol) -> destination_state1 f(source_state, input_symbol) -> destination_state2 f(source_state, input_symbol) -> destination_state3

f(source_state, input_symbol) -> destination_state1, destination_state2,destination_state3

# For all transition statements where source_state is identical and the input_symbol is different, the source_state in each statement should be postpended by an incrementing count value in each successive transition statement. If the source_state was enclosed in parentheses, each rewritten source_state should also be enclosed in parentheses.

f(source_state, input_symbol1) -> destination_state f(source_state, input_symbol2) -> destination_state

The statements would be modified into two new transition statements:

f(source_state_0, input_symbol1) -> destination_state f(source_state_1, input_symbol2) -> destination_state

# The destination_states with value equal to the source_states modifed in the prior step should be changed to match the value of the new source_states, creating multiple destination_states for those transition statements which are modified. For example:

source_statex = destination_statey

and source_statex was changed in two transition statements to source_statex_0 and source_statex_1

therefore, everywhere that destination_statey occurs should be changed to the two destinations with the values of source_statex_0 and source_statex_1

# If a destination_state is also never a start_state, it does not match an input_symbol and can be removed from the transition expression. If such a destination_state is also an accept state the destination_state value should be removed but the empty parentheses retained.

# Each transition statement will now become one ANML state transition element where the symbol-set attribute value is the input_symbol containing one activate-on-match element for each destination_state. The id attribute of the statetransition- element should be the source_state value, and if the source_state is in parentheses, the attribute and attribute value start="start-of-data" should be included in the state transition element.

If the destination_state of the transition statement is enclosed in parentheses, the attribute and attribute value output="enabled" should be included in its state transition element, including empty destination_states created on the prior step. If, after removal of destination_states in the prior step there are no destination_states in a particular transition expression, there will be no activate-on-match elements nested in the state transition element.

Example: NFA-to-ANML Conversion


Ste abbnfa conv

  1. Write the NFA as transition expressions:

    f( (q1), a ) -> q1 f( (q1), a ) -> q2 f( (q1), b ) -> q1 f( q2 , b ) -> q3 f( q3 , b ) -> (q4)

  2. Combine transition expressions with the same source_state, input_symbol:

    f( (q1), a ) -> q1 , q2 f( (q1), b ) -> q1 f( q2 , b ) -> q3 f( q3 , b ) -> (q4)

  3. Rewrite source_state names to uniquely identify by input_symbol processed:

    f( (q1-0), a ) -> q1 , q2 f( (q1-1), b ) -> q1 f( q2 , b ) -> q3 f( q3 , b ) -> (q4)

  4. Rewrite destination_state names corresponding to the changes made to source_state:

    f( (q1-0), a ) -> q1-0 , q1-1 , q2 f( (q1-1), b ) -> q1-0, q1-1 f( q2 , b ) -> q3 f( q3 , b ) -> (q4)

  5. Remove destination_states that are never start_states:

    f( (q1-0), a ) -> q1-0 , q1-1 , q2 f( (q1-1), b ) -> q1-0, q1-1 f( q2 , b ) -> q3 f( q3 , b ) -> ()

  6. Each transition expression now describes an ANML state transition element:

    <state-transition-element aid="q1-0" symbol-set="a" start="start-of-data"> <activate-on-match element="q1-0"/> <activate-on-match element="q1-1"/> <activate-on-match element="q2"/> </state-transition-element> <state-transition-element aid="q1-1" symbol-set="b" start="start-of-data"> <activate-on-match element="q1-0"/>