Problem Solving in Automata, Languages, and Complexity

2.4 Converting an NFA to a DFA 51

a, c

(a)

C

8

a, c

m

Figure 2.32: Two NFA’s for Example 2.28.

Next, we define Q’ = {qa, qb, qC, qf } and a transition function 6’ : Q’ x C -+

2Q’ by letting qf E 6(q,, 2) for all x E C, and qa: E 6(q,, y) if x = IX: x y, for

x:, yt x f C. That is, we change state q9 in Figure 2.32(a) to state qf, and

reverse all arrows in Figure 2.32(a). Then, for each x E C, the DFA A4: =

(Q’, C> 6 qx, {qf)) accepts the set of all strings w over C having value(wR) =

X. Figure 2.32(b) shows the NFA AIL.

Now, the language L can be described as

(L(M,) n L(M;)) u @(Mb) n L(M;)) u @(MC) n L(M:,))-

In Section 2.3, we have seen that it is easy to construct an NFA to accept the

union or the concatenation of two languages accepted by two given NFA’s.

For the intersection of two languages, however, there is no simple way to do

it. Here, we are going to use the product automaton method introduced in

Section 2.2 to do it.

Let Q” = Q x Q’. To simplify the notation, we will write qUV to denote the

state [qU, qv] in Q”. Define 6” : Q” x C + Q” by

”

s (q uv, 4 = huZ I Qw = s(4u, x) and 42 E qqv, x)}*

We show the complete table for 6” in Figure 2.33. (Note that s”(q,f, y) = 8

for all x, y E C, and so we do not show them in the table.)

Then, for each x E {a, b, c}, the NFA Mt = (Q”, C, S”, qsx, {qxf}) accepts

the language L(Mx) n L(ML).

Now, toget anNFA accepting L(Mt)UL(ML’)UL(ML’), wecansimplyuse

three copies of Mt , Mi’, ML’ and add an initial state & with three E-transitions

from @” to the three initial states of the machines Mf, ML’, ML’. More pre-