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

Solution:

a)

Recursive definition of language L, of strings containing the substring 00 defined over ∑= {0,1}.

Step 1

00 is in L

Step 2

x00x is also in L where x belong to {0,1}*

Step 3

No strings except those constructed in above, are allowed to be in L.

b)

Give the recursive definition of language L,of positive integers divisible by 2 or 7

Step 1

2 or 7 is in L

Step 2

2n or 7n are also in L where n = {1, 2, 3 …}

Step 3

No strings except those constructed in above, are allowed to be in L.

Question No. 2

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

Solution:

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’

Solution:

a) a((a+b)(a+b))* + b((a+b)((a+b)(a+b))*)

b) bb⁺ + abb⁺ + b⁺ab⁺ + bb⁺a

Question No. 4

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

Solution: