Discrete Algebraic Methods

□

Generalizing nondeterministic automata, we now allow rational sets as labels. An M-automaton with rational labels is a tuple A = (Q, δ, I, F), where Q, I, F are have the same meaning as in the definition of nondeterministic automata and δ is a subset of Q×RAT(M)×Q. A run ofAis a sequence of the form q0u1q1 ⋅⋅ ⋅ unqn with qi ∈ Q, ui ∈ M and for all i ∈ {1, . . . , n} there is a transition (qi−1, Li , qi)∈ δ with ui ∈ Li. Accepting runs and the accepted set L(A) of A are defined as above. As before, A is called finite if δ is a finite set. Of course, this does not mean that a rational set L ∈ RAT(M) which occurs as a label of a transition has to be finite.

Next, we want to show that nondeterministic automata accept rational sets. We do so by ...