6.5 Summary of Chapter 6

f Pushdown Automata: A PDA is a nondeterministic finite automaton coupled with a stack that can be used to store a string of arbitrary length. The stack can be read and modified only at its top.

f Moves of a Pushdown Automata: A PDA chooses its next move based on its current state, the next input symbol, and the symbol at the top of its stack. It may also choose to make a move independent of the input symbol and without consuming that symbol from the input. Being nondeterministic, the PDA may have some finite number of choices of move; each is a new state and a string of stack symbols with which to replace the symbol currently on top of the stack.

-f Acceptance by Pushdown Automata: There are two ways in which we may allow the PDA to signal acceptance. One is by entering an accepting state; the other- by emptying its stack. These methods are equivalent, in the sense that any language accepted by one method is accepted (by some other PDA) by the other method.

f Instantaneous Descriptions: We use an ID consisting of the state, remaining uiput, and stack contents to describe the current condition of a PDA. A transition function h between IDs represents single moves of a PDA.

+ Pushdown AutoTnata and Grammars: The languages accepted by PDAs either by final state or by empty stack, are exactly the context-free languages.

4- Deterministic Pushdown Automata: A PDA is deterministic if it never has a choice of move for a given state, input symbol (including e), and stack symbol- Also, it never has a choice between making a move using a true input and a move using e input.

4- Acceptance by Deterministic Pushdown Automata: The two modes of acceptance - final state and empty stack - are not the same for DPDAs. Rather, the languages accepted by empty stack are exactly those of the languages accepted by final state that have the prefix property: no string in the language is a prefix of another word in the language.

♦ The Languages Accepted by DPDAs: All the regular languages are accepted (by final state) by DPDAs, and there are nonregular languages accepted by DPDAs. The DPDA languages are context-free languages, and in fact are languages that have unambiguous CFGs. Thus, the DPDA languages lie strictly between the regular languages and the context-free languages.

6.6. REFERENCES FOR CHAPTER 6 253

6.6 References for Chapter 6

The idea of the pushdown automaton is attributed independently to Oettinger [4] and Schutzenberger [5]. The equivalence between pushdown automata and context-free languages was also the result of independent discoveries; it appears in a 1961 MIT technical report by N. Chomsky but was first published by Evey

[1]-

The deterministic PDA was first introduced by Fischer [2] and Schutzenberger [5]. It gained significance later as a model for parsers. Notably, [3] introduces the LR(k] grammars, a subclass of CFGs that generate exactly the DPDA languages. The LR{k) grammars, in turn, form the basis for YACC, the parser-generating tool discussed in Section 5.3.2.

1. J. Evey, Application of pushdown store machines, Pwc. Fall Joint Computer Conference (1963), AFIPS Press, Montvale, NJ, pp. 215-227.

2. P. C. Fischer, On computability by certain classes of restricted Turing machines, Proc. Fourth Annl. Symposium on Switching Circuit Theory and Logical Design (1963), pp. 23-32.

3. D. E. Knuth, On the translation of languages from left to right, Information and Control 8:6 (1965), pp. 607-639.

4. A. G. Oettinger, Automatic syntactic analysis and the pushdown store, Proc. Symposia on Applied Math. 12 (1961), American Mathematical Society, Providence, RI.

5. M. P. Schutzenberger, On context-free languages and pushdown automata, Information and Control 6:3 (1963), pp. 246-264.

Chapter 7

Properties of Context-Free Languages

We shall complete our study of context-free languages by learning some of their properties. Our first task is to simplify context-free grammars; these simplifications make it easier to prove facts about CFLs, since we can claim that if a language is a CFL, then it has a grammar in some special form.

We then prove a pumping lemma for CFLs. This theorem is in the .same spirit as Theorem 4.1 for regular languages, but can be used to prove a language not to be context-free. Next, we consider the sorts of properties that we studied in Chapter 4 for the regular languages: closure properties and decision properties. We shall see that some, but not all, of the closure properties that the regular languages have are also possessed by the CFLs. Likewise, some questions about CFLs can be decided by algorithms that generalize the tests we developed for regular languages, but there are also certain questions about CFLs that we cannot answer.

7.1 Normal Forms for Context-Free Grammars

The goal of this section is to show that every CFL (without e) is generated by a CFG in which all productions are of the form .4 -> ВС от A a, where ,4, B, and С are variables, and a is a terminal. This form is called Chamsky Normal Form. To get there, we need to make a number of preliminary simplifications, which are themselves useful in various ways:

1. We must eliminate useless symbols, those \ariables or terminals that do not appear in any derivation of a terminal string from the start symbol.

2. We must eliminate t-productions, those of the form A-y t for some variable A.