Mathematical Foundation of Computer Science

DHARM

224 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

(For the acceptance of the string 0011)

Since, at state E return string is 001, then for next symbol 1 automaton reaches to final

state. Hence state E connected to B by transition arc over symbol 1.

(^0) D E
1
A
B
C
1
0
0011
000001
1
(Acceptance of the string formed over {00,001} followed by 1)
For repetitions of substring 00 one/more times, clearly an arc from state D comes back
to C on symbol 0 such that return symbols at D are multiple of 00.
(^0) D E
1
A
B
C
1
0
0011
0 00/0000 001/00001
1
0
(For repetition of 001 one/more times)
From state E (return symbols 001) an arc connected to C on symbol 0.
(^0) D E
1
A
B
C
1
0
0011
00/0000 001/00001
1
0
0
Therefore, from the starting state A over symbol 1, automaton reaches to B and halt.
There is no further possibility of acceptance of symbols {0, 1} from B onwards hence; we show
the transition on these symbols from B goes to state Φ. Further, no string starting with symbol
0 followed any symbol 1 is in language so it reaches to state Φ. Therefore we obtain the required
DFA shown in Fig. 9.7.