Automata Theory Objective Questions Answers

Questions
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

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

Answer: Option [B]
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

Answer: Option [D]
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)

Answer: Option [D]
5 Any given Transition graph has an equivalent
A DFSM
B NDFSM
C regular expression
D all of the above

Answer: Option [D]
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

Answer: Option [A]
7 Context-free grammar is not closed under
A complementation
B union
C concatenation
D kleene star

Answer: Option [A]
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

Answer: Option [A]
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

Answer: Option [C]
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

Answer: Option [D]
junior administrative assistant jaa test series