next up previous
Next: How to implement a Up: Pushdown automata Previous: Deterministic PDAs

Context free grammars and push-down-automata

Theorem 6.1   For a language $ L\subseteq
\Sigma^*$ the following is equivalent:
  1. $ L$ is given by a CFG $ G$, $ L=L(G)$.

  2. $ L$ is the language of a PDA $ P$, $ L=L(P)$.

To summarize: Context free languages (CFLs) can be described by a context free grammar (CFG) and can be processed by a pushdown automaton.

We will he only show how to construct a PDA from a grammar - the other direction is shown in the text book (6.3.2, pp. 241).

Given a CFG $ G=(V,\Sigma,S,P)$, we define a PDA

$\displaystyle P(G) = ( \{q_0\},\Sigma,V\cup\Sigma,\delta,q_0,S) $

where $ \delta$ is defined as follows:

$\displaystyle  \delta(q_0,\epsilon,A)$ $\displaystyle = \{ (q_0,\alpha) \mid A\to\alpha \in P \}$    
$\displaystyle  $    
  $\displaystyle \textrm{for all $A\in V$.}$    
$\displaystyle  \delta(q_0,a,a) = \{ (q_0,\epsilon) \}$    
$\displaystyle  $    
  $\displaystyle \textrm{for all $a\in\Sigma$.}$    

We haven't given a set of final states because we use acceptance by empty stack. Yes, we use only one state!

Take as an example $ G=(\{E,T,F\},\{(,),a,+,*\},E,P)$ where

$\displaystyle P = \{$ $\displaystyle E \to T \mid E + T$    
$\displaystyle  $ $\displaystyle T \to F \mid T * F$    
$\displaystyle  $ $\displaystyle F \to a \mid ( E )$    

we define

$\displaystyle P(G) = ( \{q_0\},\{(,),a,+,*\},\{E,T,F,(,),a,+,*\},\delta,q_0,E) $

with

$\displaystyle  \delta(q_0,\epsilon,E) = \{ (q_0,T),(q_0,E+T) \}$    
$\displaystyle  \delta(q_0,\epsilon,T) = \{ (q_0,F),(q_0,T*F) \}$    
$\displaystyle  \delta(q_0,\epsilon,F) = \{ (q_0,a),(q_0,\texttt{(}E\texttt{)}) \}$    
$\displaystyle  \delta(q_0,\texttt{(},\texttt{(}) = \{(q_0,\epsilon)\}$    
$\displaystyle  \delta(q_0,\texttt{)},\texttt{)}) = \{(q_0,\epsilon)\}$    
$\displaystyle  \delta(q_0,\texttt{a},\texttt{a}) = \{(q_0,\epsilon)\}$    
$\displaystyle  \delta(q_0,\texttt{+},\texttt{+}) = \{(q_0,\epsilon)\}$    
$\displaystyle  \delta(q_0,\texttt{*},\texttt{*}) = \{(q_0,\epsilon)\}$    

How does the $ P(G)$ accept $ \texttt{a + (a*a)}$?

$\displaystyle  (q_0,\texttt{a + (a*a)},E)$ $\displaystyle \vdash (q_0,\texttt{a + (a*a)},E\texttt{+}T)$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{a + (a*a)},T\texttt{+}T\texttt{)}$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{a + (a*a)},F\texttt{+}T\texttt{)}$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{a + (a*a)},a\texttt{+}T\texttt{)}$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{+ (a*a)},\texttt{+}T\texttt{)}$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ (a*a)},T\texttt{)}$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ (a*a)},F)$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ (a*a)},\texttt{(}E\texttt{)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a*a)},E\texttt{)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a*a)},T\texttt{)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a*a)},T*F))$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a*a)},F*F))$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a*a)},a*F))$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ *a)},\texttt{*}F\texttt{)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a)},F\texttt{)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ a)},\texttt{a)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\texttt{ )},\texttt{)})$    
$\displaystyle  $ $\displaystyle \vdash (q_0,\epsilon,\epsilon)$    

Hence $ \texttt{a + (a*a)}\in L(P(G))$.

This example hopefully already illustrates the general idea:

$\displaystyle  w \in L(G)$    
$\displaystyle  \iff$    
$\displaystyle  S \Rightarrow \dots \Rightarrow w$    
$\displaystyle  \iff$    
$\displaystyle (q_0,w,S) \vdash \dots \vdash (q_0,\epsilon,\epsilon)$    
$\displaystyle \iff w \in L(P(G))$    

The automaton we have constructed is very non-deterministic: Whenever we have a choice between different rules the automaton may silently choose one of the alternative.


next up previous
Next: How to implement a Up: Pushdown automata Previous: Deterministic PDAs
Thorsten Altenkirch 2001-05-08