Problem Solving in Automata, Languages, and Complexity

26 FINITE AUTOMATA

Figure 2.3: DFA of Example 2.4.

will accept the input string. (We call such a state a success state.) From these

observations, we see that L(M) consists of the string^0 (which ends at state

qi) and all strings starting with 00. In the regular expression notation,

L(M) = 0 + oo(0 + 1>*. cl

Example 2.4 What is the language L(M) accepted by the DFA M of Figure

2.3?

Solution. Similar to Example 2.3, q6 is a failure state and 43 is a success state.

So, we only need to figure out how we can reach 43 from 40. There are three

kinds of paths from qo to 43:

They correspond with strings beginning with Oll*O, 000* 1 and lOO* 1, respec-

tively. So,

L(M) = (o11*0 + 000*1+ 1oo*1)(0 + 1>*.^0

Example 2.5 What is the language L(M) accepted by the DFA M of Figure

2.4?

Solution. A string IX: accepted by M is either in 0* (so, M never leaves state
qo), or is associated with a computation cycle from qo to qo, passing through
states ql, q2,q3, q4 for a finite number of times. Note that the DFA M changes
from a state qi, 0 < - i < - 3, to a new state qi+l (or from q4 to qo) if and only if
it reads a symbol 1. Thus, each time M goes from state qo to states 41,... , q4