CS402 Theory of Automata Assignment 6 Solution Fall 2012

Question No. 1:

Sà aSSb | aab
Sà SSS | a | b

Construct a Push Down Automaton (PDA) for above Context Free Grammar (CFG) without conversion into Chomsky Normal Form (CNF).


Sà      aSSb | aab

 Sà     SSS | a | b

We don’t have to convert to CNF( non terminal  à two nonterminals    OR     non terminal à   one terminal) , but we can add new nonterminals to replace  a   and    b  i.e;

Sà     ASSB | AAB

 Sà    SSS | a | b

Aà       a

 Bà      b

Question No. 2:

Convert the following Push Down Automaton (PDA) in to conversion form:

A PDA is in conversion form if it fulfills the following conditions:
There is only one ACCEPT state.
There are no REJECT states.
Every READ or HERE is followed immediately by a POP i.e. every edge leading out of any READ or HERE
state goes directly into a POP state.
No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are
any intervening PUSH states (i.e. the POP states must be separated by READs or HEREs).
All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every
edge has only one label.
Even before we get to START, a “bottom of STACK” symbol $ is placed on the STACK. If this symbol is ever
popped in the processing it must be replaced immediately. The STACK is never popped beneath this symbol.
Right before entering ACCEPT this symbol is popped out and left.
The PDA must begin with the sequence.