1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 13
Текст из файла (страница 13)
Clearly no string in £( (c* (aU (bc*)) *)) can contain the substringac, since each occurrence of a in such a string is either at the end of the string,or is followed by another occurrence of a, or is followed by an occurrence of b.On the other hand, let w be a string with no substring ac. Then w begins withzero or more c's. If they are removed, the result is a string with no sub-stringac and not beginning with c. Any such string is in £«aU(bc*))); for it canbe read, left to right, as a sequence of a's, b's, and c's, with any blocks of c'simmediately following b's (not following a's, and not at the beginning of thestring). Therefore wE C«c*(aU(bc*))*)).OExample 1.8.4: (O*U«(O*(1U(ll)))«OO*)(1U(ll)))*)O*)) represents the setof all strings over {O, I} that do not have the substring 111.0Every language that can be represented by a regular expression can berepresented by infinitely many of them.
For example, a and (O'U0) always represent the same language; so do «O'U(3)U,) and (O'U«(3U,)). Since set unionChapter 1: SETS, RELATIONS, AND LANGUAGES50and concatenation are associative operations --that is, since (L1 U L 2 ) U L3 =L1 U (L2 U L 3) for all L 1, L 2 , L 3, and the same for concatenation- we normally omit the extra ( and ) symbols in regular expressions; for example, wetreat aUbUc as a regular expression even though "officially" it is not. For another example, the regular expression of Example 1.8.4 might be rewritten asO*UO*(lU11 )(OO* (lUll) )*0*.Moreover, now that we have shown that regular expressions and the languages they represent can be defined formally and unambiguously, we feel free,when no confusion can result, to blur the distinction between the regular expressions and the "mathematical English" we are using for talking about languages.Thus we may say at one point that a' b' is the set of all strings consisting ofsome number of a's followed by some number of b's -to be precise, we shouldhave written {a}' 0 {b}*.
At another point, we might say that a'b' is a regular expression representing that set; in this case, to be precise, we should havewritten (a*b*).The class of regular languages over an alphabet I; is defined to consist ofall languages L such that L = Lea) for some regular expression a over I;. That is,regular languages are all languages that can be described by regular expressions.Alternatively, regular languages can be thought of in terms of closures. The classof regular languages over I; is precisely the closure of the set of languages{{O'} : 0'E I;} U{0}with respect to the functions of union, concatenation, and Kleene star.We have already seen that regular expressions do describe some nontrivialand interesting languages.
Unfortunately, we cannot describe by regular expressions some languages that have very simple descriptions by other means. Forexample, {on 1n : n ~ O} will be shown in Chapter 2 not to be regular. Surelyany theory of the finite representation of languages will have to accommodate atleast such simple languages as this. Thus regular expressions are an inadequatespecification method in general.In search of a general method for finitely specifying languages, we mightreturn to our general schemeL= {w E I;' : w has propertyP}.But which properties P should we entail? For example, what makes the preceding properties, "w consists of a number of O's followed by an equal numberof 1's" and "w has no occurrence of 111" such obvious candidates? The readermay ponder about the right answer; but let us for now allow algorithmic properties, and only these.
That is, for a property P of strings to be admissible as aspecification of a language, there must be an algorithm for deciding whether agiven string belongs to the language. An algorithm that is specifically designed,1.8: Finite Representations of Languages51for some language L, to answer questions of the form "Is string w a member ofL?" will be called a language recognition device. For example, a device forrecognizing the languageL = {w E {O, 1} * : w does not have 111 as a substring}.by reading strings, a symbol at a time, from left to right, might operate like this:Keep a count. which starts at zero and is set back to zero every time a 0 is encountered in the input; add one every time a 1 is encountered in the input; stop with aNo answer if the count ever reaches three.
and stop with a Yes answer if the wholestring is read without the count reaching three.An alternative and somewhat orthogonal method for specifying a languageis to describe how a generic specimen in the language is produced. For example,a regular expression such as (e U b U bb)(a U ab U abb)* may be viewed as a wayof generating members of a language:To produce a member of L. first write down either nothing. or b.
or bb; then writedown a or abo or abb. and do this any number of times, including zero; all and onlymembers of L can be produced in this way.Such language generators are not algorithms, since they are not designedto answer questions and are not completely explicit about what to do (how are weto choose which of a, ab, or abb is to be written down?) But they are importantand useful means of representing languages all the same. The relation betweenlanguage recognition devices and language generators, both of which are typesof finite language specifications, is another major subject of this book.Problems for Section 1.81.8.1.
What language is represented by the regular expression ((a*a)b)Ub)?1.8.2. Rewrite each of these regular expressions as a simpler expression representing the same set.(a) 0*Ua*Ub*U(aUb)*(b) ((a*b*)*(b*a*)*)*(c) (a*b)*U(b*a)*(d) (aUb)*a(aUb)*1.8.3. Let(a)(b)(c){a, b}. Write regular expressions for the following sets:All strings in I;* with no more than three a's.All strings in I;* with a number of a's divisible by three.All strings in I;* with exactly one occurrence of the substring aaa.I; =1.8.4. Prove that if L is regular, then so is L' = {w : uw E L for some string u}.(Show how to construct a regular expression for L' from one for L.)52Chapter 1: SETS, RELATIONS, AND LANGUAGES1.8.5.
Which of the following are true? Explain.(a) baa E a*b*a*b*(b) b*a* n a*b* = a* U b*(c) a*b*nb*c*=0(d) abcd E (a(cd)*b)*1.8.6. The star height h(a) of a regular expression a is defined by induction asfollows.h(0) =0h(a) =0 for each a Eh(aUj3) =h(a;3)h(a*) =h(a)I;= the maximum of h(a) and h(j3).+1For example, if a = «(ab)*Ub*)*Ua*), then h(a) = 2. Find, in each case, aregular expression which represents the same language and has star heightas small as possible.(a) (abc)*ab)*(b) (a(ab*c)*)*(c) (c(a*b)*)*(d) (a*Ub*Uab) *(e) (abb*a)*1.8.7.
A regular expression is in disjunctive normal form if it is of the form(aJ Ua2 U ... Ua n ) for some n ;::: 1, where none of the ai's contains an occurrence of U. Show that every regular language is represented by one indisjunctive normal form.REFERENCESAn excellent source on informal set theory is the booko P. Halmos Naive Set Theory, Princeton, N.J.: D. Van Nostrand, 1960.A splendid book on mathematical induction iso G. Polya Induction and Analogy in Mathematics, Princeton, N.J.: PrincetonUniversity Press, 1954.A number of examples of applications of the pigeonhole principle appear in the firstchapter ofo C.
L. Liu Topics in Combinatorial Mathematics, Buffalo, N.Y.: MathematicalAssociation of America, 1972.Cantor's original diagonalization argument can be found ino G. Cantor Contributions to the Foundations of the Theory of Transfinite Numbers New York: Dover Publications, 1947.The V-notation and severol variants were introduced in53Referenceso D. E. Knuth "Big omicron and big omega and big theta," ACM SIGACT News,8 (2), pp. 18-23, 1976.The O(n3) algorithm for the reflexive-transitive closure is fromo S. Warshall "A theorem on Boolean matrices," Journal of the ACM, 9, 1, pp. 1112, 1962.Two books on algorithms and their analysis areo T.
H. Cormen, C. E. Leiserson, R. L. Rivestbridge, Mass.: The MIT Press., 1990, andIntroduction to Algorithms, Cam-o G. Brassard, P. Bratley Fundamentals of Algorithms, Englewood Cliffs, N.J.:Prentice Hall, 1996.Two advanced books on language theory areo A. SalomaaFormal Languages New York: Academic Press, 1973.o M. A.
Harrison Introduction to Formal Language Theory, Reading, Massach.:Addison-Wesley, 1978.Finite Automata2.1 DETERMINISTIC FINITE AUTOMATAThis book is about mathematical models of computers and algorithms. In thisand the next two chapters we shall define increasingly powerful models of computation, more and more sophisticated devices for accepting and generating languages.
Seen in the light of the whole development of the book, this chapter willseem a rather humble beginning: Here we take up a severely restricted modelof an actual computer called a finite automaton,t or finite-state machine.The finite automaton shares with a real computer the fact that it has a "centralprocessing unit" of fixed, finite capacity.
It receives its input as a string, delivered to it on an input tape. It delivers no output at all, except an indicationof whether or not the input is considered acceptable. It is, in other words, alanguage recognition device, as described at the end of Chapter 1. What makesthe finite automaton such a restricted model of real computers is the completeabsence of memory outside its fixed q:mtral processor.Such a simple computational model might at first be considered too trivialto merit serious study: of what use is a computer with no memory? But a finiteautomaton is not really without memory; it simply has a memory capacity thatis fixed "at the factory" and cannot thereafter be expanded. It can be arguedthat the memory capacity of any computer is limited -by budget constraints,by physical limits, ultimately by the size of the universe. Whether the bestmathematical model for a computer is one that has finite memory or one thathas unbounded memory is an interesting philosophical question; we shall studyboth kinds of models, starting with the finite one and later dwelling much moretAn automaton (pronounced: o-to-ma-ton, plural: automata) is a machine designed to respond to encoded instructions; a robot.55Chapter 2: FINITE AUTOMATA56on the unbounded one.Even if one thinks, as we do, that the correct way to model computers andalgorithms is in terms of an unbounded memory capacity, we should first besure that the theory of finite automata is well understood.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
