1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 18
Текст из файла (страница 18)
That is, R(i,j, k) is the set of strings spelled by all paths from qi to qj ofrank k (recall the similar maneuver in the computation of the reflexive-transitive80Chapter 2: FINITE AUTOMATAclosure of a relation in Section 1.6, in which we again considered paths with progressively higher and higher-numbered intermediate nodes).
When k = n, itfollows thatR(i,j,n) = {w E ~*: (qi'W) ~M (qj,e)}.ThereforeL(M) = U{R(l,j, n) : qj E F}.The crucial point is that all of these sets R(i,j, k) are regular, and hence so isL(M).The proof that each R(i,j, k) is regular is by induction on k. For k = 0,R(i,j,O) is either {a E ~ U {e} : (qi,a,qj) E Ll} if i f.: j, or it is {e} U {a E~ U {e} : (qi, a, qj) Ell} if i = j. Each of these sets is finite and thereforeregular.For the induction step, suppose that R(i, j, k-1) for all i, j have been definedas regular languages for all i, j. Then each set R( i, j, k) can be defined combiningpreviously defined regular languages by the regular operations of union, Kleenestar, and concatenation, as follows:R(i,j, k) = R(i,j, k - 1) U R(i, k, k - l)R(k, k, k - 1)* R(k,j, k - 1).This equation states that to get from qi to qj without passing through a statenumbered greater than k, M may either(1) go from qi to qj without passing through a state numbered greater thank - 1; or(2) go (a) from qi to qk; then (b) from qk to qk zero or more times; then (c)from qk to qj; in each case without passing through any intermediate statesnumbered greater than k - 1.Therefore language R(i,j, k) is regular for all i, j, k, thus completing theinduction .•Example 2.3.2: Let us construct a regular expression for the language acceptedby the deterministic finite automaton of Figure 2-15.
This automaton acceptsthe language{w E {a, b}* : w has 3k + 1 b's for some kEN}.Carrying out explicitly the construction of the proof of the if part can be verytedious (in this simple case, thirty-six regular expressions would have to beconstructed!). Things are simplified considerably if we assume that the nondeterministic automaton M has two simple properties:812.3: Finite Automata and Regular ExpressionsaabFigure 2-15(a) It has a single final state, F = {f}.(b) Furthermore, if (q,u,p) E ~, then q -::j:.
f and p -::j:. s; that is, there are notransitions into the initial state, nor out of the final state.This "special form" is not a loss of generality, because we can add to any automaton M a new initial state s and a new final state f, together with e-transitionsfrom s to the initial state of M and from all final states of M to f (see Figure 2-16(a), where the automaton of Figure 2-15 is brought into this "specialform"). Number now the states of the automaton ql, q2, ... , qn, as required bythe construction, so that s = qn-l and f = qn' Obviously, the regular expressionsought is R(n - I, n, n).We shall compute first the R(i,j,O)'s, from them the R(i,j, l)'s, and so on,as suggested by the proof. At each stage we depict each R( i, j, k) 's as a labelon an arrow going from state qi to state qj.
We omit arrows labeled by 0, andself-loops labeled {e}. With this convention, the initial automaton depicts thecorrect values of the R(i,j, O)'s -see Figure 2-16(a). (This is so because in ourinitial automaton it so happens that, for each pair of states (qi, qj) there is atmost one transition of the form (qi, u, qj) in~. In another automaton we mighthave to combine by union all transitions from qi to qj, as suggested by the proof.)Now we compute the R(i,j, l)'s; they are shown in Figure 2-16(b). Noticeimmediately that state ql need not be considered in the rest of the construction;all strings that lead M to acceptance passing through state ql have been considered and taken into account in the R(i,j, l)'s.
We can say that state ql has beeneliminated. In some sense, we have transformed the finite automaton of Figure2-16(a) to an equivalent generalized finite automaton, with transitions that maybe labeled not only by symbols in ~ or e, but by entire regular expressions. Theresulting generalized finite automaton has one less state than the original one,since ql has been eliminated.82Chapter 2: FINITE AUTOMATAq4>O~----~-C~~--~--~_ea(a)(b)aU ba*ba*bq4>0a*b.gq3e.@q4>0a*b(a U ba*ba*b)*q5.@q5(d)(c)Figure 2-16Let us examine carefully what is involved in general in eliminating a stateq (see Figure 2-17). For each pair of states qi -::j:.
q and qj -::j:. q, such that thereis an arrow labeled 0: from qi to q and an arrow labeled (3 from q to qj, we addan arrow from qi to qj labeled 0:')'* (3, where,), is the label of the arrow from qto itself (if there is no such arrow, then,), = 0, and thus ')'* = {e}, so the labelbecomes 0:(3). If there was already an arrow from qi to qj labeled J, then thenew arrow is labeled J U 0:')'* (3.qioFigure 2-17Continuing like this, we eliminate state q2 to obtain the R( i, j, 2) 's in Figure2-17(c), and finally we eliminate q3. We have now deleted all states except the2.3: Finite Automata and Regular Expressions83initial and final ones, and the generalized automaton has been reduced to a singletransition from the initial state to the final state.
We can now read the regularexpression for M as the label of this transition:R = R(4, 5, 5) = R(4, 5, 3) = a*b(ba*ba*b U a)*,which is indeed {w E {a,b}* : w has 3k + 1 b's for some k E N}.OProblems for Section 2.32.3.1. In part (d) of the proof of Theorem 2.3.1 why did we insist that M bedeterministic? What happens if we interchange the final and nonfinal statesof a nondeterministic finite automaton?2.3.2. What goes wrong in the proof of Part (c) of Theorem 2.3.1 if we simplymake SI final, and add arrows from all members of Fl back to SI (withoutintroducing a new starting state)?2.3.3. Give a direct construction for the closure under intersection of the languagesaccepted by finite automata.
(Hint: Consider an automaton whose set ofstates is the Cartesian product of the sets of states of the two originalautomata.) \Vhich of the two constructions, the one given in the text orthe one suggested in this problem, is more efficient when the two languagesare given in terms of nondeterministic finite automata?2.3.4. Using the construction in the proofs of Theorem 2.3.1, construct finite automata accepting these languages.(a) a*(abUbaUe)b*(b) ((aU b)*(e U c)*)*(c) ((ab)* U (bc)*)ab2.3.5. Construct a simple nondeterministic finite automaton to accept the language (ab U aba) *a. Then apply to it the constructiOll of Part (c) of theproof of Theorem 2.3.1 to obtain a nondeterministic finite automaton accepting ((ab U aba)*a)*.2.3.6.
Let L, L' ~ ~*. Define the following languages.1. Pref(L) = {w E ~* : x = wy for some x E L,y E ~'} (the set of prefixes of L).1. Suf(L) = {w E ~* : x = yw for some x E L,y E ~*} (the set of suffixes of L).3. Subseq(L) = {WI W2 .•• Wk : kEN, Wi E ~* for i = 1, ... , k, and thereis a string x = XOWIXI W2X2 .•• WkXk E L} (the set of subsequencesof L).Chapter 2: FINITE AUTOMATA844. Lj L' = {w E ~* : wx E L for some x E L'} (the right quotient of Lby L').5. Max(L) = {w E L : if x -::j:. e then wx ¢:. L}.6.
LR = {w R : w E L}.Show that if L is accepted by some finite automaton, then so is each of thefollowing.(a) Pref(L)(b) Suf(L)(c) Subseq(L)(d) Lj L', where L' is accepted by some finite automaton.(e) Lj L', where L' is any language.(f) Max(L)(g) LRbbb(a)a(c)ababa(b)a(d)2.3.7. Apply the construction in Example 2.3.2 to obtain regular expressions corresponding to each of the finite automata above. Simplify the resultingregular expressions as much as you can.2.3.8. For any natural number n ~ 1 define the nondeterministic finite automatonMn = (Kn'~n,Lln,sn,Fn) with Kn = {Ql,q2, ... ,qn}, Sn = Ql, Fn = {QI},~n = {aij: i,j = 1, ...
,n}, and Ll n = {(i,aij,j): i,j = 1, ... ,n}.(a) Describe L(Mn) in English.852.3: Finite Automata and Regular Expressions(b) Write a regular expression for L(M3).(c) Write a regular expression for L(M5).It is conjectured that, for all polynomials p there is an n such that no regularexpression for L(Mn) has length smaller than p(n) symbols.2.3.9. (a) By analogy with Problem 2.1.5, define a nondeterministic 2-tapefinite automaton, and the notion that such an automaton accepts a particular set of ordered pairs of strings.(b) Show that {(amb,anbP): n,m,p ~ 0, and n = m or n = p} is acceptedby some nondeterministic 2-tapc finite automaton.(c) We shall see (Problem 2.4.9) that nondeterministic 2-tape finite automata cannot always be converted into deterministic ones.
This being thecase, which of the constructions used in the proof of Theorem 2.3.1 can beextended to demonstrate closure properties of the following?(i) The sets of pairs of strings accepted by nondeterministic 2-tape finiteautomata.(ii) The sets of pairs of strings accepted by deterministic 2-tape finite automata.Explain your answers.2.3.10. A language L is definite if there is some k such that, for any string w,whether w E L depends only on the last k symbols of w.(a) Rewrite this definition more formally.(b) Show that every definite language is accepted by a finite automaton.(c) Show that the class of definite languages is closed under union andcomplementation.(d) Give an example of a definite language L such that L * is not definite.(e) Give an example of definite languages L 1 , L2 such that Ll L2 is notdefinite.2.3.11. Let ~ and ~ be alphabets.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
