Problem Solving in Automata, Languages, and Complexity

52 FINITE AUTOMATA

6”

%a

qsb

4sc

4aa

qab

Qac

@a

qbb

qbc

4ca

qcb

4cc

ro41

b

140 >

(qbd {A

ab b&f, qbc) bIba}

{%a~ qac) {qbb} (4cf 7 %xJ

hf 1 {%-ii (abb)

{Qcb) hbf 7 qac) {!&a)

{%a~ !kc) {qab} b&f, t&c)

bf 1 i&d hhd

hd (4cf 9 !kc} {qua}

{@a, qbc) (qcb} {Cbf 7 4ac)

{Qcf 1 {Qba) {Qcb)

{qcb) b&f 7 qbc) {%a)

{&a 7 !kc) {qbb) {acf j accl

Figure 2.33: The transition function 6”.

cisely, the required NFA can be described as E = (0, C, S, &, {qtf, qkf, q,Cf }),
where
6 = {c&t, I t E {a, hch quv E Q”) u {CL),
and

‘(fS,&) = {a,“,, qfby q,“,}?

• t
  s(Q uv,x) = {q;,^1 qwz E ~“(quv,x)}r for quv E Q”,+ E {O,c). •I

Exercise 2.4

1. Convert each of the following NFA’s into an equivalent DFA:

(a) The NFll M = ({P, 4, r, 1, {O,l}, 4 P, {CL cl), with

(b) The NFA M of Figure 2.27(a).

(c) The NFA A4 of Figure 2.27(b).

(d) The NFA M of Figure 2.27(c).

2. For each of the following languages, construct a DFA that accepts the
   language:
   (a) The set of binary strings that contain both substring 010 and
   substring 101.