1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

At this state the automaton checks that indeedthe symbol guessed does not occur in the string. If so, it ends up accepting.This automaton illustrates vividly the remarkable power of nondeterministic devices: they can guess and always be right, since one successful computation isall that is required for acceptance. As we shall see later in Section 2.5, anydeterministic finite automaton that accepts the same language must be far morecomplicated. <>A deterministic finite automaton is just a special type of a nondeterministicfinite automaton: In a deterministic finite automaton, it so happens that thetransition relation 6. is in fact a function from K x ~ to K.

That is, a nondeterministic finite automaton (K,~, 6, s, F) is deterministic if and only if thereare no transitions of the form (q,e,p) in 6., and for each q E K and a E ~ thereis exactly one p E K such that (q, a, p) E 6.. It is therefore evident that theclass of languages accepted by deterministic automata is a subset of the classof languages accepted by nondeterministic automata. Rather surprisingly, theseclasses are in fact equal. Despite the apparent power and generality enjoyed bynondeterministic automata, they are no more powerful than the deterministic2.2: Nondeterministic Finite Automata69ones in terms of the languages they accept: A nondeterministic finite automatoncan always be converted into an equivalent deterministic one.Formally, we say that two finite automata Ml and M2 (deterministic ornondeterministic) are equivalent if and only if L(M1 ) = L(M2).

Thus twoautomata are considered to be equivalent if they accept the same language, eventhough they may "use different methods" to do so. For example, the threeautomata in Figures 2-4-2-6 are all equivalent.Theorem 2.2.1: For each nondeterministic finite automaton, there is an equivalent deterministic finite automaton.Proof: Let M = (K,~, 6., s, F) be a nondeterministic finite automaton. Weshall construct a deterministic finite automaton M' = (K',~, s', F') equivalentto M. The key idea is to view a nondeterministic finite automaton as occupying,at any moment, not a single state but a set of states: namely, all the states thatcan be reached from the initial state by means of the input consumed thus far.Thus if M had five states {qO, ... , q4} and, after reading a certain input string,it could be in state qo, q2, or q3, but not ql, or q4, its state could be consideredto be the set { qo, q2, q3}, rather than an undetermined member of that set.

Andif the next input symbol could drive M from qo to either ql or q2, from q2 to qo,and from q3 to q2, then the next state of M could be considered to be the set{qo, ql , q2} .The construction formalizes this idea. The set of states of M' will be K' =2K , the power set of the set of states of M. The set of final states of M' willconsist of all those subsets of K that contain at least one final state of M. Thedefinition of the transition function of M' will be slightly more complicated.

Thebasic idea is that a move of M' on reading an input symbol a E ~ imitates amove of M on input symbol a, possibly followed by any number of e-moves ofM. To formalize this idea we need a special definition.For any state q E K, let E(q) be the set of all states of M that are reachablefrom state q without reading any input. That is,8:E(q)= {p E K:(q, e) I-~ (p, e)}.To put it otherwise, E( q) is the closure of the set {q} under the relation{ (p, r) : there is a transition (p, e, r) E 6.}.Thus, E(q) can be computed by the following algorithm:Initially set E(q) := {q};while there is a transition (p, e, r) E 6. with p E E( q)and r ~ E(q) do: E(q) := E(q) U {r}.70Chapter 2: FINITE AUTOMATAThis algorithm is a specialization of our general algorithm for closure computations (recall the last algorithm in Section 1.6) to the situation in hand. Itis guaranteed to terminate after at most IKI iterations, because each executionof the while loop adds another state to E(q), and there are at most IKI statesto be added.

We shall see many instances of such closure algorithms later.eFigure 2-9Example 2.2.3: In the automaton of Figure 2-9, we have E(qo)E(qt) = {ql,q2,q3}, and E(q2) = {q2}'O(K',= {qO, ql, q2, q3},We are now ready to define formally the deterministic automaton M'~, <5', s', F') that is equivalent to M. In particular,K' =2K,s' = E(s),F' = {Qand for each Q~~K: Q n FK and each symbol a E<5'(Q, a) = U{E(p) : pE K~,i= 0},defineand (q, a,p) E 6. for some q E Q}.That is, <5' (Q, a) is taken to be the set of all states of M to which M can go byreading input a (and possibly following several e transitions). For example, ifM is the automaton of Figure 2-9.

then S' = {qQ. qt. q2. q3}' Since the only transitionsfrom ql on input a are (ql,a,qo) and (ql,a,q4), it follows that <5'({qd,a) =E(qo) U E(q4) = {QO,Ql,Q2,q3,q4}.It remains to show that M' is deterministic and equivalent to M. Thedemonstration that M' is deterministic is straightforward: we just notice that<5' is single-valued and well defined on all Q E K' and a E ~, by the way it wasconstructed. (That <5'(Q,a) = 0 for some Q E K' and a E ~ does not mean <5' isnot well defined; 0 is a member of K'.)712.2: Nondeterministic Finite AutomataWe now claim that for any string w E(q,w)I-iw (p,e)~*and any states p.

qif and only if (E(q),w)EK.I-iw' (P,e)for some set P containing p. From this the theorem will follow easily: To showthat M and M' are equivalent, consider any string w E ~*. Then w E L(M)if and only if (s, w) I-iw (f, e) for some f E F (by definition) if and only if(E(s),w) I-iw' (Q,e) for some Q containing f (by the claim above); in otherwords, if and only if (s',w) I-iw' (Q,e) for some Q E F'. The last condition isthe definition of w E L(M').We prove the claim by induction on Iwl.Basis Step. For Iwl = 0 -that is, for w = e- we must show that (q, e) I-iw (p, e)if and only if (E(q), e) I-iw' (P, e) for some set P containing p. The first statementis equivalent to saying that p E E(q).

Since M' is deterministic, the secondstatement is equivalent to saying that P = E(q) and P contains p; that is,p E E(q). This completes the proof of the basis step.Induction Hypothesis. Suppose that the claim is true for all strings w of lengthk or less for some k~O.Induction Step.

We prove the claim for any string w of length k + 1. Let w = va,where a E ~, and v E ~*.For the only if direction, suppose that (q, w) I-iw (p, e). Then there arestates rl and r2 such that(q,w)I-iw (rl,a)I-M(r2,e)I-iw (p,e).That is, M reaches state p from state q by some number of moves during whichinput v is read, followed by one move during which input a is read, followed bysome number of moves during which no input is read.

Now (q,va) I-iw (rl,a) istantamount to (q,v) I-iw (rl,e), and since Ivl = k, by the induction hypothesis(E(q),v) I-iw' (RI,e) for some set RI containing rl· Since (rl,a) I-M (r2,e),there is a triple (rl,a,r2) E 6., and hence by the construction of M', E(r2) <:;;15'(R1 , a). But since (r2,e) I-iw (p,e), it follows that p E E(r2), and thereforep E 15'(R1,a). Therefore (Rl,a) I-M' (P,e) for some P containing p, and thus(E(q), va)I-iw' (Rl,a)I-M'(P,e).To prove the other direction, suppose that (E(q), va) I-iw' (RI, a) I- M' (P, e)for some P containing p and some Rl such that 15'(R1 , a) = P.

Now by thedefinition of 15', 15'(R I ,a) is the union of all sets E(r2), where, for some staterl E R 1 , (rl,a,r2) is a transition of M. Since pEP = 15'(R1 , a), there issome particular r2 such that p E E(r2), and, for some rl E R 1 , (rl,a,r2) isa transition of M. Then (r2, e) I-iw (p, e) by the definition of E(r2)' Also, bythe induction hypothesis, (q,v) I-iw (r i • e) and therefore (q,va) I-iw (rl,a) I-M(r2,e)I-iw (p,e).Chapter 2: FINITE AUTOMATA72This completes the proof of the claim and the theorem .•Example 2.2.4: The proof of Theorem 2.2.1 has the salutary property of beingconstructive, in that it provides an actual algorithm for constructing, startingfrom any nondeterministic finite automaton M, an equivalent deterministic M'.Let us apply this algorithm then to the nondeterministic automaton inFigure 2-9.

Since M has 5 states, M' will have 25 = 32 states. However, only afew of these states will be relevant to the operation of M' -namely, those statesthat can be reached from state s' by reading some input string. Obviously, anystate in K' that is not reachable from s' is irrelevant to the operation of M'and to the language accepted by it. We shall build this reachable part of M' bystarting from s' and introducing a new state only when it is needed as the valueof J'(q, a) for some state q E K' already introduced and some a E ~.We have already defined E(q) for each state q of M.

Характеристики

Список файлов решённой задачи