# Compilers Questions and Answers – Finite Automata – 1

«
»

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

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

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

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 >.
Note: Join free Sanfoundry classes at Telegram or Youtube

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

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

Explanation: 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

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

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. 