Theory of Automata (CS402)
Assignment No.5

Deadline
Your assignment must be uploaded before or on 7th July, 2011 [Try to upload your solution well before due date to avoid any issue]

Rules for Marking

It should be clear that your assignment will not get any credit if:
• The assignment is submitted after due date
• The assignment is copied

Objectives
Objective of this assignment is to make students able to understand the following concepts,

• CNF
• PDA

Question No.1 CNF
Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)




Question No.2 PDA
Design Push Down Automata (PDA) for

(ba)n(ab)n n = 1,2,3…


Hint: 
You can push single a on reading ‘ba’ (in loop) and once you get ‘a’ again after reading ‘ba’ start popping pushed a’s against each occurrence of ‘ab’ . You will move to accept state if you have empty stack (∆ on pop) on finish of input string (reading ∆)




Assignment Uploading Instructions:
Upload single word file in word 2003 format having solutions for all questions.