CSC 341: February 16, 2007

From CSWiki

Jump to: navigation, search

Previous Lecture Next Lecture

Contents

[edit]

Instructor's notes for the class session

[edit]

Theorem 2.20: A language is context-free if, and only if, some pushdown automaton recognizes it.

The theorem is an implicit universal quantification ("For every language, ...") enclosing a biconditional. For the universal quantification, we use the pattern of showing that the enclosed proposition holds for an arbitrary language about which we start with no assumptions. For the enclosed biconditional, we use the "first left to right, then right to left" pattern, breaking it into two conditionals (Lemmas 2.21 and 2.27). For each conditional, we use the pattern of assuming the protasis and deducing the apodosis from it. And each of those deductions is a proof by construction of an existential quantification.

[edit]

Lemma 2.21: If a language is context-free, then some pushdown automaton recognizes it.

Suppose A is context-free. By definition (an unnumbered definition on page 101 of Sipser), there is a context-free grammar (V,Σ,R,S) that generates A. The goal is to construct a pushdown automaton that somehow simulates or reflects the capabilities of this grammar so closely that it recognizes the same language, A. We can design the PDA incrementally as follows:

  1. The input alphabet for the pushdown automaton is Σ.
  2. Its stack alphabet is V \cup \Sigma.
  3. Begin with a start state, qstart.
  4. Add a new state (unlabelled in Sipser) and a transition to it from qstart, reading no input, popping nothing from the stack, and pushing a bottom-of-stack marker $ onto the stack.
  5. Add another new state, qloop, and a transition to it from the unlabelled state just mentioned, reading no input, popping nothing from the stack, and pushing the start symbol onto the stack.
  6. For each symbol a \in \Sigma, add a transition from qloop to qloop that reads a from the input, pops a from the stack, and pushes nothing onto the stack. This transition cannot be used unless the same symbol appears both in the input and on top of the stack, so in effect it matches the input symbol to the stack symbol, discarding both.
  7. Now go through the rules of the grammar. For each rule, our objective is to give the automaton the option of replacing the variable on the left-hand side of the rule, when it appears on top of the stack, with the symbols on the right-hand side of the rule.
    1. If the right-hand side of the rule is \varepsilon, add a transition from qloop to qloop that reads nothing from the input, pops the left-hand-side variable from the stack, and pushes nothing onto the stack.
    2. If the right-hand side of the rule is a single symbol, either a variable or a terminal, add a transition from qloop to qloop that reads nothing from the input, pops the left-hand-side variable from the stack, and pushes the right-hand-side symbol onto the stack.
    3. Otherwise, let n be the number of symbols on the right-hand side. We'll need to add n − 1 extra states q_1, \ldots, q_{n - 1} to the automaton, since we'll have to push those symbols onto the stack one by one. Also, add a transition from qloop to q1, reading nothing from the input, popping the left-hand-side variable from the stack, and pushing the last of the right-hand-side symbols onto the stack; we push the last symbol to be matched onto the stack first so that it will be the one farthest down when we get back to qloop. Then we add transitions from q1 to q2, from q2 to q3, and so on, each time reading nothing from the input, popping nothing from the stack, and pushing the rightmost remaining symbol from the right-hand side onto the stack. Finally, to deal with the first of the symbols from the right-hand side, we add a transition from qn − 1 to qloop.
  8. Finally, we add one more state, qaccept, which is the only accept state, and one more transition, from qloop to qaccept, reading nothing from the input, popping the bottom-of-stack marker from the stack, and pushing nothing onto the stack.

Sipser, exercise 2.11.

Any leftmost derivation in the grammar can now be simulated on the PDA that we have constructed, and any accepting computation in the PDA can be simulated by a derivation in the grammar, so the language generated by the grammar and the language recognized by the PDA are identical.

[edit]

Lemma 2.27: For any pushdown automaton P, the language recognized by P is context-free.

Without loss of generality ... This handy phrase typically occurs near the beginning of a proof and signals that some kind of preprocessing may be needed to establish some assertion that is subsequently assumed. There may be some previously proven theorem or lemma that establishes that the preprocessing can always be done, or in some cases in may be obvious.

Question: Is it obvious that, for any pushdown automaton, there is an equivalent pushdown automaton that has a single accept state, empties its stack before accepting, and has only transitions that pop without pushing or push without popping?

Given such a PDA, (Q,Σ,Γ,δ,q0,F), we construct an equivalent grammar:

  1. The variables are Apq for all p, q \in Q.
  2. The start symbol is A_{q_0, q_\mathrm{accept}}.
  3. The terminals are the elements of the PDA's input alphabet.
  4. Go through the transition function of the PDA and find all the cases in which (r, t) \in \delta(p, a, \varepsilon) and (q, \varepsilon) \in \delta(s, b, t), for any p, q, r, s \in Q, any t \in \Gamma, and any a, b \in \Sigma_\varepsilon. Each time this configuration is found, add the rule A_{pq} \rightarrow a A_{rs} b to the grammar.
  5. For all p, q, r \in Q, add the rule A_{pq} \rightarrow A_{pr} A_{rq} to the grammar.
  6. For all p \in Q, add the rule A_{pp} \rightarrow \varepsilon to the grammar.

The idea is that a string of terminals can be derived from a variable Apq in this grammar if, and only if, it can drive the pushdown automaton from state p (and an empty stack) to state q (leaving the stack empty). The fact that the grammar generates the same language as the PDA is then the special case in which p = q0 and q = qaccept.

Now we can simulate any computation in the PDA in the grammar (Claim 2.31) and any computation in the grammar in the PDA (Claim 2.30), so again the language recognized by the PDA is identical with the language generated by the grammar.

[edit]

Study questions

  1. Sipser says that "every finite automaton is automatically a pushdown automaton that ignores its stack" (page 122), but that is technically not quite correct, because of the differences between the formal definitions of the two categories. Given a deterministic finite automaton M = (Q,Σ,δ,q0,F), how would you construct a pushdown automaton P = (Q',Σ,Γ,δ',q0',F') that recognizes the same language?
  2. Sipser's solution (page 133) to Problem 2.18 omits a key part of the construction: the transition function for the pushdown automaton P'. Remedy this defect by giving a complete definition of that function.
  3. Using the construction plan that Sipser presents in his proof of Lemma 2.27, construct a context-free grammar that generates the language that the pushdown automaton M3 (in Example 2.18) recognizes.
[edit]

Proposed Solutions

  1. Q' = Q; Γ = {}; If δ(qi,a) = qj for some q_i, q_j \in Q, and some a \in \Sigma, then \delta'(q_i, a, \varepsilon) = (q_j, \varepsilon).



Previous Lecture Next Lecture

Front Door

Retrieved from "http://wiki.cs.grinnell.edu/mediawiki/index.php/CSC_341:_February_16%2C_2007"
Personal tools