1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

Consider a function h fromto a function from ~* to ~ * as follows.~to~*.Extend hh(e) =e.h(w) =h(w)h(a) for any w EFor example, if~~*,a E~.= ~ = {a, b}, h(a) = ab, and h(b) = aab,thenh(aab) =h(aa)h(b)=h(a)h(a)h(b)=ababaab.Any function h : ~* I--T ~ * defined in this way from a function h :is called a homomorphism.~ I--T ~ *86Chapter 2: FINITE AUTOMATALet h be a homomorphism from ~* to Ll *.(a) Show that if L ~ ~* is accepted by a finite automaton, then so is h[L].(b) Show that if L is accepted by a finite automaton, then so is {w E ~* :h(w) E L}. (Hint: Start from a deterministic finite automaton Maccepting L, and construct one which, when it reads an input symbola, tries to simulate what M would do on input h(a).)2.3.12. Deterministic finite-state transducers were introduced in Problem 2.1.4.Show that if L is accepted by a finite automaton, and 1 is computed by adeterministic finite-state transducer, then each of the following is true.(a) j[L] is accepted by a finite automaton.(b) 1-1 [L] is accepted by a finite automaton.2.4LANGUAGES THAT ARE AND ARE NOT REGULARThe results of the last two sections establish that the regular languages are closedunder a variety of operations and that regular languages may be specified eitherby regular expressions or by deterministic or nondeterministic finite automata.These facts, used singly or in combinations, provide a variety of techniques forshowing languages to be regular.Example 2.4.1: Let ~ = {O, 1, ...

, 9} and let L ~ ~* be the set of decimalrepresentations for nonnegative integers (without redundant leading O's) divisibleby 2 or 3. For example, 0,3,6,244 E L, but 1,03, 00 ~ L. Then L is regular.We break the proof into four parts.Let Ll be the set of decimal representations of nonnegative integers. Thenit is easy to see thatLl =OU{1,2, ... ,9}~*,which is regular since it is denoted by a regular expression.Let L2 be the set of decimal representations of nonnegative integers divisibleby 2. Then L2 is just the set of members of L, ending in 0, 2, 4, 6, or 8; that is,L2 = Lln~*{0,2,4,6,8},which is regular by Theorem 2.3.1(e).Let L3 be the set of decimal representations of nonnegative integers divisibleby 3.

Recall that a number is divisible by 3 if and only if the sum of its digitsis divisible by 3. We construct a finite automaton that keeps track in its finitecontrol of the sum modulo 3 of a string of digits. L3 will then be the intersection2.4: Languages That Are and Are Not Regular870,3,6,90,3,6,90,3,6,9Figure 2-18with L1 of the language accepted by this finite automaton. The automaton ispictured in Figure 2-18.Finally, L = L2 U L 3 , surely a r~gular language.\'>Although we now have a variety of powerful techniques for showing thatlanguages are regular, as yet we have none for showing that languages are notregular.

We know on fundamental principles that nonregular languages do exist,since the number of regular expressions (or the number of finite automata) iscountable, whereas the number of languages is uncountable. But to demonstratethat any particular language is not regular requires special tools.Two properties shared by all regular languages, but not by certain nonregular languages, may be phrased intuitively as follows:(1) As a string is scanned left to right, the amount of memory that is requiredin order to determine at the end whether or not the string is in the languagemust be bounded, fixed in advance and dependent on the language, not theparticular input string.

For example, we would expect that {anb n : n 2: O}is not regular, since it is difficult to imagine how a finite-state device couldbe constructed that would correctly remember, upon reaching the borderbetween the a's and the b's, how many a's it had seen, so that the numbercould be compared against the number of b's.(2) Regular languages with an infinite number of strings are represented by automata with cycles and regular expressions involving the Kleene star. S~chlanguages must have infinite subsets with a certain simple repetitive structure that arises from the Kleene star in a corresponding regular expressionor a cycle in the state diagram of a finite automaton.

This would lead us to88Chapter 2: FINITE AUTOMATAexpect, for example, that {an: n 2 1 is a prime} is not regular, since thereis no simple periodicity in the set of prime numbers.These intuitive ideas are accurate but not sufficiently precise to be used informal proofs. We shall now prove a theorem that captures some of this intuitionand yields the nonregularity of certain languages as an easy consequence.Theorem 2.4.1: Let L be a regular language. There is an integer n 2 1 suchthat any string W E L with iwi 2 n can be rewritten as W = xyz such that y -I- e,ixyi <::: n, and xyi z E L for each i 2 o.Proof: Since L is regular, L is accepted by a deterministic finite automaton M.Suppose that n is the number of states of M, and let W be a string of length nor greater.

Consider now the first n steps of the computation of M on w:where qo is the initial state of M, and WI ... Wn are the n first symbols of w.Since Jvl has only n states, and there are n + 1 configurations (qi, Wi+1 ... , w n )appearing in the computation above, by the pigeonhole principle there exist iand j, 0 <::: i < j <::: n, such that qi = qj. That is, the string y = WiWi+I ... Wjdrives M from state qi back to state qi, and this string is nonempty since i < j.But then this string could be removed from w, or repeated any number of timesin W just after the jth symbol of w, and M would still accept this string. Thatis, Jvl accepts xyi z E L for each i 20, where x = WI ... Wi, and z = Wj+1 ...

Wm.Notice finally that the length of xy, the number we called j above, is by definitionat most n, as required .•This theorem is one of a general class called pumping theorems, because theyassert the existence of certain points in certain strings where a substring can berepeatedly inserted without affecting the acceptability of the string. In termsof its structure as a mathematical statement, the pumping theorem above is byfar the most sophisticated theorem that we have seen in this book, because itsassertion, however simple to prove and apply, involves five alternating quantifiers.Consider again what it says:for each regular language L,there exists an n 2 1, such thatfor each string W in L longer than n,there exist strings x, y, z with W = xyz, y -I- e, and ixyi <::: n, such thatfor each i 2 0 xyi z E L.Applying the theorem correctly can be subtle.

It is often useful to think of theapplication of this result as a game between yourself, the prover, who is strivingto establish that the given language L is not regular, and an adversary who isinsisting that L is regular. The theorem states that, once L has been fixed, the2.4: Languages That Are and Are Not Regular89adversary must start by providing a number n; then you come up with a stringw in the language that is longer than n; the adversary must now supply anappropriate decomposition of w into xyz; and, finally, you triumphantly pointout i for which xyi z is not in the language.

If you have a strategy that alwayswins, no matter how brilliantly the adversary plays, then you have establishedthat L is not regular.It follows from this theorem that each of the two languages mentioned earlierin this section is not regular.Example 2.4.2: The language L = {aib i : i ~ O} is not regular, for if it wereregular, Theorem 2.4.1 would apply for some integer n. Consider then the stringw = a n b11 E L.

By the theorem, it can be rewritten as w = xyz such thatIxYI .s; nand y -I- e -that is, y = a i for some i > O. But then xz = an-ibn ~ L,contradicting the theorem.OExample 2.4.3: The language L = {an: n is prime} is not regular. For supposeit were, and let x, y, and z be as specified in Theorem 2.4.1. Then x = a P , y = a q ,and and z = aT, where p, r ~ 0 and q > O. By the theorem, xyn z E L for eachn ~ 0; that is, p + nq + r is prime for each n 2 o.

But this is impossible; for letn = p + 2q + r + 2; then p + nq + l' = (q + 1) . (p + 2q + r), which is a productof two natural numbers, each greater than 1.0Example 2.4.4: Sometimes it pays to use closure properties to show that alanguage is not regular. Take for exampleL= {wE {a, b}* :w has an equal number of a's and b's}.L is not regular, because if L were indeed regular, then so would be L n a*b*-by closure under intersection; recall Theorem 2.3.1(e).

However, this latterlanguage is precisely {anb n : n ~ O}, which we just showed is not regular.OIn fact, Theorem 2.4.1 can be strengthened substantially in spveral ways(see Problem 2.4.11 for one of them).Problems for Section 2.42.4.1. An arithmetic progression is the set {p + qn : n = 0,1,2, ...

Характеристики

Список файлов решённой задачи