CS402 Theory of Automata Mid Term paper spring 2011

[Vuhelper]

for solve look attachment


CS402 Theory of Automata
Mid Term Examination – Spring 2006
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

for solve look attachment