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
Post a Comment