Push Down Automaton


## PDAs
$$P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$$
<details><summary>

**Use stack data structure (can remove, get and change top only)**</summary>

Q, Sigma, Gamma, F are finite sets
1. Q is set of states
2. Σ is set of input symbols(alphabet)
3. Γ is set of stack symbols(alphabet)
4. δ 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 is `math: 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 / γ)  
5. q0 is start state
6. Z0 is start symbol for the stack (marker on the bottom stack)
7. `math: F \subseteq Q` is set of final(accepting) states
- infinite stack memory
</details>


> 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)
<details><summary>

**involves both the state and the contents of the stack**</summary>

(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,αβ)`
</details>

<details><summary>

**Claim1 : **`math: (q,x,α) \vdash^∗ (p,y,β) ⇒ (q,xw,αγ) \vdash^∗ (p,yw,βγ)`</summary>

**Proof** : Induction on the length of the sequence to the left
</details>

reverse is not true - since we could use γ


<details><summary>

**Claim2** : `math: (q,xw,α) \vdash^∗ (p,yw,β) ⇒ (q,x,α)\vdash^∗ (p,y,β)`</summary>

**Proof** : Induction on the length of the sequence to the left either
</details>

> Usually ID is used for Proof




## Acceptance
> - Acceptance by final stateif there is no more input symbol state is final
> `math: {w | (q_0,w,Z_0) \vdash^∗ (q,λ,α)}` where q ∈ F

> - Acceptance by empty stackif 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
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F580bcdf1-bee6-4845-b151-4b739a99cea7%2FUntitled.png?table=block&id=d79a0b9b-573b-4e8d-be73-d44195172b6a&cache=v2)
> diagram. FESTFT
> - at left there is `math: p_0`

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F0a8f4952-eaab-44c8-a568-e60605e00c78%2FUntitled.png?table=block&id=17a14a25-1d58-45b3-b9b3-4bbe68eeb53f&cache=v2)
> 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 `
<details><summary>

**Proof**</summary>

`math: Let \,\, P_N = (Q∪\{p_0,p_f\},Σ,Γ∪\{X_0\},δ_F,p_0,X_0, \{p_f\})`
where δ_F is deﬁned by
1. make new start state `math: p_0 `which go to `math: \lambda , X_0 / Z_0X_0`
2. other production is same with original
3. 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**
> Let w ∈ N(`math: P_N`). Then, (`math: q_0,w,Z_0`) `math: \vdash^*_{P_N}`(q,λ,λ), for some q in Q
> This implies that `math: (q_0,w,Z_0X_0) \vdash^∗_{P_N} (q,λ,αX_0)`
> And `math: \delta_N \in \delta_F`, `math: (q_0,w,Z_0X_0) \vdash^∗_{P_F} (q,λ,X_0)` so `math: (p_0,w,X_0) \vdash^*_{P_F} (p_f,λ,λ)`
**Subset part**
> trivial, Since it has all of productions and states
</details>

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 `
<details><summary>

**Proof**</summary>

`math: Let \,\, P_N = (Q∪\{p_0,p\},Σ,Γ∪\{X_0\},δ_N,p_0,X_0, \{p\})`
where δ_N is deﬁned by
1. make new start state `math: p_0 `which go to `math: \lambda , X_0 / Z_0X_0`
2. other production is same with original
3. Every element in F has production to new p `math: \lambda,\,\, any/ \lambda` which has self production from p to p either
We need to show `math: N(P_N) = L(P_F)`
**Super set part**
> Let w ∈ N(`math: P_F`). Then, (`math: q_0,w,Z_0`) `math: \vdash^*_{P_F}`(q,λ,α), for some q ∈ F and α ∈ Γ*
> This implies that `math: (q_0,w,Z_0X_0) \vdash^∗_{P_F} (q,λ,αX_0)`
> And `math: \delta_F \in \delta_N`, `math: (q_0,w,Z_0X_0) \vdash^∗_{P_N} (q,λ,αX_0)` so `math: (p_0,w,X_0) \vdash^*_{P_N} (p_f,λ,λ)`
**Subset part**
> trivial, Since it has all of productions and states
</details>




### 3. From CFGs to PDAs with empy stack
<details><summary>

**Easily understanding - from stack variable(right part) to string terminal(left part) by left-sentential form**</summary>

we construct a PDA that simulates `math: \vdash^∗_{lm}`(the leftmost derivation)
<details><summary>

Let xAα`math: \vdash^∗_{lm} `​xβα  **iff **PDA ﬁrst having consumed x and having Aα on the stack, and then on λ it pops A and pushes β (one production)</summary>

- shoud save y, same stage means rewriting - one stage
→  with string w = xy then (q,y,Aα) `math: \vdash^∗_{lm}`(q,y,βα) 
</details>

</details>

> 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
1. for each variable A, δ(q,λ,A) = {(q,β) | A → β is a production of G}
2. for each terminal a, δ(q,a,a) = {(q,λ)}
**Claim : **N(`math: P_G`) = L(G)
### This mean all PDA can be in one state
<details><summary>

**Proof**</summary>

A**t G**,`math: S = γ_1 ⇒_{lm} γ_2 ⇒_{lm} ···⇒_{lm} γ_n = w`  (since top of stack is left of string)
A**t 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**
> **if **`**math: S⇒^*_{lm} γ_i **`**then **`**math: (q,w,S) \vdash^∗ (q,y_i,α_i)**`** **
> **Basis**
> For i = 1,γ1 = S. Thus, x1 = λ and y1 = w. Clearly (q,w,S) `∗ (q,w,S).
> **Induction**
> IH is (q,w,S) `∗ (q,yi,αi). We have to show that
> (q,yi,αi) ` (q,yi+1,αi+1).
> Since αi begins with a variable A, the step of the derivation γi ⇒ γi+1 involves replacing A by one of its production bodies, say β. R1 lets us replace A at the top of the stack by β and R2 allows us to match any terminals on top of the stack with the next input symbols. As a result, we reach the next left-sentential form γi+1 = (q,yi+1,αi+1). Finally, since γn = w, we have αn = λ and yn = λ, and thus (q,w,S) `∗ (q,λ,λ). Namely, w ∈ N(PG).


**Subset part**
> **If (q,x,A) `∗ (q,λ,λ), then A ∗ =⇒x.**
> **Basis**
> Length 1. This implies that A → λ is in G and, thus, we have (q,λ) ∈ δ(q,λ,A). Therefore, A ∗ =⇒λ. 
> **Induction **on the length of `∗
> Length n ≥ 1 and IH holds for lengths < n. Since A is a variable, we should have (q,x,A) `(q,x,Y1Y2···Yk)`···` (q,λ,λ), where A → Y1Y2···Yk is in G.
</details>

> **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
<details><summary>

**Alternative Method**</summary>

P = ({q0,q1,qf},T,V ∪{Z0},δ,q0,Z0,{qf})
> δ(q0,λ,Z0) = {(q1,SZ0)},
> (q1,u) ∈ δ(q1,a,A) whenever A → au,
> δ (q1,λ,Z0) = {(qf,Z0)}.
- 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
</details>

Is combination of 3 → 1 + At variable production, use first terminal instead of using lambda



### 5. PDAs to CFGs (very difficult)
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F0e4fa2b0-d08b-49d9-97a7-9cf8511d397e%2FAnnotation_2019-05-21_122127.jpg?table=block&id=0be9d7db-21a5-4bf2-88d5-79042ee5997e&cache=v2)

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F3ba691fa-39f1-4871-8309-e7ee909b01b4%2FAnnotation_2019-05-21_122127.jpg?table=block&id=6bc0de97-2c9a-4233-bcd3-5a484cdbaf64&cache=v2)

> 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\}`
> <details><summary>
> 
> R = {S → [q0Z0p] | p ∈ Q}∪ {[qXrk] → a[rY1r1]···[rk−1Ykrk] | a ∈ Σ∪{λ},r1,...,rk ∈ Q,(r,Y1Y2···Yk) ∈ δ(q,a,X)}.</summary>

> - 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
> </details>
> 
> then N(P) = L
> from \delta(q, \sigma)




**Claim**: Let G be constructed from a PDA P. Then, L(G) = N(P).
<details><summary>

Proof</summary>

</details>




# DPDAs
P is DPDA if and if only
3. delta(q, a, X) is always empty or a singleton** (because function result is set)**
4. if delta(q, a ,X) is nonempty, then delta(q, lambda, X) must be empty
<details><summary>

Then we can define DCFL L = L(P), but it is undecidable whether or not a given CFL is DCFL</summary>

• For any given input symbol and any stack top, at most one move can be made 
• When a λ-move is possible for some conﬁguration, no input consuming alternative is available 
• The diﬀerence 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
</details>



<details><summary>

**Property of DPDA**</summary>

1. accept a subfamily of CFLS
2. 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'
3. if L = N(P) for some DPDA P, then L has an unambiguous CFG
4. It is undecidable whether or not a given context-free language is a DCFL.
</details>

Claim: If L is regular, then L = L(P) for some DPDA P by ﬁnal state.
<details><summary>

Proof: Since L is regular, there is a DFA A = (Q,Σ,δA,q0,F) such that L(A) = L. </summary>

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.
</details>

dcfl accepted by final state  = Rl
dcfl accepted by final state - only accept CFLs with prefix property
- preﬁx property if there are no two distinct strings in L such that one is a preﬁx of the other.
- Example: {0}∗, which is regular, does not have the preﬁx 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.
<details><summary>

Proof: Let $ be a symbol that is not in the alphabet of L and let L0 = L$.</summary>

that L0 has the preﬁx 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.
</details>



## 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




