CSC 341: February 14, 2007

From CSWiki

Jump to: navigation, search

1 Instructor's notes for the class session
- 1.1 Leftovers
- 1.2 Pushdown automata
2 Study questions
- 2.1 Proposed Solutions

[edit]

Instructor's notes for the class session

[edit]

Leftovers

Demonstrate the Chomsky-normal-form module.

[edit]

Pushdown automata

The rationale for nondeterminism.

Popping and pushing the stack memory; the independence of the stack alphabet from input.

Definition 2.13 -- the structure of the device.

$\varepsilon$ means "consume no input," "don't pop the stack," or "don't push anything onto the stack," depending on context.

The domain and range of the transition function in a (nondeterministic) pushdown automaton.

Sipser's pushdown automata can accept strings even when their stacks aren't empty; some authors define acceptance in such a way that it occurs only if the stack is empty. This difference isn't very significant, since the power of the model of computation is the same either way -- every language that is recognized by any pushdown automaton is recognized by a pushdown automaton that empties its stack.

Examples of pushdown automata, including a trace of a computation.

Statement of Theorem 2.20: A language is context-free if, and only if, there is a pushdown automaton that recognizes it.

[edit]

Study questions

In each cycle of the operation of a PDA, there are three steps, each in effect optional (since the datum can be $\varepsilon$ ): popping a symbol from the stack, pushing a symbol onto the stack, and reading a character from the input. Do these steps have to be done in any particular order? How do these steps correspond to the three symbols in the label $a,b\rightarrow c$ on an arc in a state diagram?
Are there any conditions in which the PDA $M 1$ (in Example 2.14, page 112 of the text) uses nondeterminism, or is its behavior fixed in all situations? Does this imply that $\{\texttt{0}^n \texttt{1}^n \mid n \ge 0\}$ could be recognized by a deterministic pushdown automaton?
In the state diagram in Figure 2.17 (page 114 of the text), why is the label on the arc from $q 3$ to $q 4$ $\varepsilon,\texttt{\$}\rightarrow\varepsilon$ rather than $\varepsilon,\varepsilon\rightarrow\varepsilon$ ? Why not defer the test for the bottom of the stack until after the $\texttt{c}$ s in the input have been consumed?

[edit]

Proposed Solutions

If you tried to push a symbol before you popped a symbol, you would always get back what you'd just pushed, so the "pushdown" part of the PDA would be basically pointless. So yes, order does matter at least somewhat.
Doesn't the PDA $M 1$ need nondeterminism to mark the bottom of the stack, since the the PDA accepts the empty string?
If the label on the arc from $q 3$ to $q 4$ was instead $\varepsilon,\varepsilon\rightarrow\varepsilon$ , the PDA would accept all strings $a i b j$ such that $i \neq j$ , which contradicts the definition of the language that the PDA is supposed to recognize as long as $i \neq 0$ .