High yield ●●●

🔁 Finite Automata (DFA, NFA, ε-NFA)

Why it matters: The most predictable TOC marks: count states of a minimal DFA, read the language of a given automaton, convert NFA to DFA.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.

Formulas

Ends with a fixed string of length m
minimal DFA has m + 1 states
Contains a fixed substring of length m
minimal DFA has m + 1 states
Number of a's ≡ r (mod k)
k states (also: length ≡ r mod k)
Starts with a string of length m
m + 2 states (m + 1 plus one dead state)
m-th symbol from the end is a fixed symbol
2^m states in the minimal DFA (NFA needs only m + 1)
Product construction
|Q₁| × |Q₂| states for union or intersection
Subset construction bound
n NFA states → at most 2^n DFA states
Complement
swap F and Q − F (the DFA must be complete, i.e. have a dead state if needed)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Minimum number of states in a DFA for a language
Ends with / contains / divisible by / starts with. Decide whether a dead state is counted (complete DFA).
★★★
What language does this automaton accept?
Given a DFA/NFA figure, pick the regex, the verbal description, or a string that is accepted.
★★★
NFA → DFA state count
Run the subset construction on a small NFA and count reachable subsets.
★★★
Equivalence of DFA states / closure statements
Which states merge in the minimal DFA; true/false on NFA vs DFA power.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

6 real questions from the official GATE CSE papers (2013 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

6 questions · 0 correct of 0 attempted · marks 0 / 9

Year:
GATE 2025 CS1 · Q28MSQ1 mark
A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

One or more options may be correct. Select all that apply, then submit.

GATE 2023 · Q63NAT2 marks
Consider the language L over the alphabet {0, 1}, given below: L = {w ∈ {0, 1}* | w does not contain three or more consecutive 1's}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is ______.
GATE 2020 · Q51NAT2 marks
Consider the following language: L = { x ∈ {a, b}* | number of a's in x is divisible by 2 but not divisible by 3 }. The minimum number of states in a DFA that accepts L is ______.
GATE 2018 · Q6MCQ1 mark
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
GATE 2017 Set 1 · Q22NAT1 mark
Consider the language L given by the regular expression (a + b)*b(a + b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ______.
GATE 2013 Code A · Q33MCQ2 marks
Consider the DFA A with three states. The start state q0 goes to q1 on 1 and to q2 on 0. State q1 loops to itself on 1 and goes to q2 on 0. State q2 is the only accepting state and loops to itself on both 0 and 1. Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0 + 0)(0 + 1)*1*).
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.

Common traps

The dead state counts as a state in a complete minimal DFA but is often omitted in diagrams; read the question.
You cannot complement an NFA by swapping final states; determinise first.
"Ends with" and "contains" patterns have the same state count but different structure.
ε-closure applies to the start state and after every move.