Answer-

To prove this first we construct a PDA for grammar G.
Context Free Grammar (CFG) to Push Down Automata(PDA) -
Let G=(V, Σ, P, S) is a context free grammar, we can construct a Push Down Automata(PDA) corresponding to given Context Free Grammar  (CFG) as follows.
PDA (A)=({Q},∑,δ, Γ,q0,Z,F)
Q-finite number of states
∑-input symbol
δ-transition function
Where δ is defined by the following rules
R1: δ(q, ε,A)={(q,α)|for all A→α is in P}
R2: δ(q, a,a)={(q, ε)} for each terminal a in Σ.
Γ-stack symbols
q0-initial state
Z-initial stack symbol
F-final state (F ∈ Q)

Grammar G = (V, Σ, P, S)
where
V = {S}
Σ = {a,b} 
Production rule 
P = {S  → aaSb|aSab|abSa|aSba|baSa|bSaa|ε}
S is the start variable

PDA corresponding to given CFG-
PDA(A)=({q1,q2,q3},{a,b},δ,{a,b, S,$},{q1},{S},{q3})
where
Q -{q1,q2,q3}
∑-{a,b}
Γ-Stack symbols {a,b,S ,$}
F - {q3} final state
Z-{S}- Initial stack  symbol 
qo-{q1 Initial state}
Where δ is defined by the following rules
δ(q1, ε,ε)={(q2,S$)
δ(q2, ε,S)={(q2,aaSb),(q2,aSab),(q2,abSa)
        ,(q2,aSba),(q2,baSa),(q2,bSaa),(q2,ε)}

δ(q2, a,a)={(q2, ε)}
δ(q2, b,b)={(q2, ε)}
δ(q2, ε,$)={(q3, ε)}




Comments

Popular posts from this blog

The python program allows the user to enter the Sales amount and Actual cost of a Product. Next, Python calculates the Loss Amount or profit Amount based on those two values using if-elif-else Statement

Mealy and Moore Machine

Question Bank of Theory of Automata & Formal Languages