Non-deterministic Finite Automata (NFA) MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

Which of the following is true for an NFA?

A) It has multiple start states.
B) It has multiple transitions for a single input symbol from a given state.
C) It cannot have epsilon transitions.
D) It has a unique next state for each input symbol.
Answer: B

An NFA is called non-deterministic because:

A) It can have multiple transitions for the same input symbol from a state.
B) It can deterministically decide whether to accept or reject a string.
C) It does not accept epsilon transitions.
D) It has a fixed number of states.
Answer: A

Which of the following is not a part of the 5-tuple representation of an NFA?

A) A finite set of states.
B) A finite set of input symbols.
C) A finite set of output symbols.
D) A transition function.
Answer: C

In an NFA, the transition function:

A) Maps a state and an input symbol to multiple states.
B) Maps a state and an input symbol to a single state.
C) Maps a state and an input symbol to an output symbol.
D) Maps a state and an output symbol to an input symbol.
Answer: A

The language accepted by an NFA is:

A) Context-free.
B) Context-sensitive.
C) Regular.
D) Recursively enumerable.
Answer: C

Which of the following is true about the states of an NFA?

A) Every state must be an accept state.
B) Every state must be a start state.
C) There can be exactly one start state.
D) There can be multiple start states.
Answer: C

In an NFA, what happens if there is no valid transition for a given input symbol from a particular state?

A) The NFA moves to a random state.
B) The NFA halts and rejects the input.
C) The NFA accepts the input.
D) The NFA nondeterministically chooses an epsilon transition.
Answer: B

Which of the following is not true for an NFA?

A) It can recognize regular languages.
B) It can have epsilon transitions.
C) It has a single start state.
D) It has a unique transition for each input symbol from a state.
Answer: D

An NFA can be used to determine if a string:

A) Is in a context-free language.
B) Is in a regular language.
C) Is in a context-sensitive language.
D) Is in a recursively enumerable language.
Answer: B

Which of the following operations can be performed on regular languages recognized by NFAs?

A) Union
B) Intersection
C) Complement
D) All of the above
Answer: D

The set of all strings over the alphabet {0, 1} that contain an even number of 1s can be recognized by:

A) An NFA
B) A PDA
C) A Turing machine
D) None of the above
Answer: A

The NFA for the language {w | w contains at least one ‘a’} over the alphabet {a, b} will have:

A) 2 states
B) 3 states
C) 1 state
D) 4 states
Answer: A

For an NFA, which of the following statements is false?

A) It has a finite number of states.
B) It can be represented using a transition table.
C) It can accept all types of languages.
D) It can have multiple transitions for a single input symbol.
Answer: C

The complement of a language recognized by an NFA can be obtained by:

A) Reversing the transitions
B) Making the start state an accept state
C) Swapping the accept and non-accept states
D) Converting the NFA to a DFA and then complementing the DFA
Answer: D

Which of the following is necessary for a language to be recognized by an NFA?

A) The language must be infinite.
B) The language must be context-free.
C) The language must be regular.
D) The language must be context-sensitive.
Answer: C

Which one of the following cannot be recognized by any NFA?

A) Strings with an even number of 0s
B) Palindromes
C) Strings containing ‘101’ as a substring
D) Strings ending with ‘0’
Answer: B

An NFA can be minimized by:

A) Combining equivalent states
B) Adding more states
C) Adding more transitions
D) Removing all final states
Answer: A

In a minimized NFA, each state represents:

A) A single string
B) A set of strings
C) A single input symbol
D) An epsilon transition
Answer: B

The product of two NFAs recognizing languages L1 and L2 will recognize:

A) L1 ∪ L2
B) L1 ∩ L2
C) L1 – L2
D) L1 concatenated with L2
Answer: B

An NFA can be converted to:

A) A DFA
B) A PDA
C) A Turing machine
D) None of the above
Answer: A

Which of the following is true about the start state of an NFA?

A) It can be any state.
B) It is the state from which the machine starts processing the input.
C) It is always an accept state.
D) It must have at least one incoming transition.
Answer: B

A language L is recognized by an NFA if and only if:

A) L is context-free.
B) L is context-sensitive.
C) L is regular.
D) L is recursively enumerable.
Answer: C

The transition function of an NFA takes as input:

A) A state and an input symbol
B) A state and an output symbol
C) Two states
D) Two input symbols
Answer: A