Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 233

l The regular expression for the incoming arc from state 2 to 3 on symbol 0 is 0 and the
regular expression for the outgoing arc from state 3 to 1 on symbol 0 is again 0. The
regular expression for the path 3 → 2 → 3 is 1. 0 and also with the possibility of zero/
more repetitions of this path will have the regular expression (1. 0) followed by the
regular expression 0 for an out going arc from state 3 to 1. Hence, the regular expres-
sion will be 0 .(1. 0 ) 0.
Now these two regular expressions can be equivalently expressed by the regular expres-
sion 0.(1. 0 )* 0. So we have the remaining states of DFA which is looking as,

1

2

1 0

0.(1.0)*0 +r.(1.0)*0

(Now eliminate the state 2)

After elimination of state 2 we obtain the equivalent regular expression 0 [0. (1. 0 )* 0

+ r. (1. 0 )* 0]. And finally DFA has remaining state 1, shown below.

1

1

0[0.(1.0)*0 +r.(1.0)*0]

l The regular expression for repetition arc on state 1 over symbol 1 is 1 *, and

l The regular expression for another repetition arc on state 1 is 0 [0. (1. 0 )*. 0 + r. (1.

0 )* 0]. Therefore the final regular expression is union of them i.e.,

1* + 0 .[0. (1. 0)* 0 + r. (1. 0)* 0]

Substitute the value of r thus we obtain the final regular expression

1* + 0 .[0. (1. 0)* 0 + 1. 0* 1 (1. 0)* 0]

9.6 Finite Automatons with Output.....................................................................................

In the previous chapter of finite automata we have discussed in detail the deterministic and

nondeterministic nature of finite automata. The behaviors of these automatons are defined by

the nature of the input strings accepted by them. That is, after processing the input string

automaton generates the output in the form of decisions i.e., either accepted if automaton

reaches to its final state/s or rejected if automaton never reaches to its final state/s. (Fig. 9.22)

So, the nature of language which is accepted by the finite automaton designates the power of

such finite automaton.

Finite

Automata

Accepted

Rejected

Input

String

Fig. 9.22