Finite Automata - Compilers Questions and Answers

This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Finite Automata – 1”.

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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: a
Explanation: 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
View 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 an NFA with nstates is?
a) n
b) n²
c) 2n
d) None of the mentioned
View Answer

Answer: c
Explanation: 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
View Answer

Answer: b
Explanation: Because it does to store its previous state of the transition.

Note: Join free Sanfoundry classes at Telegram or Youtube

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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: d
Explanation: All regular languages are implemented by finite automata.

Sanfoundry Global Education & Learning Series – Compilers.

To practice all areas of Compilers, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

« Prev - Compilers Questions and Answers – Relations – 2

» Next - Compilers Questions and Answers – Finite Automata – 2

Related Posts: