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.
(1)
The recognizing capability of NDFSM and DFSM
[A]
must be the same
[B]
may be different
[C]
must be different
[D]
none of the above
View Answer
Comment
Answer: Option [A]
The recognizing capability of NDFSM and DFSM both are same. Because it is possible to generate equivalent DFSM from NDFSM and Vice versa.
(2)
Pumping lemma is generally used for proving
[A]
a given grammar is regular
[B]
a given language is not regular
[C]
whether two given regular expressions are equivalent
[D]
none of the above
View Answer
Comment
(3)
Why Palindromes can't be recognized by any FSM ?
[A]
an FSM can't deterministically fix the mid-point
[B]
an FSM can't remember arbitrarily large amount of information
[C]
even if the mid-point is known, an FSM can’t find whether the second half of the string matches the first half
[D]
all of the above
View Answer
Comment
(4)
L = {anbnan | n = 1, 2, 3 ……..} is an example of a language that is
[A]
not context free but whose complement is CF
[B]
not context free
[C]
only [A]
[D]
both (B) and (C)
View Answer
Comment
(5)
Any given Transition graph has an equivalent
[A]
DFSM
[B]
NDFSM
[C]
regular expression
[D]
all of the above
View Answer
Comment
(6)
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
[A]
Finite state automata
[B]
Deterministic pushdown automata
[C]
Non-Deterministic pushdown automata
[D]
Turing machine
View Answer
Comment
(7)
Context-free grammar is not closed under
[A]
complementation
[B]
union
[C]
concatenation
[D]
kleene star
View Answer
Comment
(8)
A PDM behaves like an FSM when the number of auxiliary memory it has is
[A]
0
[B]
1
[C]
2
[D]
none of the above
View Answer
Comment
(9)
A PDM behaves like a TM when number of auxiliary memory it has is
[A]
0
[B]
1
[C]
2 or more
[D]
none of the above
View Answer
Comment
(10)
Which of the following statements is/are true?
[A]
DFSM and NDFSM both are equivalent.
[B]
An FSM with 2 stacks is as powerful as a TM.
[C]
A DFSM with 2 stacks and an NDFSM with 2 stacks have the same power.
[D]
All of the above
View Answer
Comment
Please share this page