[Intro to Theoretical Comp Sci] CFG to PDA

Q) What is CFG? 

 

[ CFG - Context Free Grammar ]

: Context Free Grammar from CFL(Context-Free Language) 

Grammar G = (V,T,S,P)

V(variables) | T(Terminal symbols) | S(Start variable) | P(Productions of the form: A -> x)

 

* CFL(Context-Free Languages):

A language L is context-free if and only if

there is a context-free grammar(CFG) G that generates it, L = L(G). 

 

* Derivation Tree

 

* Normal Forms for CFG : CNF & GNF 

1) Chomsky Normal Form (CNF) 

: A context-free grammar is said to be in CNF if each production has the form -> 2 variable or only one terminal! 

=> Every context-free language L(that does not contain lambda) is generated by a grammar G in CNF.

The transformation from CFG G for L to G' in CNF by removing all illegal productions. 

 

* Steps of Removing Illegal(Undesired) Productions : GFG to CNF 

Step 1) lambda-production

if there is only lambda in production, we say the variable is nullable!

 

 

 

Step 2) Unit-Productions 

 

 

Step 3) Useless Productions

- Some derivations never terminate

- Not reachable from S(Start Variable) 

 

 

 

step 4) For every terminal symbol, add production T(a) -> a

 

 

 

 

step 5) For each production p, introduce new variables V(1), V(2),... 

 

==> Therefore,

** For any context-free grammar(doesn't generate lambda), there is an equivalent grammar in CNF.

 

 

2) Greibach Normal Form (GNF) 

: all productions have the form: only one terminal! 

==> Therefore, 

** For any context-free grammar(doesn't generate lambda), there is an equivalent grammar in GNF.

 

 

Q) What is PDA? 

 

* PDA[Pushdown Automata ]

: Pushdown Automata 

- PDA has stack 

 

 

 

 

Q) How to convert from CFG to PDA? 

 

reference 

https://www.youtube.com/watch?v=ZImtQBMSW_Y