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.
 |
Upload your Solution |