Finite Automata Questions and Answers

Q: A language that is accepted by a non-deterministic finite automaton (NFA) is also accepted by

A language accepted by an NFA is also accepted by a deterministic finite automaton (DFA).By the subset (powerset) construction, any NFA with n states can be turned into an equivalent DFA with at most 2n states, each DFA state standing for a set of NFA states. So NFAs and DFAs accept exactly the same class, the regular languages.A Turing machine or pushdown automaton can also accept every regular language, but the word 'only' makes those options false. Since a DFA always exists, 'None of the above' is wrong as well.

Q: The minimum number of states required for a DFA to accept even parity (strings with even number of 1's over the alphabet {0,1}) is

The minimum is 2 states.The DFA only needs to track whether it has read an even or an odd number of 1s. State E (even, the start and accepting state) and state O (odd): a 1 switches between them and a 0 leaves the state unchanged.One state cannot work, because it would either accept or reject everything. Three or four states are more than needed; any extra state would be equivalent to E or O and merge in minimisation.

Q: The minimum number of states required for a DFA to accept strings with even number of 0's and even number of 1's over the alphabet {0,1} is

The minimum is 4 states.The DFA must remember the parity of 0s and the parity of 1s separately, giving four combinations: (even, even), (even, odd), (odd, even) and (odd, odd). Reading 0 flips the first parity, reading 1 flips the second. The start state and only accepting state is (even, even).All four states are distinguishable, since from each a different shortest string leads to acceptance, so none can merge. Two states track only one parity, three cannot hold four combinations, and five would include a redundant state.

Q: The minimum number of states required for DFA to accept binary strings that are divisible by 3 is

The minimum is 3 states.Read the binary number left to right and track the value modulo 3. Appending a bit b to a number x gives 2x + b, so the remainder changes as r to (2r + b) mod 3. Only three remainders are possible, 0, 1 and 2, so three states suffice, with remainder 0 as the start and accepting state.The three states are distinguishable (from remainder 1, reading 1 gives 0; from remainder 2, reading 0 then 1 is needed), so fewer cannot work, and a fourth state would be redundant.

Q: Which of the following is correct statement in Finite Automata ?

The key's answer is infinite tape length, unidirectional tape movement.In this textbook comparison a finite automaton reads its input from a tape that it scans in one direction only, left to right, one symbol per move, never moving back and never writing. The tape is not bounded in advance, since the input may be any length, which is what the paper calls infinite tape length.The decisive point is the movement: a Turing machine's head moves both ways on an unbounded tape, which is why the bi-directional options describe a Turing machine, not a finite automaton. Some books instead call the tape finite because it holds only the input, which would favour option B; the paper's key follows the convention of an unbounded, one-way, read-only tape.

11.

A language that is accepted by a non-deterministic finite automaton (NFA) is also accepted by

A.Deterministic finite automaton (DFA)
B.Turing machine only
C.Pushdown automaton only
D.None of the above

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: A

A language accepted by an NFA is also accepted by a deterministic finite automaton (DFA).

By the subset (powerset) construction, any NFA with n states can be turned into an equivalent DFA with at most 2ⁿ states, each DFA state standing for a set of NFA states. So NFAs and DFAs accept exactly the same class, the regular languages.

A Turing machine or pushdown automaton can also accept every regular language, but the word 'only' makes those options false. Since a DFA always exists, 'None of the above' is wrong as well.

Discuss in Forum

12.

The minimum number of states required for a DFA to accept even parity (strings with even number of 1's over the alphabet {0,1}) is

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

The minimum is 2 states.

The DFA only needs to track whether it has read an even or an odd number of 1s. State E (even, the start and accepting state) and state O (odd): a 1 switches between them and a 0 leaves the state unchanged.

One state cannot work, because it would either accept or reject everything. Three or four states are more than needed; any extra state would be equivalent to E or O and merge in minimisation.

Discuss in Forum

13.

The minimum number of states required for a DFA to accept strings with even number of 0's and even number of 1's over the alphabet {0,1} is

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The minimum is 4 states.

The DFA must remember the parity of 0s and the parity of 1s separately, giving four combinations: (even, even), (even, odd), (odd, even) and (odd, odd). Reading 0 flips the first parity, reading 1 flips the second. The start state and only accepting state is (even, even).

All four states are distinguishable, since from each a different shortest string leads to acceptance, so none can merge. Two states track only one parity, three cannot hold four combinations, and five would include a redundant state.

Discuss in Forum

14.

The minimum number of states required for DFA to accept binary strings that are divisible by 3 is

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The minimum is 3 states.

Read the binary number left to right and track the value modulo 3. Appending a bit b to a number x gives 2x + b, so the remainder changes as r to (2r + b) mod 3. Only three remainders are possible, 0, 1 and 2, so three states suffice, with remainder 0 as the start and accepting state.

The three states are distinguishable (from remainder 1, reading 1 gives 0; from remainder 2, reading 0 then 1 is needed), so fewer cannot work, and a fourth state would be redundant.

Discuss in Forum

15.

Which of the following is correct statement in Finite Automata ?

A.finite tape length, bi-directional tape movement
B.finite tape length, unidirectional tape movement
C.infinite tape length, unidirectional tape movement
D.infinite tape length, bi-directional tape movement

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: C

The key's answer is infinite tape length, unidirectional tape movement.

In this textbook comparison a finite automaton reads its input from a tape that it scans in one direction only, left to right, one symbol per move, never moving back and never writing. The tape is not bounded in advance, since the input may be any length, which is what the paper calls infinite tape length.

The decisive point is the movement: a Turing machine's head moves both ways on an unbounded tape, which is why the bi-directional options describe a Turing machine, not a finite automaton. Some books instead call the tape finite because it holds only the input, which would favour option B; the paper's key follows the convention of an unbounded, one-way, read-only tape.

Discuss in Forum

16.

Let L be a set accepted by a nondeterministic finite automaton. The number of states in non-deterministic finite automaton is \(|Q|\). The maximum number of states in equivalent finite automaton that accepts L is

A.\(|Q|\)
B.\(2|Q|\)
C.\(2^{|Q|} - 1\)
D.\(2^{|Q|}\)

Exam Year(s)

UGC NET - 2012,

Answer: D

The maximum number of states in the equivalent deterministic finite automaton is 2 to the power |Q|. Subset construction makes each state of the DFA a subset of the states of the NFA, and a set of |Q| elements has 2^|Q| subsets.

So the number cannot be more than 2^|Q|, though it may be less in many cases. The values |Q| and 2|Q| are too small to cover the subsets that may be needed, and 2^|Q| - 1 leaves out one subset, the empty set, which is the dead state.

Discuss in Forum

17.

The minimum number of states of the non-deterministic finite automation which accepts the language \(\{a\,b\,a\,b^{n} \mid n \ge 0\} \cup \{a\,b\,a^{n} \mid n \ge 0\}\) is

Exam Year(s)

UGC NET - 2012,

Answer: C

The language is the union of \(\{abab^n\}\) and \(\{aba^n\}\), with n at least 0. Strings of the first kind are aba followed by b's, and strings of the second kind are ab followed by a's. An automaton for both needs the states: \(q_0\) at the start, \(q_1\) after a, \(q_2\) after ab (accepting, since ab is in the second set with n = 0), \(q_3\) after aba (accepting, with a loop on a for \(aba^n\) and a move on b), and \(q_4\) after abab (accepting, with a loop on b). That is 5 states, and the non-determinism at \(q_3\) is not needed to save any state. The keyed answer is 5.

Discuss in Forum

18.

Given the following statements :

(i) The power of deterministic finite state machine and nondeterministic finite state machine are same.
(ii) The power of deterministic pushdown automaton and nondeterministic pushdown automaton are same.
Which of the above is the correct statement(s) ?

A.Both (i) and (ii)
B.Only (i)
C.Only (ii)
D.Neither (i) nor (ii)

Exam Year(s)

UGC NET - 2012,

Answer: B

Statement (i) is true: every language accepted by a non-deterministic finite automaton is accepted by a deterministic one, by the subset construction, so the two have the same power. Statement (ii) is false: a deterministic pushdown automaton accepts only the deterministic context free languages, while a non-deterministic one accepts all context free languages, as the language of even-length palindromes shows, which needs a guess of the middle. So only (i) is correct, option (B).

Discuss in Forum

19.

Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below :

	a	b
p	-	q
q	r	s
r	r	s
s	r	s

The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is

Exam Year(s)

UGC NET - 2013,

Answer: C

The minimum DFA has 3 states, option (C). From the table the NFA is in fact deterministic, with no move from p on a. Starting at p, the reachable states are p, then q on b, then r and s. The states q and s have identical rows (a to r, b to s) and both are non-final, so they are equivalent and merge into one state. The final state r has the same moves but is final, so it stays separate, and p differs from them because its a move leads to nowhere. The minimal machine has p, the merged q and s, and r: 3 states, if the dead state for the missing move is not counted. So (C), and options (A) 5, (B) 4 and (D) 2 do not match this minimisation.

Discuss in Forum

20.

The number of states in a minimal deterministic finite automaton corresponding to the language \(L = \{ a^{n} \mid n \ge 4 \}\) is

Exam Year(s)

UGC NET - 2013,

Answer: C

The language of strings with at least four a's needs a minimal DFA with 5 states: one state for each count of a's from 0 to 3, and an accepting state for four or more.

The strings a^0, a, a^2, a^3 and a^4 are pairwise distinguishable by the suffixes that complete them to a member of the language, so fewer than 5 states are not enough, while 6 states are more than needed because every count from four onwards behaves in the same way. Option C is correct.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Finite Automata Questions and Answers || Finite Automata MCQ Questions and Answers || Finite Automata GK Questions and Answers || Finite Automata GK MCQ Questions || Finite Automata Multiple Choice Questions and Answers || Finite Automata GK || GK on Finite Automata || Theory of Computation Questions and Answers || Theory of Computation MCQ Questions and Answers || Theory of Computation GK Questions and Answers || GK on Theory of Computation

Finite Automata Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications