Seong-lae ChoPDAs
Use stack data structure (can remove, get and change top only)
Q, Sigma, Gamma, F are finite sets
- Q is set of states
- Σ is set of input symbols(alphabet)
- Γ is set of stack symbols(alphabet)
- δ is transition function
math: Q×(Σ∪\{λ\})×Γ → 2^{Q×Γ^∗}has a triple argument (q,a,X) where q is current state, a is input symbol in Σ∪{λ}, X is stack symbol in Γ output ismath: 2^{Q×Γ^∗}which are finite set of pairs (p,γ), where p is the next state and γ is the string of stack symbols that replaces X (X / γ)
- q0 is start state
- Z0 is start symbol for the stack (marker on the bottom stack)
math: F \subseteq Qis set of final(accepting) states
- infinite stack memory
stack change ≠ stack up by preexisted terminal before / Nothing : same between left and right Pop : there is symbol on left and λ on right
Instantaneous Descriptions (IDs)
involves both the state and the contents of the stack
(q,w,γ) q is state, w is the remaining input and γ is the stack contents
math:∀w ∈ Σ^* and β ∈ Γ^* : (p,α) ∈ δ(q,a,X) ⇒ (q,aw,Xβ) \vdash (p,w,αβ)Claim1 : math: (q,x,α) \vdash^∗ (p,y,β) ⇒ (q,xw,αγ) \vdash^∗ (p,yw,βγ)
Proof : Induction on the length of the sequence to the left
reverse is not true - since we could use γ
Claim2 : math: (q,xw,α) \vdash^∗ (p,yw,β) ⇒ (q,x,α)\vdash^∗ (p,y,β)
Proof : Induction on the length of the sequence to the left either
Usually ID is used for Proof
Acceptance
- Acceptance by final state if there is no more input symbol state is final
math: {w | (q_0,w,Z_0) \vdash^∗ (q,λ,α)} where q ∈ F
- Acceptance by empty stack if bottom Z0 if popped
math: N(P) = \{w \,\, |\,\, (q_0,w,Z_0) \vdash^∗ (q,λ,λ)\}- If acceptance selected, another acceptance is ignored
- If last production to final state is λ, Z0/Z0 → λ, Z0 / λ will make it acceptance by empty stack
Two methods are equivalent - iff L has PDA accepts it by another
Equivalence
Between CFG, PDA by empty stack, PDA by final state 1~5 method
diagram. FESTFT
- at left there is
math: p_0
diagram. FFSTES
1. From Empty Stack to Final State
Claim : If L = N(
math: P_N) for some, there is a PDA math: P_F Proof
math: Let \,\, P_N = (Q∪\{p_0,p_f\},Σ,Γ∪\{X_0\},δ_F,p_0,X_0, \{p_f\})where δ_F is defined by
- make new start state
math: p_0which go tomath: \lambda , X_0 / Z_0X_0
- other production is same with original
- Every element in Q has production to new p
math: \lambda,\,\, X_0/ \lambda
We need to show
math: N(P_N) = L(P_F)Super set part
Subset part
If L = N(
math: P_N) for some, there is a PDA math: P_F 2. From Final State to Empty Stack
Claim : If L = N(
math: P_F) for some, there is a PDA math: P_N Proof
math: Let \,\, P_N = (Q∪\{p_0,p\},Σ,Γ∪\{X_0\},δ_N,p_0,X_0, \{p\})where δ_N is defined by
- make new start state
math: p_0which go tomath: \lambda , X_0 / Z_0X_0
- other production is same with original
- Every element in F has production to new p
math: \lambda,\,\, any/ \lambdawhich has self production from p to p either
We need to show
math: N(P_N) = L(P_F)Super set part
Subset part
3. From CFGs to PDAs with empy stack
Easily understanding - from stack variable(right part) to string terminal(left part) by left-sentential form
we construct a PDA that simulates
math: \vdash^∗_{lm}(the leftmost derivation)Let xAαmath: \vdash^∗_{lm} xβα iff PDA first having consumed x and having Aα on the stack, and then on λ it pops A and pushes β (one production)
left-sentential forms : xAα - so A is leftmost variable and x can be λ
So how to make it?
G(V, T, Q, S), P = ({q}, T, V
math: \cup T, math: \delta, q, S) - start symbol of stack is S- for each variable A, δ(q,λ,A) = {(q,β) | A → β is a production of G}
- for each terminal a, δ(q,a,a) = {(q,λ)}
Claim : N(
math: P_G) = L(G)This mean all PDA can be in one state
Proof
At G
math: S = γ_1 ⇒_{lm} γ_2 ⇒_{lm} ···⇒_{lm} γ_n = w (since top of stack is left of string)At P, let
math: γ_i = x_iα_i- x is left of Varible - only nonterminal since it is left most
- y if right of variable which are now and only terminal
- alpha is gonna be y part right of variable (can have variable)
Super set part
Subset part
Imagine machine work - machine start from stack symbol → make variables in stack → if terminal is maded then pop it and fill Translucent String if want Right most → move image of stack from right of string to left of string
4. GNF to PDA with Final stage
Alternative Method
P = ({q0,q1,qf},T,V ∪{Z0},δ,q0,Z0,{qf})
- A → aBC: We pop A from the stack and push BC while reading a from the input
- A → a: We pop A from the stack and read a from the input
Is combination of 3 → 1 + At variable production, use first terminal instead of using lambda
5. PDAs to CFGs (very difficult)
image : while read string, from stack like pop corn jumping will stroe in net popping. and push symbol by transform terminal symbol
net popping of X (X has been replaced by λ)
- [pi-1Ypi](to presend change (add and removed all)) representing the transition with net effect of popping Y
- \delta(q, \sigma, X) = {(p, Y)} can make [qXp] → \sigma[qY1o]...[oYr] (r is all state can go by Y) - and if Y is lambda than delta only
- by rewriting start state and end state is same
How can construct
let P = (Q,Σ,Γ,δ,q0,Z0)
math: Let \,\,\,\, G = (V, \Sigma, S, R)math: V = \{[pXq] \, | \, p, q \in Q \, and \, X \in \Gamma\} \, \cup \{S\}R = {S → [q0Z0p] | p ∈ Q}∪ {[qXrk] → a[rY1r1]···[rk−1Ykrk] | a ∈ Σ∪{λ},r1,...,rk ∈ Q,(r,Y1Y2···Yk) ∈ δ(q,a,X)}.
- net effect is symbol
- tail of net effect is other catenation of net effect
- a is input string
- S → production is arrow to start state
- R maded by each rule
then N(P) = L
from \delta(q, \sigma)
Claim: Let G be constructed from a PDA P. Then, L(G) = N(P).
Proof
DPDAs
P is DPDA if and if only
- delta(q, a, X) is always empty or a singleton (because function result is set)
- if delta(q, a ,X) is nonempty, then delta(q, lambda, X) must be empty
Then we can define DCFL L = L(P), but it is undecidable whether or not a given CFL is DCFL
• For any given input symbol and any stack top, at most one move can be made
• When a λ-move is possible for some configuration, no input consuming alternative is available
• The difference between DFA and DPDA: Since the top of the stack plays a role in determining the next move, the presence of λ-transitions does not necessarily imply nondeterminism
Property of DPDA
- accept a subfamily of CFLS
- L is N(P) for some DPDA P if and only if L has the prefix property and L is L(P') for some DPDA P'
- if L = N(P) for some DPDA P, then L has an unambiguous CFG
- It is undecidable whether or not a given context-free language is a DCFL.
Claim: If L is regular, then L = L(P) for some DPDA P by final state.
Proof: Since L is regular, there is a DFA A = (Q,Σ,δA,q0,F) such that L(A) = L.
We construct a DPDA P = (Q,Σ,{Z0},δP,q0,Z0,F), where δP(q,a,Z0) = {(δA(q,a),Z0)}, for all p,q ∈ Q and a ∈ Σ. We need to show that (q0,w,Z0) `∗ (p,λ,Z0) ⇐⇒ δA(q0,w) = p.
dcfl accepted by final state = Rl
dcfl accepted by final state - only accept CFLs with prefix property
- prefix property if there are no two distinct strings in L such that one is a prefix of the other.
- Example: {0}∗, which is regular, does not have the prefix property.
The difference between DFA and DPDA: since the top of the stack plays a role in determining the next move, the presence of λ-transitions does not necessarily imply nondeterminism
Claim: If L = N(P) for some DPDA P, then L has an unambiguous CFG.
Proof: Let $ be a symbol that is not in the alphabet of L and let L0 = L$.
that L0 has the prefix property. By the previous claim, we have L0 = N(P0) for some DPDA P0. Then, we know that N(P0) can be generated by an unambiguous CFG G0. Modify G0 into G, such that L(G) = L by adding the production $ → λ. Since G0 has unique leftmost derivations, G0 also has unique ∗ =⇒ lm since the only new thing we’re doing is adding derivations w$ =⇒ lm w to the end.
Problem (Design PDA) solve Tip
- use different stack symbol counter between pop and push of same input symbol
- check stack before string
- replace net effect to variable ← stack input as variable and count stack output by unit of input variable