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

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 317

Fig. 12-8

12.17. Describe the wordswin the languageLaccepted by the automatonMin Fig. 12-9(a).

The system can reach the accepting states 2 only when there exists anainwwhich follows ab.

Fig. 12-9

12.18. Describe the wordswin the languageLaccepted by the automatonMin Fig. 12-9(b).

Eachainwdoes not change the state of the system, whereas eachbinwchanges the state fromRi,tosi+ 1

(modulo 4). Thuswis accepted byMif the numbernofb’s inwis congruent to 3 modulo 4, that is, where

n= 3 , 7 , 11 ,···.

12.19. SupposeLis a language overAwhich is accepted by the automatonM=(A,S,Y,s 0 ,F). Find an

automatonNwhich acceptsLC, that is, those words fromAwhich do not belong toL.

Simply interchange the accepting and rejecting states inMto obtainN. Thenwwill be accepted in the new machine

Nif and only ifwis rejected inM, that is, if and only ifwbelongs toLC. Formally,N=(A,S,S\Y, s 0 ,F).

12.20. LetM=(A,S,Y,s 0 ,F)andM′=(A, S′,Y′,S 0 ′,F′)be automata over the same alphabetAwhich

accept the languagesL(M)andL(M′)overA, respectively. Construct an automatonNoverAwhich

accepts preciselyL(M)∩L(M′).

LetS×S′be the set of states ofN. Let(s, s′)be an accepting state ofNif bothsands′are accepting states inM

andM′, respectively. Let (s 0 ,s′ 0 ) be the initial state ofN. Let the next-state function ofN,G:(S×S′)×A→(S×S′),

be defined by:

G((s, s′), a)=(F (s, a), F′(s′,a))

ThenNwill accept precisely those words inL(M)∩L(M′).