cs402 5 Theory of Automata (CS402) Assignment Solution

Theory of Automata (CS402)

Assignment No.5

Deadline

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

Objectives

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

·         Chomsky Normal Form

·         Push Down Automata

Question No.1

Give CFG for the following languages,

1. aⁿb^m where n = m-1 and n = 1,2,3…

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

∑ = {a,b}

S à aX

X à aXb | ab | Λ

2. aⁿb²ⁿ where n = 1,2,3…

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

∑ = {a,b}

S à aSbb

S à abb 

S à Λ

Question No.2

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]

Solution:

   

      S à ABB | BB | CC | C | ABC | AB | BC | AC | A | C

     A à a

     B à b | C

     C à ab      

Question No.3

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

S ---- > YYY | ZZ | aa | bb

Y --- > a | Z

Z --- > b | Y

Solution:

S à RY | ZZ | YZ | ZY

R à YY

Y à a | Z

Z à b | Y

Question No.4

Design PDA (Push Down Automata) for the language given below,

(ba)ⁿ(a)ⁿ                  n = 1,2,3…