vuexpert@gmail.com

Question No. 1 Marks : 1

If s=abcd is a string defined over . = {a,bc,d} then reverse of s is dcba.

True

False

Question No. 2 Marks : 10

Find the regular expression associated to the following FA. Show all steps.

[Hint: use FA to GTG and GTG to RE.]

Question No. 3 Marks : 1

. = {aa, b}, length(aaaabaabb) = 5.

True

False

Question No. 4 Marks : 1

Every NFA can be converted into FA.

True

False

Question No. 5 Marks : 1

There can be more than one start states in TG.

True

False

Question No. 6 Marks : 1

A regular language can not be infinite.

True

False

Question No. 7 Marks : 10

a) Write the recursive definition of the following language. [6]

L = Defining the language {a2n b4n }, n=1,2,3,… , of strings defined over Ó={a, b}

b) Write a regular expression of the language having strings that either start or end with

“00” and have no more zeroes. Where the alphabet is {0, 1}. [4]

Question No. 8 Marks : 1

Kleene star of {1} generates {1, 11, 111, 1111, 11111 ……}.

True

False

Question No. 9 Marks : 10

a) Define NFA-null. [4]

b) Draw DFA for the following NFA. [6]

Question No. 10 Marks : 1

If a regular language is empty then we denote it like L = . (fi).

True

False

Question No. 11 Marks : 1

Recursive method for defining language is only for regular languages.

True

False

Question No. 12 Marks : 1

aa* = a+ ?

True

False

Question No. 13 Marks : 1

The language equal means number of a’s and b’s are equal with null string.

True

False