DFA Construction & Design MCQs: 12 Solved Questions with Explanations

DFA questions can look unrelated, but most reduce to four memory jobs: track a remainder, remember a useful suffix, combine independent conditions, or recognise when finite memory is not enough. Those four jobs run through most of the twelve previous-year questions below: a remainder counter for lengths and for binary values, a suffix tracker for patterns like 101 and aba, a Cartesian product when two independent counts must both come out right, and the palindrome case where no finite memory suffices. Choose an option first, then sketch what each necessary state must remember before reading the explanation. The DFA Construction & Design set on KnowledgeGate runs to more than 70 questions, so keep practising there once these twelve are done. Use the GATE CS Exam Preparation path when you want to place this topic inside the wider syllabus.

DFA construction in three steps

Before drawing circles, ask three questions:

1. What part of the prefix can still affect a future decision?

2. Which distinct memories cannot be merged?

3. What memory follows after each alphabet symbol?

Define every state with a sentence that states its memory, then add transitions, the start state and accepting states.

For example, consider L = {w in {0,1}* | w ends with 01}. Use q0 for no useful suffix, q1 when the current useful suffix is 0, and accepting q2 when the current suffix is 01. The complete transitions are:

• q0 --0--> q1, q0 --1--> q0

• q1 --0--> q1, q1 --1--> q2

• q2 --0--> q1, q2 --1--> q0

Trace 101: q0 -> q0 -> q1 -> q2, so it is accepted. Trace the near-miss 010: q0 -> q1 -> q2 -> q1, so it is rejected. The empty string stays at non-accepting q0.

That gives a practical check for any construction: test one positive string, one near-miss and the empty string. If two states respond differently to some continuation, they are distinguishable and cannot be merged.

DFA MCQs 1-3: equivalence, counting machines and complement

Question 1: Machine equivalence (UGC NET 2018)

Two finite state machines are said to be equivalent if they :

• A. Have the same number of edges

• B. Have the same number of states

• C. Recognize the same set of tokens

• D. Have the same number of states and edges

Correct answer: C. Recognize the same set of tokens.

Equivalence is observable behaviour, not drawing shape. State names, state counts and redundant edges may differ. Machines are equivalent when they accept exactly the same language, expressed here as the same set of tokens.

Question 2: Counting three-state machines (UGC NET 2015)

There are exactly ____ different finite automata with three states 𝑥, 𝑦 and 𝑧 over the alphabet {𝑎,𝑏} where 𝑥 is always the start state.

• A. 64

• B. 256

• C. 1024

• D. 5832

Correct answer: D. 5832.

Under the DFA interpretation, there are 3 × 2 = 6 state-symbol entries. Each can lead to any of three states, giving 3^6 = 729 transition functions. Any subset may be final, giving 2^3 = 8 choices. The start is fixed. Total: 729 × 8 = 5832.

Question 3: A complement with the same minimum size (GATE 2021)

Let \(L⊆\{0,1\}^∗\) be an arbitrary regular language accepted by a minimal DFA with \(k\) states. Which one of the following languages must necessarily be accepted by a minimal DFA with \(k\) states?

• A. \(L-\{01\}\)

• B. \(L \cup \{01\}\)

• C. \(\{0,1\}^* - L\)

• D. \(L \cdot L\)

Correct answer: C. \(\{0,1\}^* - L\).

Complement a complete DFA by swapping final and non-final states. Transitions and state count remain unchanged. A suffix that distinguished two states before still makes exactly one accept after the swap, so minimality remains. The other operations can change the minimum size.

DFA MCQs 4-6: length residues and divisibility states

Question 4: Length divisible by three (GATE 2002)

The smallest finite automation which accepts the language { x | length of x is divisible by 3 } has

• A. 2 states

• B. 3 states

• C. 4 states

• D. 5 states

Correct answer: B. 3 states.

Remember length modulo 3. States q0, q1 and q2 mean remainders 0, 1 and 2. Every symbol changes r to (r + 1) mod 3, and only q0 accepts. The three distinguishable remainders make three states necessary and sufficient.

Question 5: Two independent count conditions (GATE 2007)

A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

• A. 15 states

• B. 11 states

• C. 10 states

• D. 9 states

Correct answer: A. 15 states.

Remember (number of 0s mod 3, number of 1s mod 5). Its coordinates have three and five values, producing 3 × 5 = 15 reachable pairs. A 0 changes only the first coordinate, and a 1 only the second. Only (0,0) accepts. Independent memories multiply, not add.

Question 6: Binary numbers divisible by three (Bihar STET 2025)

For a DFA accepting binary numbers whose decimal equivalent is divisible by 3, what are all the possible remainders?

• A. 0

• B. 0,2

• C. 0,1,2

• D. 0,1,2,3

Correct answer: C. 0,1,2.

Division by 3 has remainders 0, 1 and 2. Appending bit b changes value N to 2N + b, so the update is (2r + b) mod 3. Remainder 0 accepts. Remainder 3 is not distinct because it reduces to 0.

DFA MCQs 7-9: product states, suffix memory and substring progress

Question 7: A larger product construction (GATE 2001)

Consider a DFA over Σ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?

• A. 8

• B. 14

• C. 15

• D. 48

Correct answer: D. 48.

Use (count(a) mod 6, count(b) mod 8). Six first-coordinate values and eight second-coordinate values give 6 × 8 = 48 reachable, distinguishable states. Only (0,0) accepts. One counter needs its modulus in states. Independent counters require their Cartesian product.

Question 8: Strings not ending in 101 (ISRO 2020)

Minimum number of states required in DFA accepting binary strings not ending in “101” is

• A. 3

• B. 4

• C. 5

• D. 6

Correct answer: B. 4.

Track the longest suffix that is a prefix of 101: no match, 1, 10, or 101. These four memories determine the next transition. The full-match state alone accepts strings ending in 101. Complementing acceptance gives strings not ending in 101 with the same four states.

Question 9: Detecting aba as a substring (HPSC 2021)

What is the total number of states that are required to automate the given expression i.e. {a,b}{aba}{a,b} using finite automata?

• A. 4

• B. 3

• C. 5

• D. 6

Correct answer: A. 4.

The expression means aba occurs somewhere. Track matched-prefix lengths 0, 1 and 2 for "", a and ab. Completing aba reaches the fourth state. Later input cannot undo a found substring, so that state is an accepting sink.

DFA MCQs 10-12: last-symbol memory, one excluded length and finite-memory limits

Question 10: The last two symbols are equal (Coal India 2020)

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite state automaton accepting language is ______.

• A. 2

• B. 5

• C. 8

• D. 3

Correct answer: B. 5.

The five memories are: no symbol, last symbol 0 without a pair, last symbol 1 without a pair, suffix 00, and suffix 11. The last two accept. A symbol change returns to a one-symbol state. The separate start is needed because one-symbol strings reject.

Question 11: Rejecting exactly one unary length (UGC NET 2015)

Minimal deterministic finite automaton for the language \(L=\{0^n \mid n \geq 0, n \neq 4 \}\) will have :

• A. 1 final state among 5 states

• B. 4 final states among 5 states

• C. 1 final state among 6 states

• D. 5 final state among 6 states

Correct answer: D. 5 final state among 6 states.

Keep lengths 0 through 4 separate, then merge all lengths at least 5 into an accepting sink. More 0s can never return to length 4. That gives six states. Only length 4 rejects, so the other five accept, including the start for n = 0.

Question 12: The palindrome boundary (Bihar STET 2025)

Can a DFA recognize a palindrome number?

• A. Yes

• B. No

• C. Yes, with input alphabet as ∑*

• D. Can't be determined

Correct answer: B. No.

Arbitrary-length palindromes require remembering an unbounded first half and comparing it with the reversed second half. A DFA has finite memory, so it cannot recognise the full palindrome language. A fixed maximum length would instead produce a finite language that a DFA could recognise.

Six recurring DFA construction traps

Under time pressure, name the exact memory, list its values, multiply only independent dimensions, and mark accepting values. Test ε, the shortest positive string and a near-miss. For minimisation, find a continuation on which one proposed state accepts and the other rejects. DFA Minimization for GATE develops this test. If deterministic and nondeterministic choices are getting mixed together, review Finite Automata: DFA vs NFA and Subset Construction.

DFA Construction & Design: the next practice step

Retest yourself on Questions 2, 5, 8, 9, 11 and 12 without looking at the answers during your next revision. Together they cover machine counting, product states, suffix tracking, substring progress, a finite exception and a non-regular boundary. If you want DFA construction inside a sequenced Theory of Computation route, continue with GATE Guidance by Sanchit Sir. Readers following the UGC NET Computer Science route can use NTA-UGC-NET Paper - 2. The short version is simple: every correct DFA state has a precise sentence explaining what the machine remembers. If that sentence is vague, the transitions will be vague too.