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

316 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12

12.12. LetA={a, b, c}and letw=abc. State whether or notwbelongs toL(r)where:

(a) r=a∗∨(b∨c)∗; (b) r=a∗(b∨c)∗.

(a) No. HereL(r)consists of word inaor words inbandc.

(b) Yes, sincea∈L(a)∗andbc∈(b∨c)∗.

12.13. LetA={a, b}. Find a regular expressionrsuch thatL(r)consists of all wordswwhere:

(a)wbegins witha^2 and ends withb^2 ;(b)wcontains an even number ofa’s.

(a Letr=a^2 (a∨b)∗b^2. (Note(a∨b)∗consists of all words onA.)

(b) Notes=b∗ab∗ab∗consists of all words with exactly twoa’s. Then letr=s∗=(b∗ab∗ab∗)∗.

FINITE AUTOMATA

12.14. LetMbe the automaton with the following input setA, state setSwith initial states 0 , and accepting

(“yes”) state setY:

A={a, b},S={s 0 ,s 1 ,s 2 },Y={s 2 }

Suppose next state functionFofMis given by the table in Fig. 12-7(a).

(a) Draw the state diagramD=D(M)ofM.

(b) Describe the languageL=L(M)accepted byM.

(a) The state diagramDappears in Fig. 12.7(b). The vertices ofDare the states, and a double circle indicates an

accepting state. IfF(sj,x)=sk, then there is a directed edge fromsjtosklabeled by the input symbolx. Also,

there is a special arrow which terminates at the initial states 0.

(b) L(M)consists of all wordswwith exactly oneb. Specifically, if an input wordwhas nob’s, then it terminates in

s 0 and ifwhas two or moreb’s then it terminates ins 2. Otherwisewterminates ins 1 , which is the only accepting

state.

Fig. 12-7

12.15. LetA={a, b}. Construct an automatonMwhich will accept precisely those words fromAwhich have

an even number ofa’s. For example,aababbab,aa,bbb,ababaawill be accepted byM, butababa,aaa,

bbabbwill be rejected byM.

We need only two states,s 0 ands 1. We assume thatMis in states 0 ors 1 according as the number ofa’s up to

the given step is even or odd. (Thuss 0 is an accepting state, buts 1 is a rejecting state.) Then onlyawill change the

state. Also,s 0 is the initial state. The state diagram ofMis shown in Fig. 12-8(a).

12.16. LetA={a, b}. Construct an automatonMwhich will accept those words fromAwhich begin with an

afollowed by (zero or more)b’s.

The automatonMappears in Fig. 12-8(b).