1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 22
Текст из файла (страница 22)
The splitting happened because 8(q2,b) ~o 8(q4,b),8(q5,b), and8(q4,a) ~o 6(q5,a).After the second iteration, there is no further splitting of classes. Thealgorithm thus terminates, and the minimum-state automaton is shown in=1Chapter 2: FINITE AUTOMATA100Figure 2-22Figure 2-22. As expected, it is isomorphic with the standard automatonshown in Figure 2-21.0Example 2.5.4: Recall the language L ~ {al,' .. ,an }* of all strings that do notcontain occurrences of all n symbols, and the corresponding deterministic finiteautomaton with 2n states (Example 2.2.5). We can now show that these statesare all necessary. The reason is that ~L has 2n equivalence classes.
Namely, foreach subset A of ~, let LA be the set of all strings containing occurrences of allsymbols in A, and of no symbols in ~ - A (for example, L0 = {e}). Then it isnot hard to see that the 2n sets LA are precisely the equivalence classes of ~L.Because if x E LA and y E LB for two distinct subsets A and B of ~, then forany Z E Lr,-B, XZ E L, and yz ~ L (here we assumed that B is not containedin A; otherwise, reverse the roles of A and B). 0Recall that there is a nondeterministic finite automaton with n + 1 statesthat accepts the same language (Example 2.2.2). Although deterministic automata are exactly as powerful as nondeterministic ones in principle, determinism comes with a price in the number of states which is, at worst, exponential.To put it in a different way, and in fact a way that anticipates the importantissues of computational complexity discussed in Chapters 6 and 7: When thenumber of states is taken into account, non determinism is exponentially morepowerful than determinism in the domain of finite automata.Problems for Section 2.52.5.1.
(a) Give the equivalence classes under ~L for these languages:(i) L = (aabUab)*.(ii) L = {x: x contains an occurrence of aababa}.(iii) L = {xx R : x E {a, b}*}.(iv) L = {xx: x E {a,b}*}.(v) Ln = {a,b}*a{a,b}n, where n > 0 is a fixed integer.(vi) The language of balanced parentheses (Problem 2.4.6).1012.5: State Minimization(b) For those languages in (a) for which the answer is finite, give a deterministicfinite automaton with the smallest possible number of states that acceptsthe corresponding language.2.5.2. Call a string x E I:* square-free if it cannot be written as x = uvvw forsome u, v, w E I:*, vi-e.
For example, lewis and christos are square-free,but harry and papadimitriou are not. Show that, if II:I > 1, then the setof all square-free strings in I:* is not regular.2.5.3. For each of the finite automata (deterministic or nondeterministic) considered in Problems 2.1.2 and 2.2.9, find the minimum-state equivalent deterministic finite automaton.2.5.4. A two-way finite automaton is like a deterministic finite automaton,except that the reading head can go backwards as well as forwards on theinput tape.
If it tries to back up off the left end of the tape, it stops operating without accepting the input. Formally, a two-way finite automaton Mis a quintuple (K, I:, 8, s, F), where K, I:, s, and F are as defined for deterministic finite automata, and 8 is a function from K x I: to K x {f-, --+};the f- or --+ indicates the direction of head movement. A configuration isa member of K x I:* x I:*; configuration (p, u, v) indicates that the machineis in state p with the head on the first symbol of v and with u to the left ofthe head. If v = e, configuration (p, u, e) means that M has completed itsoperation on u, and ended up in state p.We write (PI, Ul, vd f- M (P2, U2, 1)2) if and only if VI = av for some a E I:,8(Pl,a) = (P2,E), and either1. E =--+ and U2 = Ula,V2 = v, or2.
E =f-, Ul = ua' for some u E I:*, and V2 = a'vl.As usual, f-'M is the reflexive, transitive closure of f- M. M accepts w if andonly if (s, e, w) f-'M (1, w, e) for some f E F. In this problem you will usethe Myhill-Nerode Theorem (Theorem 2.5.2 and its corollary) to show that alanguage accepted by a two-way finite automaton is accepted by a one-wayfinite automaton. Thus, the apparent power to move the head to the left doesnot enhance the power of finite automata.Let M be a two-way finite automaton as just defined.(a) Let q E K and w E I:*.
Show that there is at most one p E K suchthat (q,e,w) f-~1 (p,w,e).(b) Let t be some fixed element not in K. For any wEI: *, define a functionXw: K I-t KU {t} as follows.Xw(q) = {p,t,if (q,e,w) f-'M (p,w,e)otherwiseChapter 2: FINITE AUTOMATA102By Part (a), XW is well defined.
Also, for anyK x ~ f-t Ku {t} as follows:Ow(q, a)={P't,WE ~*,define Ow :if (q,w,a) f-t (p,w,a) but it is not the case that(q,w,a) f-!f (r,w,a) f-!f (p,w,a) for any r i- p,if there is no p E K such that (q, w, a) f- t (p, w, a)t(c)(d)(e)(f)B(Here by fwe mean the transitive (not reflexive) closure of f- M, thatis, the "yields in one or more steps" relation on configurations.) Nowsuppose that w, v E ~*, Xw = Xv, and Ow = Ov. Show that, for anyu E ~*, M accepts wu if and only if M accepts vu.Show that, if L(M) is the language accepted by a deterministic twoway automaton, then L(M) is accepted by some ordinary (one-way)deterministic finite automaton. (Hint: Use (b) above to show that';:;;;£(M) has finitely many equivalence classes.)Conclude that there is an exponential algorithm which, given a deterministic two-way automaton M, constructs an equivalent deterministicfinite automaton.
(Hint: How many different functions XW and Ow canthere be, as a function of IKI and I~I?)Design a deterministic two-way finite automaton with O(n) states accepting the language Ln = {a, b}*a{ a, b}n (recall Problem 2.5.1(a)(v)).Comparing with Problem 2.5.1(b)(v), conclude that the exponentialgrowth in (d) above is necessary.Can the argument and construction in this problem be extended tonondeterministic two-way finite automata?ALGORITHMS FOR FINITE AUTOMATAMany of the results in this chapter were concerned with different ways of representing a regular language: as a language accepted by a finite automaton,deterministic or nondeterministic, and as a language generated by a regular expression. In the previous section we saw how, given any deterministic finiteautomaton, we can find the equivalent deterministic finite automaton with thefewest possible states.
All these results are constructive, in that their proofs immediately suggest algorithms which, given a representation of one kind, producea representation of anyone of the others. In this subsection we shall make suchalgorithms more explicit, and we shall analyze roughly their complexity.We start from the algorithm for converting a nondeterministic finite automaton to a deterministic one (Theorem 2.2.1); let us pinpoint its complexity. The input to the algorithm is a nondeterministic finite automaton M =2.6: Algorithms for Finite Automata103(K,~, 6., s, F); thus, we must calculate its complexity as a function of the cardinalities of K, ~, and 6..
The basic challenge is to compute the transitionfunction of the deterministic automaton, that is, for each Q ~ K, and eacha E ~, to compute8'(Q, a) =U{ E(p) : p E K and (q, a,p) E 6. for some q E Q}.It is more expedient to precompute all E(P)'s once and for all, using the closurealgorithm explained in that proof. It is easy to see that this can be done in totaltime O(IKI 3) for all E(p)'s. Once we have the E(p)'s, the eomputation ofr5' (Q, a)can be carried out by first collecting all states p such that (q, a,p) E 6., and thentaking the union of all E(p)'s -a total of O(I6.IIKI2) elementary operations suchas adding an element to a subset of K.
The total complexity of the algorithm isthus O(2IKIIKI31~116.IIKI2). It is no surprise that our complexity estimate is anexponential function of the size of the input (as manifested by the 21K1 factor);we have seen that the output of the algorithm (the equivalent deterministic finiteautomaton) may in the worst case be exponential.Converting a regular expression R into an equivalent nondeterministic finiteautomaton (Theorem 2.3.2) is in comparison efficient: It is very easy to showby induction on the length of R that the resulting automaton has no more than21RI states, and therefore no more than 41RI2 transitions -a polynomial.Turning a given finite automaton M = (K,~, 6., s, F) (deterministic ornot) into a regular expression generating the same language (Theorem 2.3.2)involves computing IKI3 regular expressions R(i,j, k). However, the length ofthese expressions is in the worst case exponential: During each iteration onthe index k, the length of each regular expression is roughly tripled, as it isthe concatenation of three regular expressions from the previous iteration.
Theresulting regular expressions may have length as large as 31K1 -an exponentialfunction of the size of the automaton.The minimization algorithm in the previous section which, given any deterministic automaton M = (K,~, 8, s, F), computes an equivalent deterministicfinite automaton with the smallest number of states, is polynomial. It proceedsin at most IKI - 1 iterations, with each iteration involving the determination,for each pair of states, whether they are related by =n; this test only takesO(I~I) elementary operations such as testing whether two states are related bya previously computed equivalence relation =n-l.
Thus the total complexity ofthe minimization algorithm is O(I~IIKI:l) -a polynomial.Given two language generators or two language acceptors, one natural andinteresting question to ask is whether they are equivalent that is, whether theygenerate or accept the same language. If the two acceptors are deterministicfinite automata, the state minimization algorithm also provides a solution tothe equivalence problem: Two deterministic finite automata are equivalent if104Chapter 2: FINITE AUTOMATAand only if their standard automata are identical. This is because the standardautomaton only depends on the language accepted, and is therefore a usefulstandardization for testing equivalence.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
