Download PDF
Free download pdf of Automata Theory Multiple Choice Questions and Answers for papers of graduate and post-graduate examinations in Computer Science & Engineering Branch.
(11)
Which of the following is not primitive recursive but partially recursive?
[A]
Ricmann function
[B]
Bounded function
[C]
Carnot function
[D]
Ackermann function
View Answer
Comment
(12)
Regular expression a+b denotes the set
[A]
{a}
[B]
{Epsilon, a, b}
[C]
{a, b}
[D]
none of the above
View Answer
Comment
(13)
Finite State Machine can recognize
[A]
only ambiguous CFG
[B]
any grammar
[C]
any unambiguous grammar
[D]
only regular grammar
View Answer
Comment
(14)
Which of the following are not regular grammar?
[A]
Strings of 0’s, whose length is a prime number.
[B]
String of 0’s whose length is a perfect square.
[C]
Both [A] and [B].
[D]
Only [A]
View Answer
Comment
(15)
Set of regular languages over a given alphabet ∑ is not closed under
[A]
union
[B]
concatenation
[C]
Kleene star
[D]
none of the above
View Answer
Comment
(16)
The following CFG
S → aB | bA
A → b | aS | bAA
B → b | bS | aBB
generates strings of terminals that have
[A]
equal number of a’s and b’s
[B]
odd number of a’s and odd number b’s
[C]
even number of a’s and even number of b’s
[D]
odd number a’s and even number of a’s
View Answer
Comment
Answer: Option [A]
We have S → aB → aaBB → aabB → aabb
So (b) is wrong. We have
S → aB → ab
So (c) is wrong.
A careful observation of the productions will reveal a similarity. Change A to B, B to A, a to b and b to a. The new set of productions will be the same as the original set. So (d) is false and (a) is the correct answer.
(17)
Let L1 = {anbnam | m, n = 1, 2, 3 …………}
L2 = {anbmam | m, n = 1, 2, 3 ……………}
L3 = {anbnan | n = 1, 2, 3 ………}
Choose the correct statements.
[A]
L3 = L1 ∩ L2
[B]
L1 and L2 are CFL but L3 is not a CFL
[C]
L1 and L2 are not CFL but L3 is a CFL
[D]
(A) and (B)
View Answer
Comment
(18)
CSG can be recognized by a
[A]
FSM
[B]
DPDM
[C]
NDPDM
[D]
linearly bounded memory machine
View Answer
Comment
(19)
Which of the following is not primitive recursive but computable?
[A]
Bounded function
[B]
Ackermann function
[C]
Carnot function
[D]
Riemann function
View Answer
Comment
(20)
Which of the following pairs of regular expression are not equivalent?
[A]
(a+b)* and (a*+b)*
[B]
(a*+b)* and (a+b)*
[C]
(ab)*a and a(ba)*
[D]
none of the above
View Answer
Comment
Take Mock Tests