Theory of Automata (CS402)
Your assignment must be uploaded before or on.
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
Objective of this assignment is to make you able to understand the following concepts,
· Defining Context Free Grammars for Different Languages
· Null and Null-able Transitions and Regular Context Free Grammars
· Push Down Automata
Give CFG for the following languages,
- anbm where m = n-1 and n = 1,2,3…
Some words belonging to this language are, a , aab , aaabb , aaaabbb , ….
- anb2n where n = 1,2,3…
Some words belonging to this language are, abb , aabbbb , aaabbbbbb , ….
Consider the CFG given below and find Null and Null-able transitions (if any) also remove these transitions to give new CFG
S ---- > ABB | CC | ABC | AC
A --- > a | Є
B --- > b | C
C --- > ab | Є
[Here Є means null string, as in CFG’s we use Є for indicating null string instead of ^ sign]
Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)
S ---- > YYY | ZZ | aa | bb
Y --- > a | Z
Z --- > b | Y
Design PDA (Push Down Automata) for the language given below,
(ba)n(a)n n = 1,2,3…
Assignment Uploading Instructions:
Upload single word file in word 2003 format having solutions for all questions.