UMass Amherst LINGUIST 726 - Push-Down Storage Automata and Context-Free Grammars

Unformatted text preview:

Ling 726: Mathematical Linguistics, Lecture 16 PDAs and CFGs V. Borschev and B. Partee, November 9, 2006 p. 1 Lecture 16. Push-Down Storage Automata and Context-Free Grammars 1. Pushdown automata .............................................................................................................................................1 2. Context-free grammars and languages .................................................................................................................3 3. Pumping theorem for context-free languages.......................................................................................................3 4. Closure properties of context free languages. ......................................................................................................3 5. Decidability properties of context free languages. ..............................................................................................4 6. Are natural languages context-free?.....................................................................................................................5 7. Issues concerning the difficulty of processing nested and serial dependencies...................................................6 References................................................................................................................................................................7 Reading: Chapter 18, “Pushdown Automata, Context Free Grammars and Languages” of PtMW, pp. 485-504. See also References at the end of this handout. 1. Pushdown automata A pushdown automaton, or pda, is essentially a finite state automaton augmented with an auxiliary tape on which it can read, write, and erase symbols. Its transitions from state to state can depend not only on what state it is in and what it sees on the input tape but also on what it sees on the auxiliary state, and its actions can include not only change of state but also operations on the auxiliary tape. The auxiliary tape works as a pushdown store, “last in, first out”, like a stack of plates in some cafeterias. You can’t ‘see’ below the top item on the stack without first removing (erasing) that top item. States: as in a fsa, a pda has a finite number of states, including a designated initial state and a set of “final” or “accepting” states. Transitions: (qi, a, A) → (qj, γ), where qi, qj are states, a is a symbol of the input alphabet, A is either the empty string e or a symbol of the stack alphabet (which need not be the same as the input alphabet), and γ is a string of stack symbols, possibly the empty string. Interpretation: When in state qi, reading a on the input tape, and reading A at the top of the stack, go to state qj, and replace A by the string γ. The elements of the string γ go onto the stack one at a time, so the last symbol of γ ends up as the top symbol on the stack. In case γ is the empty string e, the effect is to erase γ, that is to remove it (“pop” it) from the stack. (“Push” down and “pop” up.) Examples of A and of γ, and their effects. First suppose that A is a particular symbol (and let’s just call it A.) If γ is BC, the result is to remove A, and add B on the top of the stack, and then add C on top of B. If γ is e, the result is to remove A, and the new top symbol will be whatever was just below A, if anything. If γ is AB, the result is to add a B on top of the A that was there. If γ is A, then the stack will be unchanged. If A is e, that means that the transition does not depend on what’s on the stack; it does not mean that the stack must be empty. (We don’t have any special way of indicating that the stack isLing 726: Mathematical Linguistics, Lecture 16 PDAs and CFGs V. Borschev and B. Partee, November 9, 2006 p. 2 empty, though you can design an individual machine to start by putting some particular symbol on the stack, and to be sensitive to when it sees that symbol again as a way of knowing its stack is empty except for that one symbol.) If A is e and γ is also e, the stack stays unchanged. Otherwise γ is added to the stack. Initial configuration: the stack is assumed to be empty at the beginning of a computation, with the pda in its initial state and the reading head looking at the first (leftmost) symbol on the input tape. A pda accepts an input tape if the computation leads to a situation in which all three of the following are simultaneously true: (i) the entire input has been read; (ii) the pda is in a final (accepting) state; (iii) the stack is empty. Example 1. A deterministic pda for the classic context-free and non-finite-state language {anbn | n ≥ 0}. (on blackboard. See p. 486.) Example 2: A pda for another classic context-free and non-finite-state language: {xxR | x ∈ {a, b}* } (on blackboard. See pp 487-8.) This machine is non-deterministic. Acceptance for non-deterministic vs deterministic machines is defined just as for finite state automata: a non-deterministic pda accepts a string iff there is some computation which leads to acceptance. The natural question: are deterministic and non-deterministic pda’s equivalent? Answer: NO. The proof is not simple and it isn’t included in PtMW. Intuitively, in the given case, we can see that there is no deterministic way for a pda to know when it is at the middle of the string in Example 2, and it needs to know that in order to know when to stop adding symbols and start matching and erasing. By contrast, the language {xcxR | x ∈ {a, b}* }, in which the center is marked by a distinctive symbol c, is acceptable by a deterministic pda. Example 3: A pda for the language of exercise 1c, p. 503: L3 = {x| x ∈ {a, b}* and x contains twice as many b’s as a’s } Note: both example 3 and example 1 can be done with a 1-symbol pushdown alphabet; these are sometimes called “counter machines”, since they are not requiring the full power of a pushdown store with arbitrary alphabet. The mirror-image language, by contrast, requires as many distinct symbols in the pushdown alphabet as there are in the input alphabet.Ling 726: Mathematical Linguistics, Lecture 16 PDAs and CFGs V. Borschev and B. Partee, November 9, 2006 p. 3 2. Context-free grammars and languages Non-deterministic pda’s accept exactly the languages generated by context-free (Type 2) grammars. The regular languages are a proper subset of the context-free languages. The


View Full Document

UMass Amherst LINGUIST 726 - Push-Down Storage Automata and Context-Free Grammars

Download Push-Down Storage Automata and Context-Free Grammars
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Push-Down Storage Automata and Context-Free Grammars and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Push-Down Storage Automata and Context-Free Grammars 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?