Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

Goals

• Context free grammars (CFGs) - definition
• Context free languages (CFLs)
• Pushdown automata (PDA)
• Converting CFGs to PDAs

CFG - Formal definition

Defn: A Context Free Grammar (CFG) G is a 4-tuple ($V,\Sigma ,R,S$)

• finite set of variables
• finite set of terminal symbols
• finite set of rules (rule form: $V\to (V\bigcup \Sigma {)}^{\ast }$ )
• start variable For $u,v\in (V\bigcup \Sigma {)}^{\ast }$ write

1. $u\to v$ if can go
2. $u\to v$ if

PDA - Formal definition

$(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$