1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 29
Текст из файла (страница 29)
We shall do this in three stages: First we shall replace transitions with1,81 2 2. Then we shall get rid of transitions with hi > 2, without introducingany transitions with 1,81 2 2. Finally, we shall get rid of transitions with ,8 = e,without introducing any transitions with 1,81 2 2 or hi > 2.Consider any transition ((q,a,,8),(p,,)) E ~', where,8 = B 1 ···B n withn > 1. It is replaced by new transitions that pop sequentially the individualsymbols in Bl ... B n , rather than removing them all in a single step.
Specifically,we add to ~' these transitions:bottom symbol, also not in((q, e, B 1 ), (qB 1, e)),((qB 1, e,B2 ),(qB 1B2· e )),((qBI B, ... B._." e, Bn-d, (qB 1B, ... B,,_I, e)),((qB1B2 .. B._I' a, B n ), (p, ,)),where, for i = 1, ... ,n - 1, qB1B2... Bi is a new state with the intuitive meaning"state q after symbols B 1 B 2 ••• Bi have been popped. We repeat this with alltransitions ((q,u,,8), (p,,)) E ~' with 1,81 > 1. It is clear that the resultingpushdown automaton is equivalent to the original one.Similarly, we replace transitions ((q,u,,8), (p,,)) with, = C1 ...
,Cm andm 2 2 by the transitions((q, a, ,8), (rl' Cm)),(h, e, e), (r2' Cm-d),((r m -2, e, e), (r m - l , C2 )),((r m -l, e, e), (p, Cd),where rl,.'" r m -l are new states. Notice that all transitions ((q, a, ,8), (p, ,)) Et{ have now hi ::; I-a more stringent requirement than simplicity (and actually3.4: Pushdown Automata and Context-Free Grammars141one that would be a loss of generality). It will be restored to hi ::; 2 in the nextstage. Also, no transitions (( q, u, ,8), (p, ,)) with 1,81 > 1 were added.Finally, consider any transition ((q, a, e), (p, ,)) with q i- s' ~the only possible remaining violations of the simplicity condition. Replace any such transitionby all transitions of the form ((q,a,A), (p"A)), for all A E r U {Z}. That is,if the automaton could move without consulting its stack, it can also move byconsulting the top stack symbol, whatever it may be, and replace it immediately.
And we know that there i8 at least one symbol in the stack: throughoutthe main computation ~apart from the start and final transitions~ the stacknever becomes empty. Notice also that at this stage we may introduce ,'s oflength two ~this does not violate the simplicity eondition, but is necessary forobtaining general pushdown automata.It is easy to see that this construction results in a simple pushdown automaton M' such that L(M) = L(M'). To continue the proof of the lemma, we shallexhibit a context-free grammar G such that L(G) = L(M'); this would concludethe proof of the lemma, and with it of Theorem 3.4.l.We let G = (V,~, R, S), where V contains, in addition to a new symbolS and the symbols in ~, a new symbol (q, A.,p) for all q,p E K' and each A Er U ie, Z}. To understand the role of the nonterminals (q, A,p), remember thatG is supposed to generate all strings accepted by M~ Therefore the nonterminalsof G stand for different parts of the input strings that are accepted by M~ Inparticular, if A E r, then the nonterminal (q,A.,p) represents any portion of theinput string that might be read between a point in time when M'is in state qwith A.
on top of its stack, and a point in time when M'removes that occurrenceof A from the stack and enters state p. If A = e, then (q, e,p) denotes a portionof the input string that might be read between a time when M'is in state q anda time when it is in state p with the same stack, without in the interim changingor consulting that part of the stack.The rules in R are of four types.(1) The rule S , (8, Z, 1'), where 8 is the start state of the original pushdownautomaton M and I' the new final state.(2) For each transition ((q,a,B), (r.C». where q,r E K: a E ~ U {e}, B,C Er U {e}, and for each p E K~ we add the rule (q, B,p) , a(r, C,p).(3) For each transition ((q,a,B), (r,C1 C 2 )), where q,r E K~ a E ~ U {e},B E r U {e}, and C 1 ,C2 E r and for each p,p' E K~ we add the rule(q, B,p) , a(r, C1 ,p')(p', C2 ,p).(4) For each q E K: the rule (q, e, q) , e.Note that, because M'is simple, either type 2 or type 3 applies to eachtransition of M~A rule of type 1 states essentially that any input string which can be readby M' passing from state s to the final state, while at the same time the net142Chapter 3: CONTEXT-FREE LANGUAGESeffect on the stack is that the stack bottom symbol was popped, is a string inthe language L(l'vIj.
A rule of type 4 says that no computation is needed to gofrom a state to itself without changing the stack. Finally, a rule of type 2 or 3says that, if ((q,a,B),(p,,» Ell', then one of the possible computations thatlead from state q to state p while consuming B (possibly empty) from the topof the stack, starts by reading input a, replacing B by " passing to state r.
andthen going on to consume, and end up in state p --reading whatever input isappropriate during such computation. If, = C 1 C2 , this last computation canin principle pass through any state p' immediately after C 1 is popped (this is atype-3 rule).These intuitive remarks are formalized in the following claim.Claim. For any q,p E K: A E r u {e}, and x E ~*,(q, A,p)=}a x if and only if (q, x, A) f-iw (p, e, e).iLemma 3.4.2, and with it Theorem 3.4.1, follows readily from the claim,since then (8, e, f)x for some f E F if and only if (8, x, e) f-M-' (f, e, e); thatis, x E L(G) if and only if x E L(l'vIj.Both directions of the claim can be proved by induction on the length eitherof the derivation of G or the eomputation of M; they are left as an exercise(Problem 3.4.5) .•=}aProblems for Section 3.43.4.1.
Carry out the construction of Lemma 3.4.1 for the grammar of Example3.1.4. Trace the operation of the automaton you have constructed on thein pu t string (() 0 ).3.4.2. Carry out the construction of Lemma 3.4.2 for the pushdown automatonof Example 3.3.2, and let G be the resulting grammar. What is the set{w E {a, b}* : (q, a,p)w}? Compare with the proof of Lemma 3.4.2.=}a3.4.3. Carry out the construction of Lemma 3.4.2 for the pushdown automaton ofExample 3.3.3. The resulting grammar will have 25 rules, but many canbe eliminated as useless. Show a derivation of the string aababbba in thisgrammar. (You may change the names of the nonterminals for clarity.)3.4.4.
Show that if M = (K,~, r, Ll, s, F) is a pushdown automaton, then thereis another pushdown automaton M' = (K',~, r, Ll', s, F) such that (M') =L(M) and for all ((q, u, ,8), (p,E Ll', 1,81 + hi :=:; 1.,»3.4.5. Complete the proof of Lemma 3.4.2.1433.5: Languages that Are and Are Not Context-Free3.4.6. A context-free grammar is linear if and only if no rule has as its righthand side a string with more than one nonterminal.
A pushdown automaton (K,~, r,~, s, F) is said to be single-turn if and only if whenever(s. w. e) 1-*(qI' WI' Yt) I- (qu W2. Yz) I-*(q:y w:y y:0 and I y21 < I yII then I y31 < I Y21.(That is, once the stack starts to decrease in height, it never again increasesin height.) Show that a language is generated by a linear context-free grammar if and only if it is accepted by a single-turn pushdown automaton.3.5LANGUAGES THAT ARE AND ARE NOT CONTEXT-FREEClosure PropertiesIn the last section, two views of context-free languages -as languages generatedby context-free grammars and as languages accepted by pushdown automata-~were shown to be equivalent.
These characterizations enrich our understanding of the context-free languages, since they provide two different methods forrecognizing when a language is context-free. For example, the grammaticalrepresentation is more natural and compelling in the case of a programminglanguage fragment such as that of Example 3.1.3; but the representation interms of pushdown automata is easier to see in the case of {w E {a, b}' :w has equal numbers of a's and b's} (see Example 3.3.3). In this subsection weshall provide further tools for establishing context-freeness: we show some closure properties of the context-free languages under language operations -verymuch in the spirit of the closure properties of regular languages.
In the nextsubsection we shall prove a more powerful pumping theorem which enables us toshow that certain languages are not context-free.Theorem 3.5.1: The context-free languages are closed under union, concatenation, and Kleene star.Proof:. Let G I = (VI, ~I' R I , St) and G2 = (V2, ~2' R 2, S2) be two context-freegrammars, and without loss of generality assume that they have disjoint sets ofnonterminals --that is, VI - ~I and V2 ~ ~2 are qisjoint.Union. Let S be a new symbol and let G = (VI U V2 U {S}, ~I u ~2, R, S),where R = RI U R2 U {S --+ SI, S --+ S2}.
Then we claim that L(G) = L(Gt} UL(G 2 ). For the only rules involving S are S --+ SI and S --+ S2, so Sw if andonly if either SIw or 8 2W; and since G I and G 2 have disjoint sets ofnonterminals, the last disjunction is equivalent to saying that wE L(GduL(G 2 ).Concatenation. The construction is similar: L(Gt}L(G 2 ) is generated bythe grammar=}a=}a=}aG = (VI U V2 U {S}, ~I U ~2, RI U R2 U {S --+ SlSd,S).Chapter 3: CONTEXT-FREE LANGUAGES144Kleene Star.
L(Gd* is generated by•As we shall see shortly, the class of context-free languages is not closed underintersection or complementation. This is not very surprising: Recall that ourproof that regular languages are closed under intersection depended on closureunder complementation; and that construction required that the automaton bedeterministic.
And not all context-free languages are accepted by deterministicpushdown automata (see the corollary to Theorem 3.7.1).There is an interesting direct proof of the closure under intersection ofregular languages, not relying on closure under complement, but on a directconstruction of a finite automaton whose set of states is the Cartesian productof the sets of states of the constituent finite automata (recall Problem 2.3.3).This construction cannot of course be extended to pushdown automata -theproduct automaton would have needed two stacks. However, it can be made towork when one of the two automata is finite:Theorem 3.5.2: The intersection of a context-free language with a regular language is a context-free language.Proof: If L is a context-free language and R is a regular language, thenL(Md for some pushdown automaton Ml = (K 1 ,I:,f1 ,6.
1 ,SI,F1 ), andL(M2) for some deterministic finite automaton M2 = (K2, I:, 6, S2, F2)'idea is to combine these machines into a single pushdown automaton Mcarries out computations by Ml and M2 in parallel and accepts only ifwould have accepted. Specifically, let M = (K, I:, f, 6., s, F), whereK= Klf=fXL =R =ThethatbothK 2, the Cartesian product of the state sets of Ml and M 2;1;s = (Sl, S2);F = Fl X F2, and6., the transition relation, is defined as follows. For each transition of thepushdown automaton ((ql,a,,B), (Pl,'Y)) E 6. 1 , and for each state q2 E K 2,we add to 6. the transition (( (ql, q2), a, 13), ((PI, 6( q2, a)), 'Y)); and for eachtransition of the form (( Ql, e, (3), (PI ,'Y)) E 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
