1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 24
Текст из файла (страница 24)
(a) What is the sequence of S;'s produced if the nondeterministic finiteautomaton in Example 2.6.1 is presented with input bbabbabba?(b) Prove that the algorithm for running a nondeterministic finite automaton with m states on an input of length n takes time O(m 2 n).(c) Suppose that the given nondeterministic finite automaton has at mostp transitions from each state. Show that an O(mnp) algorithm is possible.2.6.3. Let ~ be an alphabet, x = al ... an E ~*, and consider the nondeterministicfinite automaton Mx = (K,~, Ll, s, F), where K = {qo, ql,'''' qn}, Ll ={(qi-l,ai,qi) : i = O, ...
,n -I} U {(qi,a,qi) : a E ~,i E {O,n}} (recallFigure 2-25) .(a) Show that L(Mx) = {w E ~* : x is a substring of w}.(b) Show that the deterministic finite automaton M~ with the fewest statesthat is equivalent to Mx also has n + 1 states. What is the worst-casetime required for its construction, as a function of n?(c) Show that there is a nondeterministic finite automaton M~ equivalentto M x, also with n + 1 states {qo, ql , ... , qn}, and with the followingimportant property: Each state except qo and qn has exactly two transitions out of it, of which one is an e-transition.
(Hint: Replace eachChapter 2: FINITE AUTOMATA110(d)(e)(f)(g)backwards transition in the deterministic finite automaton on Figure2-25 by an appropriate e-transition; generalize.)Argue that M~ remedies the problem of the hidden constant I~I discussed in the last paragraph of the text.Give an algorithm for constructing M~ from x. What is the complexityof your algorithm as a function of n?Devise an O(n) algorithm for the problem in (e) above. (Hint: Supposethat the e-transitions of M~ are (q;,e,qf(;)),i = 1, ... ,n - 1.
Showhow to compute f(i), based on the values f(j) for j < i. A clever"amortized" analysis of this computation gives the O(n) bound.)Suppose that ~ = {a, b} and x = aabbaab. Construct M x, M~, andM~/. Run each of these automata on the input aababbaaabbaaabbaabb.REFERENCESSome of the first papers on finite automata wereo G. H. Mealy "A method for synthesizing sequential circuits," Bell System Technical Journal, 34, 5 , pp.
1045-1079, 1955, and"Gedanken experiments on sequential machines," Automata Studies, ed. C. E. Shannon and J. McCarthy, pp. 129-53. Princeton: PrincetonUniversity Press, 1956.The classical paper on finite automata (containing Theorem 2.2.1) iso E. F. Mooreo M. O. Rabin and D. Scott"Finite automata and their decision problems," IBMJournal of Research and Development, 3, pp.
114-25, 1959.Theorem 2.3.2, stating that finite automata accept regular languages, is due to Kleene:"Representation of events by nerve nets," in Automata Studies,ed. C. E. Shannon and J. McCarthy, pp. 3-42. Princeton: Princeton UniversityPress, 1956.Our proof of this theorem follows the papero S. C. Kleeneo R. McNaughton and H. Yamada"Regular expressions and state graphs for automata," IEEE Transactions on Electronic Computers, EC-9, 1 pp. 39-47, 1960.Theorem 2.4.1 (the "pumping lemma") is fromo V.
Bar-Hillel, M. Perls, and E. Shamir"On formal properties of simple phrasestructure grammars," Zeitschrijt fur Phonetik, Sprachwissenschajt, und Kommunikationsforschung, 14, pp. 143-172, 1961.Finite-state transducers (Problem 2.1.4) were introduced in"Examples of abstract machines," IEEE Transactions on ElectronicComputers, EC-11, 2, pp. 132-135, 1962.Two-tape finite state automata (Problems 2.1.5 and 2.4.7) are examined ino S.
Ginsburg"The equivalence problem for deterministic two-tape automata," Journal of Computer and Systems Sciences, 7, pp. 218-236, 1973.The Myhill-Nerode Theorem (Theorem 2.5.2) is fromo M. BirdReferences111o A. Nerode "Linear automaton transformations," Proc. AMS, g, pp.541-544,1958.The algorithm for minimizing finite automata is from Moore's paper cited above. Amore efficient algorithm is given inoJ.
E. Hopcroft "An n log n algorithm for minimizing the states in a finite automaton," in The Theory of Machines and Computations, ed. Z. Kohavi. NewYork: Academic Press, 1971.The simulation of nondeterministic automata (Theorem 2.6.3) is based ono K. Thompson "Regular expression search algorithms," Communications of theACM, 11,6, pp. 419-422, 1968.The fast pattern matching algorithm in Problem 2.6.3 is fromo D. E. Knuth, J. H. Morris, Jr, V. R. Pratt "Fast pattern matching in strings,"SIAM J.
on Computing, 6, 2, pp. 323-350, 1976.The equivalence of one-way and two-way finite automata (Problem 2.5.4) is shown ino J. C. Shepherdson "The reduction of two-way automata to one-way automata,"IBM Journal of Research and Development, 3. pp. 198-200, 1959.Context-Free Languages3.1 CONTEXT-FREE GRAMMARSThink of yourself as a language processor. You can recogllize a legal Englishsentence when you hear one; "the cat is in the hat" is at least syntacticallycorrect (whether or not it says anything that happens to be the truth), but"hat the the in is cat" is gibberish.
However you manage to do it, you canimmediately tell when reading such sentences whether they are formed accordingto generally accepted rules for sentence structure. In this respect you are actingas a language recognizer: a device that accepts valid strings. The finiteautomata of the last chapter are formalized types of language recognizers.You also, however, are capable of producing legal English sentences. Again,why you would want to do so and how you manage to do it are not our concern;but the fact is that you occasionally speak or write sentences, and in generalthey are syntactically correct (even when they are lies). In this respect you areacting as a language generator.
In this section we shall study certain typesof formal language generators. Such a device begins, when given some sort of"start" signal, to construct a string. Its operation is not completely determinedfrom the beginning but is nevertheless limited by a set of rules. Eventually thisprocess halts, and the device outputs a completed string. The language definedby the device is the set of all strings that it can produce.Neither a recognizer nor a generator for the English language is at all easyto produce; indeed, designing such devices for large subsets of natural languageshas been a challenging research front for several decades. Nevertheless the ideaof a language generator has some explanatory force in attempts to discuss humanlanguage.
More important for us, however, is the theory of generators of formal,"artificial" languages, such as the regular languages and the important class of"context-free" languages illtroduced below. This theory will neatly complement113114Chapter 3: CONTEXT-FREE LANGUAGESthe study of automata, which recognize languages, and is also of practical valuein the specification and analysis of computer languages.Regular expressions can be viewed as language generators. For example,consider the regular expression a(a* U b*)b. A verbal description of how togenerate a string in accordance with this expression would be the followingFirst output an a. Then do one of the following two things:Either output a number of a's or output a number of b's.Finally output a b.The language associated with this language generator -that is, the set ofall strings that can be produced by the process just described -is, of course,exactly the regular language defined in the way described earlier by the regularexpression a(a* U b*)b.In this chapter we shall study certain more complex sorts of language generators, called context-free grammars, which are based on a more completeunderstanding of the structure of the strings belonging to the language.
To takeagain the example of the language generated by a(a* U b*)b, note that any stringin this language consists of a leading a, followed by a middle part -generatedby (a* U b*)- followed by a trailing b. If we let S be a new symbol interpretedas "a string in the language," and AJ be a symbol standing for "middle part,"then we can express this observation by writingS --+ aMb,where --+ is read "can be." We call such an expression a rule. What can ArI,the middle part, be? The answer is: either a string of a's or a string of b's.
Weexpress this by adding the rulesM --+ A and M --+ B,where A and B are new symbols that stand for strings of a's and b's, respectively.Now, what is a string of a's? It can be the empty stringA --+ e,or it may consist of a leading a followed by a string of a's:A --+ aA.Similarly, for B:B --+ e and B --+ bB.The language denoted by the regular expression a(a* U b*)b can then be definedalternatively by the following language generator.1153.1: Context-Free GrammarsStart with the string consisting of the single symbol 5.
Find a symbol in thecurrent string that appears to the left of ---+ in one of the rules above. Replacean occurrence of this symbol with the string that appears to the right of ---+ inthe same rule. Repeat this process until no such symbol can be found.For example, to generate the string aaab we start with 5, as specified; wethen replace 5 by aMb according to the first rule, 5 ---+ aMbo To aMb we applythe rule M ---+ A and obtain aAb. We then twice apply the rule A ---+ aA to getthe string aaaAb.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
