DFA Basics and Definitions MCQs: 12 Solved Questions with Explanations

A DFA has one active state after each symbol, yet questions become difficult when you guess a language from the picture, stop before consuming the whole string, or count free-bit combinations without tracing them. These 12 questions are all previous-year problems, drawn from GATE 1998 through 2015, ISRO 2014, HPSC 2015, UPPSC Polytechnic Lecturer 2022 and Beltron Programmer 2025, and they move from definitions and state counts to language recognition and complete traces. Choose an option first, then write a transition sequence or finite-memory argument before reading the explanation. Around two dozen DFA basics questions sit inside GATE CS Exam Preparation, and Questions 1, 2 and 5 can be attempted there through the DFA Basics and Definitions PYQ Questions hub.

1. DFA rules to fix before solving the 12 MCQs

For strings ending in 00, use start q0, q1 for “one trailing 0”, and final q2 for “suffix 00”. Set δ(q0,0)=q1, δ(q0,1)=q0, δ(q1,0)=q2, δ(q1,1)=q0, δ(q2,0)=q2, and δ(q2,1)=q0.

For 10100, the complete trace is q0 --1--> q0 --0--> q1 --1--> q0 --0--> q1 --0--> q2, so accept. For 10101, it is q0 --1--> q0 --0--> q1 --1--> q0 --0--> q1 --1--> q0, so reject.

2. DFA MCQs 1-3: determinism, acceptance and finite memory

Question 1 (Beltron Programmer 2025)

Which of the following best characterises a Deterministic Finite State Machine (DFSM)?

A. For every state and input symbol, there is exactly one defined next state.
B. It may produce outputs for each state transition.
C. It accepts context-sensitive languages.
D. It can transition to multiple states for a given input and current state.

Correct answer: A.

A DFA uses δ: Q × Σ -> Q, so each (state, symbol) pair maps to one state. B is not the defining property, C exceeds DFA power, and D is nondeterminism.

Question 2 (Beltron Programmer 2025)

Which of the following best describes the acceptance condition for a string in finite automata?

A. The input string must be empty
B. The machine must reach the initial state
C. The automaton ends in an accepting (final) state after consuming the entire string
D. The input alphabet must be infinite

Correct answer: C.

Consume every symbol, then inspect the reached state. 10100 ends at final q2, but one more symbol makes 10101 end at non-final q0.

Question 3 (ISRO 2014)

The number of states required by a Finite State Machine, to simulate the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits is?

A. m x 2ⁿ
B. 2ᵐ⁺ⁿ
C. 2ᵐⁿ
D. m+n

Correct answer: C. 2^(mn).

There are mn independent bits and therefore 2^(mn) configurations, each requiring a state. For m=3, n=2, six bits give 2^6=64, ruling out 12, 32, and 5. Recount the configurations yourself, then open the Question 3 solution page.

3. DFA MCQs 4-6: final states and regular-language limits

Question 4 (UPPSC Polytechnic Lecturer 2022)

The sum of minimum and maximum number of final states in a DFA having n states is ____

A. n
B. n+1
C. 2n
D. n-1

Correct answer: A. n.

Because F may be any subset of Q, its minimum size is 0 and maximum is n. For n=5, 0+5=5. Pick your own value of n before opening the Question 4 solution page.

Question 5 (Beltron Programmer 2025)

Which of the following is accepted by Finite Automata?

A. Context-free languages
B. Regular languages
C. Recursive languages
D. Recursively enumerable languages

Correct answer: B.

Finite automata characterise exactly the regular languages. The broader classes in A, C and D all contain the regular languages, but each needs memory a DFA does not have: a DFA can count length modulo 3 because three states suffice, yet it can never count an unbounded quantity such as matching parentheses.

Question 6 (HPSC 2015)

Palindromes cannot be recognized by:

A. FSM (Finite State Machine)
B. PDA (Pushdown Automata)
C. Post Machine
D. Turing Machine

Correct answer: A.

Unrestricted palindromes need growing memory to compare the second half with the reversed first half. An FSM has only finite memory, although a finite set of palindromes could be regular. Try building a finite-state machine for palindromes yourself, then open the Question 6 solution page.

4. DFA MCQs 7-9: read the language from the transition graph

Question 7 (GATE 2009)

The following DFA accepts the set of all strings over {0,1} that

A. Begin either with 0 or 1
B. End with 0
C. End with 00
D. Contain the substring 00

Correct answer: C. End with 00.

The states remember zero, one, or at least two trailing zeros. 10100 finishes final; 00101 returns to the start, containing 00 but not ending in 00. Redraw the three states from memory before opening the Question 7 solution page.

Question 8 (GATE 2015)

Consider the following Deterministic Finite Automata. Which of the following is true?

A. It accepts all strings with prefix as “aababb”
B. It accepts all strings with substring as “aababb”
C. It accepts all strings with suffix as “aababb”
D. None of the above

Correct answer: B.

The path into the final state reads aababb; fallbacks permit a prefix, and final-state loops permit a suffix. Therefore aababb, baababb, and aababba pass, but incomplete aabab fails. Test one more string of your own, then open the Question 8 solution page.

Question 9 (GATE 2006, Information Technology)

In the automaton below, s is the start state and t is the only final state.
Consider the strings u = ababab, v = bab, and w = aabb. Which of the following statements is true?

A. The automaton accepts u and v but not w
B. The automaton accepts each of u, v, and w
C. The automaton rejects each of u, v, and w
D. The automaton accepts u but rejects v and w

Correct answer: C.

Call the lower state r. The traces u: s->r->r->s->t->t->s, v: s->t->t->s, and w: s->r->s->t->s all finish at non-final s. Retrace u, v and w yourself before opening the Question 9 solution page.

5. DFA MCQs 10-12: enumerate constrained strings and test regularity

Question 10 (GATE 2003)

Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

A. 1
B. 5
C. 7
D. 8

Correct answer: C. 7.

The form 1 b2 b3 1 b5 b6 1 has four free bits and 2^4=16 candidates; acceptance follows seeing 001. The seven are 1001001, 1001011, 1001101, 1001111, 1011001, 1101001, and 1111001; 1011011 never completes 001. List the sixteen candidates yourself, then open the Question 10 solution page.

Question 11 (ISRO 2014)

Consider the following Deterministic Finite Automaton M.

Let S denote the set of eight-bit strings whose second, third, sixth and seventh bits are 1. The number of strings in S that are accepted by M is ____

A. 0
B. 1
C. 2
D. 3

Correct answer: C. 2.

The form b1 1 1 b4 b5 1 1 b8 has four free bits and 16 candidates; only 01110110 and 01110111 reach q4. The first traces q0->q1->q2->q1->q2->q3->q4->q4->q4, while 01100110 ends at q0. Write the transition table out before opening the Question 11 solution page.

Question 12 (GATE 1998)

Which of the following sets can be recognized by a Deterministic Finite-state Automaton?

A. The numbers 1, 2, 4, 8, ..., 2^n, ... written in binary.
B. The numbers 1, 2, 4, 8, ..., 2^n, ... written in unary.
C. The set of binary strings in which the number of zeros is the same as the number of ones.
D. The set {1, 101, 11011, 1110111, ...}.

Correct answer: A.

Binary powers of two are 1, 10, 100, ..., exactly regular expression 10*. B requires recognising lengths 2^n, C needs unbounded equal counting, and D needs matching the 1s around 0; these are not regular. Name the language family behind each option, then open the Question 12 solution page.

6. DFA traps these questions expose

Write every reached state and circle only the last. Record its memory, then compute 2^(free bits) before enumeration. In Question 7, 00101 separates “contains 00” from “ends with 00”; in Question 8, baababba proves a prefix and suffix may surround aababb.

Language recognition differs from minimality. Next, study DFA Minimization for GATE and try Finite Automata MCQs: 10 solved questions on DFA, NFA and minimization.

7. DFA basics and definitions: the short version and next step

Retest Questions 3, 7, 9, 10, 11 and 12 closed-book. They cover configuration counting, suffix memory, full traces, constrained enumeration and the boundary of regular languages.

• One state-symbol pair has one next state.

• The full input must be consumed.

• Acceptance depends on the ending state.

• States encode only finite memory.

• DFAs recognise exactly regular languages.

For a sequenced Theory of Computation route that places DFA definitions beside NFA equivalence, regular expressions and minimisation, continue with GATE Guidance by Sanchit Sir. For every wrong graph question, write the state sequence symbol by symbol before attempting another MCQ.