Generalized non-deterministic finite automaton

A generalized nondeterministic finite automaton, abbreviated ZNKA, is a nondeterministic automaton that may not only have symbols from the language in the transitions, but may have a regular expression there.

Definition

We will need ZNKA during the algorithm to convert a finite automaton to a regular expression. Thus ZNKA is an NKA that has transitions defined by regular expressions. Example of such a ZNKA:

We can see that, for example, the transition from the state q₂ leads to the state q₃ and is denoted by the regular expression $a^\ast b$. Other requirements for ZNKA:

• The initial state q₀ must have a transition to all other states. In the figure we see that from the state q₀ there are transitions to all other states.
• There is only one end state in ZNKA and all other states have a transition to this state. As can be seen in the figure, all states have an arrow pointing to q_f.
• The initial state must not be the same as the end state. Thus, ZNKA can have at least two states.
• All other states, except the initial and final states, must have transitions to all other states except the initial and final states. Including loops (transition from state q_i to state q_i).

Conversion of normal NKA to ZNKA

If we have an NKA, the conversion to ZNKA is straightforward.

1. We create a new initial state q_s and create an epsilon transition to the original initial state.
2. We create a new end state q_f and make epsilon transitions from all the original end states to the state q_f. From the original end states, we make normal states.
3. If there are multiple transitions somewhere (i.e., if we get from the state q₁ to the state q₂ via symbol 0 and via symbol 1), we merge these rules into a single regular expression and concatenate all the original symbols with the union operator (i.e., we mark the arrow with the regular expression 0|1).
4. If the automaton is missing a transition that by definition should be there, we create it and mark it with the regular expression ∅. This does not change the language that the automaton accepts, because such a transition is never made.

We can use this automaton to convert the automaton to a regular expression.