10-04-2012, 11:37 AM
Deterministic Pushdown Automata
lec14.pdf (Size: 85.61 KB / Downloads: 61)
DPDA Acceptance Modes
Are languages accepted by empty stack the same as the languages
accepted by final state for deterministic PDAs?
Definition: A language L has the prefix property if there are no two
different strings x, y such that x is a prefix of y.
Proposition: If P is a DPDA and L = N(P) then L has the prefix
property.
Proof: On any input x the DPDA has a unique run. So if x ∈ N(P) then
hq0, x,Z0i ⊢∗ hp, ǫ, ǫi. Therefore P does not accept an input of the form
xu because P necessarily empties its stack after reading x and so is stuck.
Theorem: L = N(P) for some DPDA P iff L has the prefix property and
L is L(P′) for some DPDA P′.
DPDAs and Context Free Languages
Theorem: There are context-free languages that are not accepted by any
DPDA. One such language is {wwR | w ∈ (0 + 1)∗}.
Proof of the theorem is difficult. But the intuition is that
nondeterminism is essential to figure out when wR begins.
Towards Normal Forms for Grammars
Every non-empty context-free language without ǫ, can be generated by a
CFG whose productions are of a “special” form
Chomsky Normal Form Productions are of the form A → BC or
A → a
Greibach Normal Form Productions are of the form A → aα, where
α ∈ V ∗
Use of normal forms is in simplifying the proofs for context free
languages.
Before presenting the algorithm to convert into normal form we will look
at a series of simplifications that can be applied to any grammar.
Generating and Reachable Symbols
Computing the set of generating symbols
• If A → x, where x ∈ T∗, is a production then A is generating
• If A → γ is a production and all variables in γ are generating, then
A is generating.
• Restrict the production rules to those involving only generating
symbols
Computing the set of reachable symbols
• S is reachable
• If A is reachable and A → αBβ is a production, then B is reachable
• Restrict the production rules to those involving only those that are
reachable.
Simplifying Grammars
Given a grammar G, such that L(G) 6= ∅, we can find a grammar G′
such that L(G′) = L(G) \ {ǫ} and G′ has no ǫ-productions, unit
productions, or useless symbols.
Proof: Apply the following 3 steps in order:
1. Eliminate ǫ-productions
2. Eliminate unit productions
3. Eliminate useless symbols.
Note: Applying the steps in a different order may result in a grammar
not having all the properties desired.