cs402 mid term paper 2011 virtual university of pakistan

[Vuhelper]

for solve look attachment

Question No: 1 ( Marks: 1 ) - Please choose one
Length of a null string is supposed to be 1.
True
False
Question No: 2
There is no difference between Word and String p/5
True
False
Question No: 3
There may be two RE representing the same language.
True
False
Question No: 4
NFA – null can be considered as TG and vise versa.
True
False
Question No: 5 ( Marks: 1 ) -
. = {aA, b}, length(aAbaAaAb) = 5.
True
False
Question No: 6 ( Marks: 1 ) - Please choose one
If s=abcd is a string defined over . = {a,b,c,d} then reverse of s is dcba.
True
False
Question No: 7 ( Marks: 1 ) - Please choose one
The language equal means number of a’s and b’s are equal with no null string.
True
False
Question No: 8
Palindrome is a regular language.
True
False
Question No: 9 ( Marks: 1 ) - Please choose one
If s = babab then palindrome of s = rev(s).
.
True
.
False
Question No: 10 ( Marks: 1 ) - Please choose one
TG must have only one start state.
.
True
.
False
Question No: 11 ( Marks: 1 ) - Please choose one
If a language can be accepted by FA then it can be accepted by a TG as well.
.
True
.
False
Question No: 12
Length of output string is 1 less then that of input string is mealy machine.
.
True
.
False



Question No: 13
Formal languages are called Semantic languages. p/5
True
False


Question No: 14
Every NFA can be converted to an FA
True
False


Question No: 15
In mealy machine output character are mentioned on the transition.
True
False



Question No: 16 ( Marks: 8 )
Differentiate between the following terms:
• Mealy and Moore machine.
• NFA and FA.
Question No: 17 ( Marks: 5 )
Build an FA corresponding to NFA given below.
b
b
a
+q3
q1
q0
Question No: 18 ( Marks: 7 )
Build an NFA equivalent to FA1U FA2, where FA1, FA2 are given below.
FA1
a,b
a
b
a
b
p- + q
FA2
a
1–
3
6+
2
3
4
5
a
a
a,b
b
b
b
a b
b
a

[it_traveler]

Question No: 5 ( Marks: 1 ) -
. = {aA, b}, length(aAbaAaAb) = 5.
True
False
( You said its false) but its true.. se the length of string is 5.. toknize.. aA, b, aA, aA, b its 5