# Compilers Questions and Answers – Finite Automata

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

1. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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