308 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12
Fig. 12-2LanguageL(M)Determined by an AutomatonM
Each automatonMwith input alphabetAdefines a language overA, denoted byL(M), as follows.
Letw=a 1 a 2 ···ambeaword onA. Thenwdetermines the following path in the state diagram graph
D(M)wheres 0 is the initial state andF(si− 1 ,ai)=sifori≥1:
P =(s 0 ,a 1 ,s 1 ,a 2 ,s 2 ,···,am,sm)We say thatMrecognizesthe wordwif the final statesmis an accepting state inY. The languageL(M)ofMis
the collection of all words fromAwhich are accepted byM.
EXAMPLE 12.5 Determine whether or not the automatonMin Fig. 12-2 accepts the words:
w 1 =ababba; w 2 =baab; w 3 =lthe empty word.Use Fig. 12-2 and the wordsw 1 andw 2 to obtain the following respective paths:P 1 =s 0
a
→s 0
b
→s 1
a
→s 0
b
→s 1
b
→s 2
a
→s 2 and P 2 =s 0
b
→s 1
a
→s 0
a
→s 0
b
→s 1The final state inP 1 iss 2 which is not inY; hencew 1 is not accepted byM. On the other hand, the final state in
P 2 iss 1 which is inY; hencew 2 is accepted byM. The final state determined byw 3 is the initial states 0 since
w 3 =lis the empty word. Thusw 3 is accepted byMsinces 0 ∈Y.
EXAMPLE 12.6 Describe the languageL(M)of the automatonMin Fig. 12-2.
L(M)will consist of all wordswonAwhich do not have two successiveb’s. This comes from the following
facts:
(1) We can enter the states 2 if and only if there are two successiveb’s.(2) We can never leaves 2.(3) The states 2 is the only rejecting (nonaccepting) state.The fundamental relationship between regular languages and automata is contained in the following theorem
(whose proof lies beyond the scope of this text).
Theorem 12.2 (Kleene): AlanguageLover an alphabetAis regular if and only if there is a finite state automaton
Msuch thatL=L(M).
The star operationL* on a languageLis sometimes called the Kleene closure ofLsince Kleene first proved
the above basic result.
EXAMPLE 12.7 LetA={a, b}. Construct an automatonMwhich will accept precisely those words fromA
which end in twob’s.