Tuesday, November 30, 2010
CS402- Theory of Automata Midterm Paper
MIDTERM EXAMINATION
Spring 2009
CS402- Theory of Automata (Session - 1)
Question No: 1 ( Marks: 1 ) - Please choose one
Alphabet S = {a,bc,cc} has _______ number of letters.
One
Two
Three
Four
Question No: 2 ( Marks: 1 ) - Please choose one
In which of the following language Rev(s)=s
EQUAL
INTEGER
PALINDROME
FACTORIAL
Question No: 3 ( Marks: 1 ) - Please choose one
If S = {ab, bb}, then S* will not contain
abbbab
bbba
bbbbab
ababbb
Question No: 4 ( Marks: 1 ) - Please choose one
a,b
1 –
2 +
a,b
Above given FA generates the language having strings of _________
ODD length
EVEN length
Equal number of a’s and b’s
None of these
Question No: 5 ( Marks: 1 ) - Please choose one
a+b
a+b
aa+bb
-
+
Above given GTG accepts the language in which strings
Contains double a or double b
Contains both a and double b
Depends on the alphabet
None of these
Question No: 6 ( Marks: 1 ) - Please choose one
aa+bb
aa+bb
ab+ba
3- 2 1
ab+ba
4+
If above given TG is drawn like
aa+bb
3 1
X
-
4
+
Then what will be written in place of X.
(ab+ba)(aa+bb)(ba+ab)
(ab+ba)(aa+bb)(ab+ba)
(ab+ba)(aa+bb)*(ab+ba)
(ab+ba)(aa+bb)(ab+ba)*
Question No: 7 ( Marks: 1 ) - Please choose one
FA3 expresses r1r2. Then initial state of FA3 will consist of
Initial state of FA2
Initial state of FA1
Initial states of both FA1 & FA2
Depends on FA’s
Question No: 8 ( Marks: 1 ) - Please choose one
FA3 expresses r1r2. Then there will be at least one final state of FA3 that consist
of final state of FA1 and initial state of FA2.
True
False
Depends on language
None of these
Question No: 9 ( Marks: 1 ) - Please choose one
Two machines are said to be equivalent if they print the same output string when
the different input string is run on them
True
False
Depends on language
May be or may not be
Question No: 10 ( Marks: 1 ) - Please choose one
Running the string abbabbba on this Moore
be________
b
q1/0 q2 /1
a b
a
q0/1 a
b
a
q3/1 1
b
b
a
2
q3 /0
101111010
01111010
01011110
01010101
Question No: 11 ( Marks: 1 ) - Please choose one
4 a
2
a
a
a, b a, b
· 1 – 6+
§ a,b
§ a,b
o b
o b
aaa,bbb
b
-
5
3 +
Above given TG’s are ______________.
None of these
Equivalent
Non-equivalent
TG’s are not valid
Question No: 12 ( Marks: 1 ) - Please choose one
TG can have more than one initial state.
True
False
Depends on alphabets
None of these
Question No: 13 ( Marks: 1 ) - Please choose one
a
a
+
– –
a
b
b
b
Above given FA accepts null string.
True
False
FA is not valid
None of these
Question No: 14 ( Marks: 1 ) - Please choose one
If in an NFA, is allowed to be a label of an edge then that NFA is called _________.
Will not remain NFA
NFA with
NFA with null string
Either "NFA with null string" OR "NFA with "
Question No: 15 ( Marks: 1 ) - Please choose one
One FA has n states and m letters in the alphabet. Then FA will have _____
number of transitions in the diagram.
(n)+(m)
(m)(n) OR (n)(m)
None of the given options
(m)-(n)
Question No: 16 ( Marks: 1 ) - Please choose one
(a+b)*a(a+b)*b(a+b)* is the RE of language defined over S={a,b} having at least one a
and one b
True
False
Such a language does not exist
None of the given options
Question No: 17 ( Marks: 1 )
Is the following statement trure?
A regular language can not be infinite.
Question No: 18 ( Marks: 1 )
Can you say that for a certain string there may be more than one paths in a TG?
Question No: 19 ( Marks: 2 )
If a language can be accepted by an FA then it can be accepted by a TG as well.
What are the other two statements of kleenes’s theorem?
Question No: 20 ( Marks: 3 )
Describe the method of NFA corresponding to Concatenation of FAs.
Question No: 21 ( Marks: 5 )
Draw FA corresponding to following NFA?
2
b
a
1- 4+
a
b
3
Question No: 22 ( Marks: 10 )
Let L be any language. Let us define the transpose of L to be the language of exactly
those words that are the words in L spelled backward. If w L then reverse (w) L. for
example, if L = {a, abb, bbaab, bbbaa}Then Transpose (L) = {a, bba, baabb, aabbb,
Prove that if there is an FA that accepts L, then there is a TG that accepts the transpose of
L.
Subscribe to:
Posts (Atom)