Compilers Multiple Choice Questions & Answers (MCQs) on “Finite Automata”.
1. A language L from a grammar G = { VN, Σ, P, S} is?
a) Set of symbols over VN
b) Set of symbols over Σ
c) Set of symbols over P
d) Set of symbols over S
Answer: b
Clarification: The definition of the grammar is set of symbols over Σ.
2. What is the transitional function of a DFA?
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn
Answer: a
Clarification: Q is the finite set and let be a finite set of symbols so Q X Σ fives no of states.
3. What is the transitional function of an NFA?
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn
Answer: b
Clarification: 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 an NFA with nstates is?
a) n
b) n2
c) 2n
d) None of the mentioned
Answer: c
Clarification: Take the NFA with states {qo,q1}, alphabet Σ={a}, initial state q0, transitions δ(q0,a)=q0, δ(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 δ(q0,a)=q1 and δ(q1,a)=q1.
5. What are the basic limitations of finite state machine?
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: b
Clarification: Because it does to store its previous state of the transition.
6. The string WWR is not recognized by any FSM because _____________
a) An FSM cannot remember arbitrarily large amount of information
b) An FSM cannot fix the midpoint
c) An FSM cannot match W with WR
d) An FSM cannot remember first and last inputs
Answer: b
Clarification: Palindromes cannot be recognized by FSM.
7. A finite automata recognizes ____________
a) Any Language
b) Context Sensitive Language
c) Context Free Language
d) Regular Language
Answer: d
Clarification: All regular languages are implemented by finite automata.