1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 27
Текст из файла (страница 27)
Similarly, the grammar givenin Example 3.1.4 for generating balanced strings of parentheses, which is alsoambiguous (as discussed at the end of Example 3.2.2, can be easily made unambiguous (see Problem 3.2.2). In fact, there are context-free languages with theproperty that all context-free grammars that generate them must be ambiguous.Such languages are called inherently ambiguous. Fortunately, programminglanguages are never inherently ambiguous.Problems for Section 3.23.2.1. Show that the context-free grammar G given in Example 3.1.3, which generates all arithmetic expressions over id, is unambiguous.3.2.2.
Show that the context-free grammar given in Example 3.1.4, which generates all strings of balanced parentheses is ambiguous. Give an equivalentunambiguous grammar.3.2.3. Consider the grammar of Example 3.1.3. Give two derivations of the stringid * id + id, one which is leftmost and one which is not leftmost.3.2.4. Draw parse trees for each of the following.(a) The grammar of Example 3.1.2 and the string "big Jim ate green cheese."(b) The grammar of Example 3.1.3 and the strings id + (id + id) * id and(id * id + id * id).Chapter 3: CONTEXT-FREE LANGUAGES130liiJPUSHDOWN AUTOMATANot every context-free language can be recognized by a finite autom~ton, since,as we have already seen, some context-free languages are not regular. Whatsort of more powerful device could be used for recognizing arbitrary context-freelanguages? Or, to be a bit more specific, what extra features do we need to addto the finite automata so that they accept any context-free language?To take a particular example, consider {ww R : w E {a, b}·}.
It is contextfree, since it is generated by the grammar with rules S ~ aSa, S ~ bSb, andS ~ e. It would seem that any device that recognizes the strings in this languageby reading them from left to right must "remember" the first half of the inputstring so that it can check it -in reverse order- against the second half of theinput. It is not surprising that this function cannot be performed by a finiteautomaton. If, however, the machine is capable of accumulating its input stringas it is read, appending symbols one at a time to a stored string (see Figure3-8), then it could nondeterministically guess when the center of the input hasbeen reached and thereafter check the symbols off from its memory one at atime.
The storage device need not be a general-purpose one. A sort of "stack"or "pushdown store," allowing read and write access only to the top symbol,would do nicely.InputaFinitecontrolbb"Stack"or"Pushdownstore"aFigure 3-8To take another example, the set of strings of balanced parentheses (Example 3.1.4) is also nonregular. However, computer programmers are familiar witha simple algorithm for recognizing this language: Start counting at zero, add onefor every left parenthesis, and subtract one for every right parenthesis. If thecount either goes negative at any time, or ends up different from zero, then thestring should be rejected as unbalanced; otherwise it should be accepted.
Now,3.3: Pushdown Automata131a counter can be considered as a special case of a stack, on which only one kindof symbol can be written.To address this question from yet another point of view, rules such as A -+aB are easy to simulate by a finite automaton, as follows: "If in state A readinga, go to state B." But what about a rule whose right-hand side is not a terminalfollowed by a nonterminal, say the rule A -+ aBb? Certainly the machine mustagain go from state A to state B reading a, but what about b? What furtheraction would allow us to remember the presence of b in this rule? A stack wouldbe handy here: By pushing b on the top of a stack, we resolve to remember itand act upon it when it resurfaces again -presumably to be checked against ab in the input.The idea of an automaton with a stack as auxiliary storage can be formalizedas follows.Definition 3.3.1: Let us define a pushdown automaton to be a sextupleM = (K,I:,r,~,s,F), whereK is a finite set of states,I: is an alphabet (the input symbols),r is an alphabet (the stack symbols),s E K is the initial state,F ~ K is the set of final states, and~, the transition relation, is a finite subset of (K x (I: U {e}) x r*) x(K x r*).Intuitively, if ((p, a, (3), (q, ,)) E ~, then M, whenever it is in state p with f3at the top of the stack, may read a from the input tape (if a = e, then the inputis not consulted), replace f3 by , on the top of the stack, and enter state q.
Sucha pair ((p, a, (3), (q, ,)) is called a transition of M; since several transitions of Mmay be simultaneously applicable at any point, the machines we are describingare nondeterministic in operation. (We shall later alter this definition to definea more restricted class, the deterministic pushdown automata.)To push a symbol is to add it to the top of the stack; to pop a symbol is toremove it from the top of the stack.
For example, the transition ((p, u, e), (q, a))pushes a, while ((p,u,a),(q,e)) pops a.As is the case with finite automata, during a computation the portion of theinput already read does not affect the subsequent operation of the machine. Accordingly, a configuration of a pushdown automaton is defined to be a memberof K x I:* x r*: The first component is the state of the machine, the second is theportion of the input yet to be read, and the third is the contents of the pushdownstore, read top-down. For example, if the configuration were (q, W, abc), the awould be on the top of the stack and the c on the bottom.
If (p, x, Cl:) and (q, y, ()Chapter 3: CONTEXT-FREE LANGUAGES132are configurations of M, we say that (p,x,a) yields in one step (q,y,() (notation: (p,x,a) f-M (q,y,()) if there is a transition ((p,a,(3),(q,,)) E ~ suchthat x = ay, a = (3T], and ( = ,T] for some T] E r*. We denote the reflexive,transitive closure of f- M by f- M. We say that M accepts a string w E ~*if and only if (s, w, e) f-M (p, e, e) for some state p E F. To put it anotherway, M accepts a string w if and only if there is a sequence of configurationsCO,Cl, ... ,Cn (n > 0) such that CO f-M C l f-M ... f-M Cn , Co = (s,w,e), andCn = (p, e, e) for some p E F.
Any sequence of configurations Co, C l , ... , Cnsuch that C i f- M CHI for i = 0, ... , n - 1 will be called a computation by M;it will be said to have length n, or to have n steps. The language acceptedby M, denoted L(M), is the set of all strings accepted by M.When no confusion can result, we write f- and f-* instead of f- M and f- M.Example 3.3.1: Let us design a pushdown automaton M to accept the languageL = {wcw R : w E {a, b}*}.
For example, ababcbaba E L, but abcab ~ L, andcbc ~ L. We let M = (K,~,r,~,s,F), where K = {s,f}, ~ = {a,b,c},r = {a, b}, F = {f}, and ~ contains the following five transitions.(1)(2)(3)(4)(5)((s,a,e),(s,a))((s,b,e),(s,b))(( s, c, e), (f, e))((f,a,a),(f,e))((f,b,b),(f,e))This automaton operates in the following way. As it reads the first halfof its input, it remains in its initial state s and uses transitions 1 and 2 totransfer symbols from the input string onto the pushdown store. Note thatthese transitions are applicable regardless of the current content of the pushdownstore, since the "string" to be matched on the top of the pushdown store is theempty string.
When the machine sees a c in the input string, it switches fromstate s to state f without operating on its stack. Thereafter only transitions 4and 5 are operative; these permit the removal of the top symbol on the stack,provided that it is the same as the next input symbol. If the input symboldoes not match the top symbol on the stack, no further operation is possible. Ifthe automaton reaches in this way the configuration (f, e, e) -final state, endof input, empty stack -then the input was indeed of the form wcw R , and theautomaton accepts. On the other hand, if the automaton detects a mismatchbetween input and stack symbols, or if the input is exhausted before the stackis emptied, then it does not accept.To illustrate the operation of M, we describe a sequence of transitions forthe input string abbcbba.Example 3.3.2: Now we construct a pushdown automaton to accept L ={ww R : w E {a, b}*}.
That is, the strings accepted by this machine are the3.3: Pushdown AutomataState133Unread InputStackabbcbbabbcbbabcbbacbbabbabaaeeababbabbabaaessssjjfjTransition Used1223554same as those accepted by the machine of the previous example, except that thesymbol c that marked the center of the strings is missing. Therefore the machinemust "guess" when it has reached the middle of the input string and change fromstate s to state f in a nondeterministic fashion. Thus M = (K, I:, r,~, s, F),where K = {s,f}. I: = {a, b}, F = {f}, and ~ is the set of the following fivetransitions.(1)(2)(3)(4)(5)((s,a,e), (s,a))((s, b, e), (s, b))((s,e,e),(j,e))((f,a,a),(f,e))((j,b,b),(j,e))Thus this machine is identical to that of the last example, except for transition 3.
Whenever the machine is in state s, it can nondeterministically chooseeither to push the next input symbol onto the stack, or to switch to state jwithout consuming any input. Therefore even starting from a string of the formww R , M has computations that do not lead it to the accepting configuration(f, e, e)j but there is some computation that leads M to this configuration if andonly if the input string is of this form.OExample 3.3.3: This pushdown automaton accepts the language {w E {a, b}· :a's and b's}.
Either a string of a's or a string of b's iskept by M on its stack. A stack of a's indicates the excess of a's over b's thus farread, if in fact M has read more a's than b'sj a stack of b's indicates the excessof b's over a's. In either case, M keeps a special symbol c on the bottom of thestack as a marker. Let M = (K, I:, r,~, s, F), where K = {s, q, f}, I: = {a, b},r = {a,b,c}, F = {f}, and ~ is listed below.w has the same number of(1) ((s,e,e),(q,c))(2) ((q,a,c),(q,ac))(3) ((q, a, a), (q, aa))Chapter 3: CONTEXT-FREE LANGUAGES134(4) ((q,a,b), (q,e))(5) ((q,b,e),(q,be))(6) ((q,b,b),(q,bb))(7) ((q,b,a),(q,e))(8) ((q,e,e), (i,e))Transition 1 puts M in state q while placing a e on the bottom of the stack.In state q, when M reads an a, it either starts up a stack of a's from the bottom,while keeping the bottom marker (transition 2), or pushes an a onto a stack ofa's (transition 3), or pops a b from a stack of b's (transition 4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
