Assignment No.01 Semester: Fall 2009 CS402:Thoery of Automata

Please join for help vuhelp.com/forum

	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. Regular Expression Regular Language (x + y)* (x+y) (x + y)* (y)* x (y)* x (y)* (x + y)* x (x + y)* x (x + y)* (y)* x (y)* x (y)* + (x)* y (x)* y (x)*) ((y)* x (y)* x (y)* )* 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