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

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

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

1 and each state Q2 E K 2, weadd to 6. the transition (( (Ql , Q2), e, ,8), UPI , Q2), 'Y))' That is, M passes fromstate (Ql, Q2) to state (Pl,P2) in the same way that Ml passes from state Qlto PI, except that in addition M keeps track of the change in the state ofM2 caused by reading the same input.3.5: Languages that Are and Are Not Context-Free145It is easy to see that indeed w E L(M) if and only if w E L(M1) n L(M2)' •Example 3.5.1: Let L consist of all strings of a's and b's with equal numbersof a's and b's but containing no substring abaa or babb.

Then L is context-free,since it is the intersection of the language accepted by the pushdown automatonin Example 3.3.3 with the regular language {a, b} * - {a, b}*(abaaUbabb){ a, b}*.<)A Pumping TheoremInfinite context-free languages display periodicity of a somewhat subtler formthan do regular languages.

To understand this aspect of context-freeness westart from a familiar quantitative fact about parse trees. Let G = (V, L, R, S)be a context-free grammar. The fanout of G, denoted ¢(G), is the largestnumber of symbols on the right-hand side of any rule in R. A path in a parsetree is a sequence of distinct nodes, each connected to the previous one by a linesegment; the first node is the root, and the last node is a leaf. The length ofthe path is the number of line segments in it. The height of a parse tree is thelength of the longest path in it.Lemma 3.5.1: The yield of any parse tree of G of height h has length at most¢(G)h.Proof: The proof is by induction on h.

When h = 1, then the parse tree is arule of the grammar (this is Case 2 of the definition of a parse tree), and thusits yield has at most ¢( G)h = ¢( G) symbols.Suppose then that the result is true for parse trees of height up to h 2 1.For the induction step, any parse tree of height h+ 1 consists of a root, connectedto at most d>( G) smaller parse trees of height at most h (this is Case 3 of thedefinition of a parse tree). By induction, all these parse "subtrees" have yieldsof length at most ¢(G)h each. It follows that the total yield of the overall parsetree is indeed at most ¢(G)h+1, completing the induction .•To put it another way, the parse tree of any string w E L(G) with Iwl >¢(G)h must have a path longer than h. This is crucial in proving the followingpumping theorem for context-free languages.Theorem 3.5.3: Let G = (V, L, R, S) be a context-free gr·ammar.

Then anystring w E L( G) of length greater than 1>( G) II" -I;I can be rewritten as w = uvxyzin such a way that either v or y is nonempty and uvnxynz is in L(G) for everyn 2 O.Proof: Let w be such a string, and let T be the parse tree with root labeled Sand with yield w that has the smallest number of leaves among all parse treesChapter 3: CONTEXT-FREE LANGUAGES146with the same root and yield. Since T's yield is longer than 4>( G) IV -EI, it followsthat T has a path of length at least IV - ~I + 1, that is, with at least IV - ~I + 2nodes. Only one of these nodes can be labeled by a terminal, and thus theremaining are labeled by nonterminals. Since there are more nodes in the paththan there are nonterminals, there are two nodes on the path labeled with thesame member A of V - L.

Let us look at this path in more detail (see Figure3-9).SFigure 3-9Let us call u, v, x, y, and z the parts of the yield of T as they are shownin the figure. That is, x is the yield of the subtree Til whose root is the lowernode labeled A; v is the part of the yield of the tree T' rooted at the higher Aup to where the yield of Til starts; u is the yield of T up to where the yield ofT' starts; and z is the rest of the yield of T.It is now clear that the part of T' excluding Til can be repeated any numberof times, including zero times, to produce other parse trees of G, whose yield isany string of the form uvnxyn z , n 2 O. This completes the proof, except for therequirement that vy f::- e. But if vy = e, then there is a tree with root Sandyield w with fewer leaves than that of T ~namely, the one that results if weomit from T the part of T' that excludes T"- contrary to our assumption thatT is the smallest tree of this kind .•E;xample 3.5.2: Just like the pumping theorem for regular languages (Theorem2.4.1), this theorem is useful for showing that certain languages are not contextfree.

For example, L = {anbnc n : n 2 O} is not. For suppose that L = L(G)¢(G)IV-EIfor some context-free grammar G = (V,~, R, S). Let n > 3. Thenw = anbnc n is in L(G) and has a representation w = uvxyz such that v or3.5: Languages that Are and Are Not Context-Free147y is nonempty and 1w n xyn;; is in L( G) for each n = 0,1,2, ... There are twocases, both leading to a contradiction. If vy contains occurrences of all threesymbols a, b, c, then at least one of v, y must contain occurrences of at least twoof them. But then uv 2xy2 z contains two occurrences out of their correct order--a b before an a, or a c before an a or b.

If vy contains occurrences of some butnot all of the three symbols, then uv 2xy2 z has unequal numbers of a's, b's, andc's.¢Example 3.5.3: L = {an: n 2 1 is a prime} is not context-free. To see this,take a prime p greater than ¢( G) Iv -EI, where G = (V,~, R, S) is the contextfree grammar allegedly generating L. Then w = a P can be written as prescribedby the theorem, w = uvxyz, where all components of ware strings of a's andvy :J:.

e. Suppose that vy = a q , and uxz = a", where q and r are natural numbers,and q > O. Then the theorem states that r + nq is a prime, for all n 2 O. Thiswas found absurd in Example 2.4.3.It was no accident that, in our proof that {an: n 2 1 is a prime} is notcontext-free, we resorted to an argument very similar to that in Example 2.4.3,showing that the same language is not regular.

It turns out that any context-freelanguage over a single-letter alphabet is regular; thus, the result of the presentexample follows immediately from this fact and Example 2.4.3.¢Example 3.5.4: We shall next show that the language L = {w E {a, b, c}'w has an equal number of a's, b's, and c's} is not context-free. This time weneed both Theorems 3.5.3 and 3.5.2: If L were context-free, then so would be itsintersection with the regular set a*b'c'.

But this language, {anbnc n : n 2 A},was shown to be non-context-free in Example 3.5.2 above.¢These negative facts also expose the POVE'Ity in closure properties of theclass of context-free languages:Theorem 3.5.4: The context-free languages are not closed under intersectionor complementation.Proof: Clearly {anbnc m : m,n 2 O} and {ambnc n : m,n 2 O} are bothcontext-free. The intersection of these two context-free languages is the language {a n bn c71 : n 2 O} just shown not to be context-free. And, sinceif the context-free languages were closed under complementation, they wouldalso be closed under intersection (we know they are closed under union, Theorem3.5.1) .•148Chapter 3: CONTEXT-FREE LANGUAGESProblems for Section 3.53.5.1.

Use closure under union to show that the following languages are contextfree.(a) {amb n : m ¥- n}(b) {a, b}* - {anb n : n ~ O}(c) {ambncPdQ:n=q, ormsporm+n=p+q}(d) {a, b}* - L, where L is the languageL = {babaabaaab ... ba n- 1ba n b: n ~ I}(e) {w E {a,b}*: w = w R }3.5.2. Use Theorems 3.5.2 and 3.5.3 to show that the following languages are notcontext-free.(a) {a P : p is a prime}(b){an2:n~O}(c) {www : wE {a, b}*}(d) {w E {a, b, c}* : w has equal numbers of a's, b's, and c's}3.5.3. Recall that a homomorphism is a function h from strings to strings suchthatfor any two strings v andw, h(vw) = h(v)h(w). Thus a homomorphismis determined by its values on single symbols: if w = a1 ...

an with eachai a symbol, then h(w) = h(ad ... h(a n ). Note that homomorphisms can"erase": h(w) may be e, even though w is not. Show that if L is a contextfree language and h is a homomorphism, then(a) h[L] is context-free;(b) h-l[L] (that is, {w E ~* : h(w) E L}) is context-free. (Hint: Startfrom a pushdown automaton M accepting L. Construct another pushdownautomaton, similar to M, except that it reads its input not from the inputtape, but from a finite buffer that is occasionally replenished in some way.You supply the rest of the intuition and the formal details.)3.5.4. In the proof of Theorem 3.5.2, why did we assume that M2 was deterministic?3.5.5. Show that the language L = {babaabaaab ...

ban-1banb : n ~ I} is notcontext-free(a) by applying the Pumping Theorem (3.5.3);(b) by applying the result of Problem 3.5.3. (Hint: What is h[L], whereh(a) = aa, and h(b) = a?)3.5.6. If L 1, L2 ~as follows.~*Lt/L2are languages, the right quotient of L1 by L2 is defined= {wE~* :there is au E L2 such that wu E Lt}3.5: Languages that Are and Are Not Context-Free149(a) Show that if L1 is context-free and R is regular, then LJ / R is contextfree.(b) Prove that {aPb n : p is a prime number and n > p} is not context-free.3.5.7. Prove the following stronger version of the Pumping Theorem (Theorem3.5.3): Let G be a context-free grammar. Then there are numbers K and ksuch that any string w E L(G) withlwl2.

K can be rewritten as w = uvxyzwith vxy skin such a way that either v or y is non empty and UV71 xy" z EL(G) for every n 2. O.3.5.8. Use Problem 3.5.7 to show that the language {ww : w E {a,b}"} is notcontext-free.3.5.9. Let G = (V,~, R, S) be a context-free grammar. A nonterminal A of G iscalled self-embedding if and only if A::::}~ uAv for some u,v E V".(a) Give an algorithm to test whether a specific nonterminal of a givencontext-free grammar is self.·embedding.(b) Show that if G has no self-embedding Ilonterminal, then L(G) is aregular language.3.5.10. A context-free grammar G = (i-T,~, R, S) is said to be in Greibach normalform if every rule is of the form or A --+ w for some w E ~(V - ~)*.(a) Show that for every context-free grammar G, there is a context-freegrammar G' in Greibach normal form such that L(G') = L(G') - {e}.(b) Show that if M is constructed as in the proof of Lemma 3.4.1 from agrammar in Greibach normal form, then the number of steps in any computation of M on an input w can be bounded as a function of the length ofw.3.5.11.

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

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