Convert CFG into PDA

Equivalence of PDAs and CFGs

A language is context iff some PDA recognize it

If L=L(G) for some CFG G, then L=L(M) for some PDA M.

Proof idea
* Need to show that given CFG G, we can find PDA M that recognize the same language
G generates.
* Basic idea is to build PDA that simulates a leftmost derivation.
* For example, consider CFG G=(V,?,R,S)
Variables V= {S}
Terminales ?={0,1}
Rules R= S?0S0S| 1S0| 1
* Leftmost derivation of string 010110 ? L(G)
S?0S0S?010S?0101S0?010110

Creat PDA for CFG as follow:
Equivalence of PDAs and CFGs

A language is context iff some PDA recognize it

If L=L(G) for some CFG G, then L=L(M) for some PDA M.

Proof idea
* Need to show that given CFG G, we can find PDA M that recognize the same language
G generates.
* Basic idea is to build PDA that simulates a leftmost derivation.
* For example, consider CFG G=(V,?,R,S)
Variables V= {S}
Terminales ?={0,1}
Rules R= S?0S0S| 1S0| 1
* Leftmost derivation of string 010110 ? L(G)
S?0S0S?010S?0101S0?010110

Creat PDA for CFG as follow: