Example of an Automaton with Graphs

Example of an automaton FA(a1) with:

1. $Q = \{q_{0}, q_{1},q_{2},q_{3}, q_{4} \}$
2. $I = \{q_{0}\}$
3. $F = \{ q_{1},q_{3}\}$
4. $\Sigma = \{b,1,2,3,x,c,o,n,t \}$
5. $\Xi = \{t,1,2,3,e,n,d,x,c,o,n,t \}$
6. $\Delta = \{\langle q_{0},''b1'',''t1'' q_{1}\rangle, \langle q_{0},''b2'',''t2... ...''tendx'', q_{3}\rangle, \langle q_{4},''cont'',''tendcont'', q_{4}\rangle,\}$
7. $l = \{ (q_{0}, \{a,b,d,g \}), (q_{1}, \{a,d,e,f \}), (q_{2}, \{b,d,e \}), (q_{3}, \{c,d,f \}), (q_{4}, \{a,b,d,e,f \}) \}$
8. $AP = \{a,b,c,d,e,f,g \}$

The smallest set of possible runs (executions) $EXEC(a1)$ of this automaton is the set:

1. $\varrho_{1} = \{ (q_{0},''b1'') \}$
2. $\varrho_{2} = \{ (q_{0},''b2''),(q_{2},''x'') \}$
3. $\varrho_{3} = \{ (q_{0},''b3''),(q_{4},''cont''), ... \}$

This automaton $a1$ can be represented as a transition graph $TrG(a1) = g1$ as follows (cf. figure 5.2):

1. $V = \{q_{0}, q_{1},q_{2},q_{3}, q_{4} \}$
2. $\Sigma = \{b,1,2,3,x,c,o,n,t \}$
3. $\Xi = \{t,1,2,3,e,n,d,x,c,o,n,t \}$
4. $E = \{\langle q_{0},''b1'',''t1'' q_{1}\rangle, \langle q_{0},''b2'',''t2'', q... ...''tendx'', q_{3}\rangle, \langle q_{4},''cont'',''tendcont'', q_{4}\rangle,\}$
5. $l = \{ (q_{0}, \{a,b,d,g \}), (q_{1}, \{a,d,e,f \}), (q_{2}, \{b,d,e \}), (q_{3}, \{c,d,f \}), (q_{4}, \{a,b,d,e,f \}) \}$
6. $AP = \{a,b,c,d,e,f,g \}$

Figure 5.2: Transition graph of the example automaton with properties and inputs-outputs

Remark: Another way to represent an automaton is by giving the transition table based on the transition function $\Delta$. The columns are presenting the different states Q, the rows representing the different input symbols $\Sigma$ and the crossing cells of the table represent the follow up state from Q.

Remark: In the specification of the finite automaton a1 given above nothing is explicitly said about the behavior of the automaton, if in a certain state $q$ an input occurs, which is an element of the alphabet $\Sigma$, but which is not an defined input event for state $q$. In case of an empty input $\epsilon$ the automaton would stay in its state, but in case of a non-empty but not allowed input this specification is incomplete. For a real instantiation of such an automaton one has exlicitely to elaborate also these cases.

The transition graph $g1$ can be translated into an execution graph $ExG(a1) = g2$ as follows (cf. figure 5.3):

Figure 5.3: The execution graph of the automaton example

1. By definition: $\hat V = \{(q_{0},0) \}$
2. The set of all successors = $\{q_{1}, q_{2},q_{4}\}$
3. $\hat V \cup \{(q_{1},1), (q_{2},1),(q_{4},1)\}$
4. The set of all successors = $\{q_{3}, q_{4}\}$
5. $\hat V \cup \{ (q_{3},2),(q_{4},2)\}$
6. The set of all successors = $\{q_{4}\}$
7. $\hat V \cup \{ (q_{4},3)\}$
8. The run with $q_{4}$ can go forever.