vuexpert@gmail.com

Assignment No.01
Semester: Fall 2009

CS402:Thoery of Automata

Total Marks: 20

Due Date: Oct 20, 2009

Rules for Marking

It should be clear that your assignment will not get any credit if:

o The assignment is submitted after due date.

o The submitted assignment does not open

o The assignment is copied.

Objective

The objective of this assignment is to provide on hand experience of:

o Recursive definition of the language.

o Writing Regular Expression of the language.

o Building of Finite Automata (FA)

Assignment

Question No.1

a) Give a recursive definition for the language L, of strings containing the substring 00 defined over ∑= {0,1}.

b) Give a recursive definition for the language L, of positive integers divisible by 2 or 7

Question No. 2

Describe the languages (in English) defined over ∑={x,y} represented by the following regular expressions.

Question No. 3

Construct a regular expression defining each of the following languages defined over Σ = {a,b}:

a) all strings that start with ‘a’ and have odd length, or start with ‘b’ and have even length

b) all strings that contain at least two b’s and at most one ‘a’

Question No. 4

Build an FA over Σ={a, b} that only accepts the strings starting with ‘ab’.

Deadline

Your assignment must be uploaded/submitted on or before Oct 20,2009