if a grammar g is context-free, we can build an equivalent nondeterministic pda which accepts the language that is produced by the context-free grammar g. a parser can be built for the grammar g.

also, if p is a pushdown automaton, an equivalent context-free grammar g can be constructed where

l(g) = l(p)

in the next two topics, we will discuss how to convert from pda to cfg and vice versa.

algorithm to find pda corresponding to a given cfg

input − a cfg, g = (v, t, p, s)

output − equivalent pda, p = (q, ∑, s, δ, q₀, i, f)

step 1 − convert the productions of the cfg into gnf.

step 2 − the pda will have only one state {q}.

step 3 − the start symbol of cfg will be the start symbol in the pda.

step 4 − all non-terminals of the cfg will be the stack symbols of the pda and all the terminals of the cfg will be the input symbols of the pda.

step 5 − for each production in the form a → ax where a is terminal and a, x are combination of terminal and non-terminals, make a transition δ (q, a, a).

problem

construct a pda from the following cfg.

g = ({s, x}, {a, b}, p, s)

where the productions are −

s → xs | ε , a → axb | ab | ab

solution

let the equivalent pda,

p = ({q}, {a, b}, {a, b, x, s}, δ, q, s)

where δ −

δ(q, ε , s) = {(q, xs), (q, ε )}

δ(q, ε , x) = {(q, axb), (q, xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

algorithm to find cfg corresponding to a given pda

input − a cfg, g = (v, t, p, s)

output − equivalent pda, p = (q, ∑, s, δ, q₀, i, f) such that the non- terminals of the grammar g will be {x_wx | w,x ∈ q} and the start state will be a_q0,f.

step 1 − for every w, x, y, z ∈ q, m ∈ s and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule x_wx → a x_yzb in grammar g.

step 2 − for every w, x, y, z ∈ q, add the production rule x_wx → x_wyx_yx in grammar g.

step 3 − for w ∈ q, add the production rule x_ww → ε in grammar g.