Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 307

Such an automatonMis denoted byM=(A,S,Y,s 0 ,F)when we want to indicate its five parts. (The
plural of automaton isautomata.)
Some texts define the next-state functionF :S×A→Sin (5) by means of a collection of functions
fa:S→S, one for eacha∈A. SettingF(s,a)=fa(s)shows that both definitions are equivalent.

EXAMPLE 12.4 The following defines an automatonMwith two input symbols and three states:

(1)A={a, b}, input symbols.

(2)S={s 0 ,s 1 ,s 2 }, internal states.

(3)Y={s 0 ,s 1 }, “yes” states.

(4)s 0 , initial state.

(5) Next-state functionF:S×A→Sdefined explicitly in Fig. 12-1(a)or by the table in Fig. 12-1(b).

Fig. 12-1

State Diagram of an AutomatonM

An automatonMis usually defined by means of its state diagramD=D(M)rather than by listing its five
parts. The state diagramD=D(M)is a labeled directed graph as follows.

(1) The vertices ofD(M)are the states inSand an accepting state is denoted by means of a double circle.

(2) There is an arrow (directed edge) inD(M)from statesjto statesklabeled by an inputaifF(sj,a)=skor,

equivalently, iffa(sj)=sk.

(3) The initial states 0 is indicated by means of a special arrow which terminates ats 0 but has no initial vertex.

For each vertexsjand each letterain the alphabetA, there will be an arrow leavingsjwhich is labeled
bya; hence the outdegree of each vertex is equal to number of elements inA. For notational convenience, we
label a single arrow by all the inputs which cause the same change of state rather than having an arrow for each
such input.

The state diagramD=D(M)of the automatonMin Example 12.4 appears in Fig. 12-2. Note that botha
andblabel the arrow froms 2 tos 2 sinceF(s 2 ,a)=s 2 andF(s 2 ,b)=s 2. Note also that the outdegree of each
vertex is 2, the number of elements inA.