This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Finite Automata ”.
- A language L from a grammar G = { VN, S, P, S} is
a) Set of symbols over VN
b) Set of symbols over S
c) Set of symbols over P
d) Set of symbols over S
Answer
Answer: b
Explanation: The definition of the grammar is set of symbols over S.
2. The transitional function of a DFA is
a) Q X S?Q
b) Q X S?2Q
c) Q X S?2n
d) Q X S?Qn
Answer
Answer: a
Explanation: Q is the finite set and let be a finite set of symbols so Q X S fives no of states.
3. The transitional function of a NFA is
a) Q X S?Q
b) Q X S?2Q
c) Q X S?2n
d) Q X S?Qn
Answer
Answer: b
Explanation: Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2Q.All the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.
Then a nondeterministic finite automaton is a 5-tuple < Q , , q0 , , A > .
4) Maximum number of states of a DFA converted from a NFA with nstates is
a) n
b) n2
c) 2n
d) None of these
Answer
Answer: c
Explanation: Take the NFA with states {qo,q1}, alphabet S={a}, initial state q0, transitions d(q0,a)=q0, d(q0,a)=q1 and final state q1. It generates the same language as the DFA with the same set of states and alphabet, but transitions d(q0,a)=q1 and d(q1,a)=q1.
5. Basic limitations of finite state machine is
a) It cannot remember arbitrarily large amount of information
b) In cannot remember state transitions
c) In cannot remember grammar for a language
d) It cannot remember language generated from a grammar
Answer
Answer: b
Explanation: Because it does to store its previous state of the transition.
6. The string WWR is not recognized by any FSM because
a) A FSM cannot remember arbitrarily large amount of information
b) A FSM cannot fix the midpoint
c) A FSM cannot match W with WR
d) A FSM cannot remember first and last inputs
Answer
Answer: b
Explanation: Palindromes cannot be recognised by FSM.
7. A finite automata recognizes
a) Any Language
b) Context Sensitive Language
c) Context Free Language
d) Regular Language
Answer
Answer: d
Explanation: All regular languages are implemented by the finite automata.
8. Which is true for Dead State?
a) It cannot be reached anytime
b) There is no necessity of the state
c) If control enters no way to come out from the state
d) If control enters FA deads
Answer
Answer: c
Explanation: It is a rejecting state for if the control enters it reaches the dead end and cannot reach an accepting state.
9. Which is true for Moore Machine?
a) Output depends on present state
b) Output depends on present input
c) Output depends on present state and present input
d) Output depends on present state and past input
Answer
Answer: a
Explanation: The definition states that moore machines output is determined by the current state only.
10. Which is true for Mealy Machine?
a) Output depends on present state
b) Output depends on present input
c) Output depends on present state and present input
d) Output depends on present state and past input
Answer
Answer: c
Explanation: The definition states that its output is determined by current state and current input.
11. Which is true for in accessible state?
a) It cannot be reached anytime
b) There is no necessity of the state
c) If control enters no way to come out from the state
d) If control enters FA deads
Answer
Answer: a
Explanation: The very meaning of in accessible state is that it cannot be reached at any point of time.
12. In Mealy Machine O/P is associated with
a) Present state
b) Next state
c) Input
d) None of the mentioned
Answer
Answer: b
Explanation: The definition states that its output is determined by current state and current input.
13. In Moore Machine O/P is associated with
a) Present state
b) Next state
c) Input
d) None of the mentioned
Answer
Answer: a
Explanation: The definition states that moore machines output is determined by the current state only.
14. Which type string is accepted by the following finite automata?
a) All string
b) Null string
c) No string
d) None of the mentioned
Answer
Answer: b
Explanation: Null strings are not accepted by finite automata.
15. Myhill-Nerode Theorem is used for __________
a) Minimization of DFA
b) Maximization of NFA
c) Conversion of NFA
d) Conversion of DFA
Answer
Answer: a
Explanation: Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myhill–Nerode theorem can be generalized to trees. And used for minimization of DFA.
