1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 17
Текст из файла (страница 17)
Since s' = E(qo) ={qo, ql , q2, (j3 },(ql,a,qO), (ql,a,q4), and (q3,a,q4)are all the transitions (q, a,p) for some q E s'. It follows thatSimilarly,are all the transitions of the form (q, b,p) for some q Es', soRepeating this calculation for the newly introduced states, we have the following.J' ({qo, ql , q2, q3, q4}, a)J'( {qO, ql, q2, q3, q4}, b)J'({q2,q3,q4},a)J'({q2,q3,q,J},b)= {qo, ql , q2, q3, q4},= {q2, q3, q4},= E(q4) = {q3,q4},= E(q4) = {q3,q4}.Next,J'({q3,q4},a) = E(q4)J'({q3,q4},b) = 0,= {q3,q4},and finallyJ'(0,a) = J'(0,b) = 0.The relevant part of M' is illustrated in Figure 2.10.
F', the set of final states,contains each set of states of which (j4 is a member, since q4 is the sole member732.2: Nondeterministic Finite AutomatabFigure 2-10of F; so in the illustration, the three states {qo, ql, q2, q3, q4}, {q2, Q3, Q4}, and{Q3,Q4} of M' are final.OExample 2.2.5: Recall the n + I-state nondeterministic finite automaton inExample 2.2.2 with ~ = {aI, ... ,an} for accepting the language L = {w E ~* :there is a symbol ai E ~ that does not occur in w}. Intuitively, there is no wayfor a deterministic finite automaton to accept the same language with so fewstates.Indeed, the construction is in this case exponential.
The equivalent deterministic automaton M' has as initial state the set s' = E( s) = {s, Ql, Q2, ... , Qn}.Even in this case, M' has several irrelevant states -in fact, half of the statesin 2K are irrelevant. For example, state {s} cannot be reached from s'; neithercan any state that contains some Qi but not s. Alas, these are all the irrelevantstates: as it turns out, all the remaining 2n states of K' -that is to say, allstates of the form {s} U Q for some nonernpty subset Q of {Ql, ... ,Qn}- arereachable from s'.One might hope, of course, that other kinds of optimizations may reducethe number of states in M'.
Section 2.5 contains a systematic study of suchoptimizations. Unfortunately, it follows from that analysis that in the presentcase of automaton M', the exponential number of states in M' is the absoluteminimum possible.OProblems for Section 2.22.2.1. (a) Which of the following strings are accepted by the nondeterministicfinite automaton shown on the left below?(i) a(ii)aa74Chapter 2: FINITE AUTOMATA~ISlb0baa(iii) aab(iv) e(b) Repeat for the following strings and the nondeterministic finite automaton on the right above:(i) e(ii) ab(iii) abab(iv) aba(v) abaa2.2.2. Write regular expressions for the languages accepted by the nondeterministic finite automata of Problem 2.2.1.2.2.3. Draw state diagrams for nondeterministic finite automata that accepts theselanguages.(a) (ab)* (ba)* U aa*(b) ((ab U aab)*a*)*(c) ((a*b*a*)*b)*(d) (baUb)*U(bbUa)*2.2.4.
Some authors define a nondeterministic finite automaton to be a quintuple(K,~, 6., S, F), where K,~, 6." and F are as defined and S is a finite setof initial states, in the same way that F is a finite set of final states. Theautomaton may nondeterministically begin operating in any of these initialstates.(a) Show that the language L ~ {a 1, ... , an} * consisting of all stringsthat are missing at least one symbol (recall Example 2.2.2) would beaccepted by such an automaton with n states ql, ... , qn, all of whichare both final and initial, and the transition relation 6. = {(qi,aj,qi) :ii=j}.(0) Explain why this definition is not more general than ours in any significant way.2.2.5. Dy what sequences of steps, other than the one presented in Example 2.2.1,ran the nondeterministic finite automaton of Figure 2-7 accept the inputbababab?2.2.6.
(a) Find a simple nondeterministic finite automaton accepting (ab U aab Uaba)* .2.3: Finite Automata and Regular Expressions75(b) Convert the nondeterministic finite automaton of Part (a) to a deterministic finite automaton by the method in Section 2.2.(c) Try to understand how the machine constructed in Part (b) operates.Can you find an equivalent deterministic machine with fewer states?2.2.7. Repeat Problem 2.2.6 for the language (a U b)*aabab.2.2.8. Repeat Problem 2.2.6 for the language (a U b)*a(a U b)(a U b)(a U b)(a U b).2.2.9. Construct deterministic finite automata equivalent to the nondeterministicautomata shown below.2.2.10. Describe exactly what happens when the construction of this section isapplied to a finite automaton that is already deterministic.2.3FINITE AUTOMATA AND REGULAR EXPRESSIONSThe main result of the last section was that the class of languages acceptedby finite automata remains the same even if a new and seemingly powerfulfeature ~nondeterminism~ is allowed.
This suggests that the class of languagesaccepted by finite automata has a sort of stability: Two different approaches,one apparently more powerful than the other, end up defining the same class.In this section we shall prove another important characterization of this class oflanguages, further evidence of how remarkably stable it is: The class oflanguagesaccepted by finite automata, deterministic or nondeterministic, is the same as theclass of regular languages ~those that can be described by regular expressions,recall the discussion in Section 1.8.We have introduced the class of regular languages as the closure of certainfinite languages under the language operations of union, concatenation, andKleene star.
We must therefore start by proving similar closure properties ofthe class of languages accepted by finite automata:Theorem 2.3.1: The class of languages accepted by finite automata is closedunderChapter 2: FINITE AUTOMATA76(a) union;(b) concatenation;(c) Kleene star;(d) complementation;(e) intersection.Proof: In each case we show how to construct an automaton M that acceptsthe appropriate language, given two automata Ml and M2 (only Ml in the casesof Kleene star and complementation).(a) Union.
Let Ml = (Kl,~,6.1,Sl,Fd and M2 = (K2,~,6.2,S2,F2) be nondeterministic finite automata; we shall construct a nondeterministic finite automaton M such that L(M) = L(MdUL(M2). The construction of M is rathersimple and intuitively clear, illustrated in Figure 2-11. Basically, Muses nondeterminism to guess whether the input is in L(Ml) or in L(M2), and thenprocesses the string exactly as the corresponding automaton would; it followsthat L(M) = L(Md U L(M2). But let us give the formal details and proof forthis case.@MFigure 2-11Without loss of generality, we may assume that Kl and K2 are disjoint sets.Then the finite automaton M that accepts L(Ml) U L(M2) is defined as follows772.3: Finite Automata and Regular Expressions(see Figure 2-11): M =(K,~,~,s, F), where s is a new state not in K1 or K 2 ,K = K1 U K2 U is},F= F1 U F 2 ,~ = ~1 U ~2 U{(s,e,sl),(s,e,s2)}'That is, M begins any computation by nondeterministically choosing to entereither the initial state of M1 or the initial state of M 2 ,and thereafter, M imitateseither M1 or M 2.
Formally, ifw E ~*, then (s,w) ~M (q,e) for some q E F ifand only if either (Sl'W) ~Ml (q,e) for some q E F l , or (S2> w) ~M2 (q,e) forsome q E F2. Hence M accepts w if and only if M1 accepts w or M2 accepts w,and L(M) = L(Md U L(M2).(b) Concatenation. Again, let M1 and M2 be nondeterministic finite automata;we construct a nondeterministic finite automaton M such that L(M) = L(Md 0L(M"2) The construction is shown schematically in Figure 2-12; M now operatesby simulating M1 for a while, and then "jumping" nondeterministically from afinal state of M1 to the initial state of M 2.
Thereafter, M imitates M 2. We omitthe formal definition and proof.@@@MFigure 2-12(c) Kleene star. Let M1 be a nondeterministic finite automaton; we construct anondeterministic finite automaton M such that L(M) = L(Md*. The construction is similar to that for concatenation, and is illustrated in Figure 2-13. Mconsists of the states of M1 and all the transitions of M l ; any final state of M1is a final state of M.
In addition, M has a new initial state s. This new initialstate is also final, so that e is accepted. From s there is an e-transition to theinitial state Sl of M 1, so that the operation of M1 can be initiated after M hasbeen started in state s. Finally, e-transitions are added from each final state of78Chapter 2: FINITE AUTOMATAFlF@SI>0@@MFigure 2-13Ml back to SI; this way, once a string in L( M 1 ) has been read, computation canresume from the initial state of MI.(d) Complementation.
Let M = (K,~, J, s, F) be a deterministic finite automaton. Then the complementary language L = ~* - L( M) is accepted by thedeterministic finite automaton M = (K,~, J, s, K - F). That is, M is identicalto M except that final and non final states are interchanged.(e) Intersection. Just recall thatand so closedness under intersection follows from closedness under union andcomplementation ((a) and (d) above) .•We now come to the main result of this section, the identification of twoimportant techniques for finitely specifying languages ~in fact, of a languagegenerator and a language acceptor:Theorem 2.3.2: A language is regular if and only if it is accepted by a finiteautomaton.Proof: Only if. Recall that the class of regular languages is the smallest classof languages containing the empty set 0 and the singletons a, where a is asymbol, and closed under union, concatenation, and Kleene star.
It is evident(see Figure 2-14) that the empty set and all singletons are indeed accepted byfinite automata; and by Theorem 2.3.1 the finite automaton languages are closedunder union, concatenation, and Kleene star. Hence every regular language isaccepted by some finite automaton.Example 2.3.1: Consider the regular expression (abUaab)*. A nondeterministicfinite automaton accepting the language denoted by this regular expression can2.3: Finite Automata and Regular Expressions79be built up using the methods in the proof of the various parts of Theorem 2.3.1,as illustrated in Figure 2-14.0stage 1a; bstage 2ab; aabae~tr::\~O------~stage 3ab U aab• O>-_b- l__ @stage 4(ab U aab)*eO--~Oae- Of------I-Figure 2-14If.
Let M = (K,~,~, s, F) be a finite automaton (not necessarily deterministic). We shall construct a regular expression R such that L(R) = L(M).We shall represent L(M) as the union of many (but a finite number of) simplelanguages. Let K = {ql, ... , qn} and s = ql. For i,j = 1, ... , nand k = 0, ... ,n,we define R( i, j, k) as the set of all strings in ~. that may drive M from stateqi to state qj without passing through any intermediate state numbered k + 1or greater -the endpoints qi and qj are allowed to be numbered higher thank.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
