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.
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
- Write the NFA as transition
f( (q1), a ) -> q1 f( (q1), a ) -> q2 f( (q1), b ) -> q1 f( q2 , b ) -> q3 f( q3 , b ) -> (q4)
- 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)
- 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)
- 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)
- 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 ) -> ()
- 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"/>