Transition function of the generalized nondeterministic finite automata

Question

Why does the transition function of a GNFA map from two states to a regular expression $$ \delta: (Q \setminus \{q_{start}\}) \times (Q \setminus \{q_{accept}\}) \to R $$ instead of mapping from the current state and the regular expression to the next state?

Answer 1

It seems to be part of a normalization for the sake of convenience. The traditional definition would work as well.

Citing from [HanWood2004] "The Generalization of Generalized Automata: Expression Automata"

Definition 2. An expression automaton A is specified by a tuple $(Q, \Sigma, \delta, s, f )$ , where $Q$ is a finite set of states, $\Sigma$ is an input alphabet, $\delta \subseteq Q \times R_\Sigma \times Q$ is a finite set of expression transitions, where $R_\Sigma$ is the set of all regular expressions over $\Sigma$, $s \in Q$ is the start state and $f \in Q$ is the final state. (Note that we need only have one final state.) We require that, for every pair $p$ and $q$ of states, there is exactly one expression transition $(p, \alpha, q ) \in δ$ , where $\alpha$ is a regular expression over $\Sigma$ .

So this early GNFA definition starts with the traditional specification of the transition function as relation from state $p$ via regular expression $\alpha$ to state $q$.

The next paragraph in that paper is (boldface added by me):

We can also use the functional notation $\delta : Q × Q \to R_\Sigma$ that gives the equivalent representation. An expression transition $( p, α, q )$ gives $\delta( p, q )= \alpha$ . Note that $\delta$ contains exactly $|Q|^2$ transitions, one transition for each pair of states, and whenever $( p,\emptyset,q )$ is in $\delta$, for some $p$ and $q$ in $Q$ , $A$ cannot move from $p$ to $q$ directly.

We note that this functional notation ($\delta$ is a function, not a relation) only allows for one expression transition from $p$ to $q$ via the regular expression $\alpha$ simply because functions are single-valued. Thus the requirement at the end of definition 2 above can be dropped.

This convenience might explain the use of the functional notation. To cite [Sipser2006] p. 70:

For convenience we require that GNFAs always have a special form that meets the following conditions.

• The start state has transition arrows going to every other state but no arrows coming in form any other state.

• There is only a single accept state, and it has arrows coming in from every other state but no arrows going to any other state. Furthermore, the accept state is not the same as the start state.

• Except for the start and accept states, one arrow goes from every state to every other state and also from each state to itself.

References:

[HanWood2004] Yo-Sub Han and Derick Wood. "The Generalization of Generalized Automata: Expression Automata." In: 9th International Conference on Implementation and Application of Automata, CIAA 2004, Kingston, Canada, July 22–24, 2004, Revised Selected Papers, LNCS 3317, pp. 156–166.

[Sipser2006] Michael Sipser. 2006. Introduction to the Theory of Computation (2nd ed.). International Thomson Publishing.