Generalised non-deterministic finite automaton

A generalised non-deterministic finite automaton, GNFA for short, is a non-deterministic automaton whose transitions can be labelled not just with symbols of the alphabet but with regular expressions.

Definition

We will need a GNFA in the algorithm for converting a finite automaton to a regular expression. A GNFA is thus an NFA whose transitions are defined by regular expressions. An example of such a GNFA:

We can see, for example, that there is a transition from state q₂ to state q_f labelled with the regular expression a^∗ b. The further requirements on a GNFA are:

• The start state q₀ must have a transition to every other state. In the diagram we can see that transitions lead from q₀ to all the other states.
• A GNFA has exactly one accept state, and every other state has a transition to it. As the diagram shows, every state has an arrow pointing to q_f.
• The start state must not be the same as the accept state. So a GNFA has at least two states.
• Every other state, apart from the start and accept states, must have transitions to all the other states except the start and accept states. This includes loops (a transition from state q_i to state q_i).

Converting an ordinary NFA to a GNFA

If we have some NFA, converting it to a GNFA is simple.

1. Create a new start state q_s and add an epsilon transition to the original start state.
2. Create a new accept state q_f and add epsilon transitions to q_f from all the original accept states. The original accept states become ordinary states.
3. If there is a multiple transition anywhere (that is, if we can get from state q₁ to state q₂ both on symbol 0 and on symbol 1), we merge these rules into a single regular expression and join all the original symbols with the union operator (that is, we label the arrow with the regular expression 0|1).
4. If the automaton is missing a transition that should be there according to the definition, we create it and label it with the regular expression ∅. This does not change the language the automaton accepts, because such a transition can never be taken.

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