Virtual University MCS assignments solutions

[sonia anam]

[FONT=&quot]Theory of Automata (CS402)[/FONT]

[FONT=&quot]Assignment No.5[/FONT]

[FONT=&quot]Deadline[/FONT]

Your assignment must be uploaded before or on.
[FONT=&quot]Rules for Marking[/FONT]

It should be clear that your assignment will not get any credit if:
·[FONT=&quot] [/FONT]The assignment is submitted after due date
·[FONT=&quot] [/FONT]The assignment is copied
[FONT=&quot]Objectives[/FONT]

Objective of this assignment is to make you able to understand the following concepts,
·[FONT=&quot] [/FONT]Defining Context Free Grammars for Different Languages
·[FONT=&quot] [/FONT]Null and Null-able Transitions and Regular Context Free Grammars
·[FONT=&quot] [/FONT]Chomsky Normal Form
·[FONT=&quot] [/FONT]Push Down Automata

[FONT=&quot]Question No.1[/FONT]

Give CFG for the following languages,

1. anbm where m = n-1 and n = 1,2,3…
   

Some words belonging to this language are, a , aab , aaabb , aaaabbb , ….

1. anb2n where n = 1,2,3…
   

Some words belonging to this language are, abb , aabbbb , aaabbbbbb , ….

[FONT=&quot]Question No.2[/FONT]

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]

[FONT=&quot]Question No.3[/FONT]

Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)

S ---- > YYY | ZZ | aa | bb
Y --- > a | Z
Z --- > b | Y

[FONT=&quot]Question No.4[/FONT]

Design PDA (Push Down Automata) for the language given below,
(ba)n(a)n n = 1,2,3…