1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 28
Текст из файла (страница 28)
When reading ab from the input, the machine acts analogously, pushing a b onto a stack of b'sor a stack consisting of just a bottom marker, and popping an a from a stack ofa's (transitions 5, 6, and 7). Finally, when e is the topmost (and therefore theonly) symbol on the stack, the machine may remove it and pass to a final state(transition 8). If at this point all the input has been read, then the configuration(j, e, e) has been reached, and the input string is accepted.The following table contains an illustration of the operation of M.StatesqqqqqqqqqfUnread InputStackabbbabaaabbbabaabbbabaabbabaababaaabaabaaaaaebebbcbebbcbeeee44e8eaceTransition12756CommentsInitial configuration.Bottom marker.Start a stack of a's.Remove one a.Start a stack of b's.46Accepts.0Example 3.3.4: Every finite automaton can be trivially viewed as a pushdown automaton that never operates on its stack.
To be precise, let M =(K, I:,~, s, F) be a nondeterministic finite automaton, and let M' be the pushdown automaton (K, I:, 0,~', s, F), where~' = {((p, '11" e), (q, e)) : (p, '11" q) E ~}.In other words, M' always pushes and pops an empty string on its stack, andotherwise simulates the transitions of M. Then it is immediate that M and M'accept precisely the same language.O3.3: Pushdown Automata135Problems for Section 3.33.3.1. Consider the pushdown automaton M= (K,~, r, 6, s, F),whereK={s,f},F = {f},~ = {a, b},r = {a},6 = {( (s, a, e), (s, a)), « s, b, e), (s, a)), « s, a, e), (f , e)),«(f, a, a), (f, e)), «(f, b, a), (f, e))}.(it) Thace all possible sequences of transitions of M on input aba.(b) Show that aba, aa, abb ~ L( !vI), but baa, bab, baaaa E L( M).(c) Describe L(M) in English.3.3.2.
Construct pushdown automata that accept each of the following.(a) The language generated by the grammar G = (V,~, R, S), wherev={S, (, ), [, ]},~= {(,),[,]},R= {S --+ e,S --+ SS,S --+ [S],S --+ (S)}.(b) The language {amb n : m ~ n ~ 2m}.(c) The language {w E {a, b}* : w = w R }.(d) The language {w E {a, b}*: w has twice as many b's as a's}.3.3.3. Let M = (K,~, r, 6, s, F) be a pushdown automaton. The language accepted by M by final state is defined as follows:L,(M) = {w E~*: (s,w,e)f-~(f,e,a) for some f E F,a E r*}.a) Show that there is a pushdown automaton M' such that L(M') = L,(M).b) Show that there is a pushdown automaton M" such that L,(M")L(M).Chapter 3: CONTEXT-FREE LANGUAGES1363.3.4.
Let M = (K" I:, r,~, s, F) be a pushdown automaton. The languageaccepted by M by empty store is defined as follows:Le(M) = {w(a) ShowL(M).(b) ShowLe(M).(c) ShowLe(M) =3.4EI:* : (s, w, e)f-M(q, e, e) for some q E K}.that there is a pushdown automaton M' such that Le(M')that there is a pushdown automaton M" such that L(M")by a counterexample that it is not necessarily the case thatL(M) U {e}.PUSHDOWN AUTOMATA AND CONTEXT-FREE GRAMMARSIn this section we show that the pushdown automaton is exactly what is neededto accept arbitrary context-free languages. This fact is of mathematical andpractical significance: mathematical, because it knits together two different formal views of the same class of languages; and practical, because it lays thefoundation for the study of syntax analyzers for "real" context-free languagessuch as programming languages (more on this in Section 3.7).Theorem 3.4.1: The class of languages accepted by pushdown automata is exactly the class of contel:t-free languages.Proof: We break this proof into two parts.Lemma 3.4.1: Each context-free language is accepted by some pushdown automaton.Proof: Let G = (V, I:, R, S) be a context-free grammar; we must construct apushdown automaton M such that L(M) = L(G).
The machine we constructhas only two states, p and q, and remains permanently in state q after its firstmove. Also, M uses V, the set of terminals and nonterminals, as its stackalphabet. We let M = ({p, q}, I:, V, ~,p, {q}), where ~ contains the followingtransitions:(1) ((p, e, e), (q, S))(2) ((q, e, A), (q, x)) for each rule A -+ x in R.(3) ((q,a,a),(q,e)) for each aE I:.The pushdown automaton M begins by pushing S, the start symbol of G,on its initially empty pushdown store, and entering state q (transition 1).
Oneach subsequent step, it either replaces the topmost symbol A on the stack,1373.4: Pushdown Automata and Context-Free Grammarsprovided that it is a nonterminal, by the right-hand side x of some rule A -+ xin R (transitions of type 2), or pops the topmost symbol from the stack, providedthat it is a terminal symbol that matches the next input symbol (transitions oftype 3). The transitions of M are designed so that the pushdown store duringan accepting computation mimics a leftmost derivation of the input string; Mintermittently carries out a step of such a derivation on the stack, and betweensuch steps it strips away from the top of the stack any terminal symbols andmatches them against symbols in the input string. Popping the terminals fromthe stack has in turn the effect of exposing the leftmost nonterminal, so that theprocess can continue.Example 3.4.1: Consider the grammar G = (V,L,R,S) with V = {S,a,b,c},L = {a, b, e}, and R = {S -+ aSa, S -+ bSb, S -+ e), which generates thelanguage {wcw R : w E {a, b}*}.
The corresponding pushdown automaton, according to the construction above, is M = ({p, q}, L, V, b., p, {q} ), with(Tl)b. = {((p, e, e), (q, S)),((q, e, S), (q, aSa)),((q, e, S), (q, bSb)),((q, e, S), (q, e)),((q, a, a), (q, e)),((q, b, b), (q, e)),((q, c,c), (q,e))}(T2)(T3)(T4)(T5)(T6)(T7).The string abbebba is accepted by M through the following sequence of moves.StatepqqqqqqqqqqqqUnread InputStackabbebbaeabbebbaSaSaabbcbbaSabbebbabbebba bSbabcbbaSbabebba bSbbaebba SbbaebbaebbabbabbababaaaeeTransition Used-TlT2T5T3T6T3T6T4T7T6T6T5Chapter 3: CONTEXT-FREE LANGUAGES138Compare this to the operation, on the same string, of the pushdown automaton of Example 3.3.1.0To continue the proof of the Lemma, in order to establish that L(M)L( G), we prove the following claim.Claim.
Let w E L* and 0: E (V - L)V* U {e}. Then S ~ * wo: if and only if(q,w,S) f-M (q,e,o:).This claim will suffice to establish Lemma 3.4.1, since it will follow (bytaking 0: = e) that S ~ * w if and only ifw E L(G) if and only if wE L(M).(q, e, S)f-M(q, e, e) ~in other words,(Only if) Suppose that S ~ * wo:, where w E L*, and 0: E (V - L)V* U {e}.We shall show by induction on the length of the leftmost derivation of w fromS that (q,w,S) f-M (q,e,o:).Basis Step.
If the derivation is of length 0, then w = e, andindeed (q,w,S) f-M (q,e,o:).0:= S, and henceInduction Hypothesis. Assume that if S ~ * wo: by a derivation of length n orless, n 2 0, then (q,w,S) f-M (q,e,o:).Induction Step. LetS= Uo :i Ul ~ ... ~ Un ~ Un+l = wo:be a leftmost derivation of wo: from S.
Let A be the leftmost nonterminal ofUn. Then Un = xA,8, and Un+l = x,,8, where x E L*, ,8"E V*, and A --+ , isa rule in R. Since there is a leftmost derivation of length n of Un = xA,8 fromS, by the induction hypothesisf-M(q, e, A,8).(2)(q,e,A,8) f-M (q,e",8),(3)(q, x, S)Since A --+ , is a rule in R,by a transition of type 2.Now notice that Un+l is wo:, but it is also x,,8.
Hence, there is a stringy E L* such that w = xy and yo: = ,,8. Thus, we can rewrite (2) and (3) aboveas(4)(q, w, S) f-M (q, y, ,,8).However, Since yo: = ,,8,(q,y",8)by a sequence ofinduction step.Iylf-M(q,e,o:),(5)transitions of type 3. Combining (4) and (5) completes the1393.4: Pushdown Automata and Context-Free Grammars(If) Now suppose that (q, w, S)f-'M(q, e, 0'.) withWE L* and 0'. E (V - L)V* U{e}; we show that S ~ * WO'.. Again, the proof is by induction, but this time onthe number of transitions of type 2 in the computation by M.Basis Step. Since the first move in any computation is by a transition of type 2,if (q,w,S) f-'M (q,e,O'.) with no type-2 transitions, then w =:: e and 0: =:: S, andthe result is true.Induction Hypothesis.
If (q,w,S)steps or fewer, n ? 0, then Sf-'M(q,e,O'.) by a computation with n type 2~ * WO'..Induction Step. Suppose that (q,w,S) f-'M (q,e,O'.) in nand consider the next-to-Iast such transition, say,(q,w,S)where w= xyf-'M(q,y,A(3)f-M(q,y,,(3)for some x, y E L*, and A---+,f-'M+ 1 type-2transitions,(q,e,O'.),is a rule of the grammar. Bythe induction hypothesis we have that S ~. xA(3, and thus S ~ * x,(3. Sincehowever (q,y,,(3) f-'M (q,e,O'.), presumably by transitions of type 3, it followsthat yO'. =:: ,(3, and thus S ~ * xyO'. = WO'..
This completes the proof of Lemma3.4.1, and with it half the proof of Theorem 3.4.1. •We now turn to the proof of the other half of Theorem 3.4.1.Lemma 3.4.2: If a language is accepted by a pushdown automaton, it is acontext-free language.Proof: It will be helpful to restrict somewhat the pushdown automata underconsideration. Call a pushdown automaton simple if the following is true:Whenever (( q, a, (3), (p, ,)) is a transition of the pushdown automaton andq is not the start state, then (3 E r, and hi ::; 2.In other words, the machine always consults its topmost stack symbol (andno symbols below it), and replaces it either with e, or with a single stack symbol,or with two stack symbols.
Now it is easy to see that no interesting pushdownautomaton can have only transitions of this kind, because then it would not beable to operate when the stack is empty (for example, it would not be able tostart the computation, since in the beginning the stack is empty). This is whywe do not restrict transitions from the start state.We claim that if a language is accepted by an unrestricted pushdown automaton, then it is accepted by a simple pushdown automaton. To see this, letfl.1 = (K, L, r,~, s, F) be any pushdown automaton; we shall construct a simplepushdown automaton M' = (KI, L, ru {Z}, ~/, Sl, {f}) that also accepts L(M);Chapter 3: CONTEXT-FREE LANGUAGES140here s' andf'are new states not in K, and Z is a new stack symbol, the stackr. We first add to ~ the transition (( s' , e, e), (s, Z));this transition starts the computation by placing the stack bottom symbol inthe bottom of the stack, where it will remain throughout the computation.
Norule of t1 will ever push a Z in the stack -except to replace it at the bottomof the stack. We also add to t1 the transitions (if. e. Z). (/', e)) for each f E F.These transitions end the computation by removing Z from the bottom of thestack and accepting the input seen so far.Initially, ~' consists of the start and final transitions described above, andall transitions of ~. We shall next replace all transitions in ~' that violate thesimplicity condition by equivalent transitions that satisfy the simplicity condition.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
