Finite Automata and Regular Language Questions in GATE CSE

Finite automata are the most mechanical part of Theory of Computation, which is why the marks there are the easiest to secure and the easiest to drop. The state-count questions have one method, the closure questions have one table, and the pumping lemma has one order of moves. Almost every lost mark comes from a state that was not counted or a proof run backwards.

Key takeaways

• A minimal DFA state count is a count of equivalence classes. Build the classes, do not draw a diagram and hope it is minimal.
• Counting one symbol modulo k needs exactly k states. Binary value modulo an even k collapses to fewer.
• The n-th symbol from the right needs 2^n states; the n-th from the left needs about n. The gap is the whole point of the question.
• A DFA is complete, so the dead state is a state. Count it whenever some prefix makes acceptance impossible.
• The pumping lemma can only prove non-regularity. A language that satisfies it may still be non-regular.

Where this sits in the paper

The official 2027 syllabus names regular expressions and finite automata first, ahead of grammars, push-down automata, the pumping lemma and Turing machines. Those first items carry more than their share of the questions.

Third-party analyst compilations place Theory of Computation between 5 and 10 marks per paper from 2009 to 2026, averaging about 7.8. The average is 7.6 for 2009 to 2017 and 8.1 for 2018 to 2026, so the direction is stable rather than rising. These figures are unofficial, and sources disagree by two or three marks because borderline questions on grammars or countability get classified under Compiler Design or Discrete Mathematics instead. The same analysts rate Algorithms and Theory of Computation as the two most consistently difficult subjects, for a structural reason: almost nothing here is solved by substituting into a formula.

Exam dates, the paper pattern and any syllabus revision are the year-dependent parts, so check the current official notification for those. The subject-level ranking sits in the Theory of Computation important topics guide, and the cross-subject numbers are in the subject-wise weightage breakdown.

Minimum-state DFA: count classes, not circles

Every state-count question is the same question in disguise. Two strings x and y need separate states exactly when some suffix z sends one into the language and the other out of it. That relation is Myhill-Nerode equivalence, and the number of its classes is the number of states in the minimal DFA. Nothing else can be smaller.

That gives you both halves of an answer. For a lower bound, list m strings and for each pair name a suffix that separates them; the machine then needs at least m states. For an upper bound, exhibit a DFA with m states. When the two meet you are done, and you never had to run the table-filling algorithm.

Residue families

For the language of strings in which one symbol occurs a number of times congruent to r modulo k, the minimal DFA has exactly k states. Each residue is reachable, and any two residues are separated by appending enough copies of that symbol to push one of them to r. There is no dead state, because every string can still be repaired.

Binary-value divisibility looks identical and is not. Reading most significant bit first, the residue updates as r becomes (2r + b) mod k. When k is odd the residues stay distinct, but when k is even, doubling destroys information and residues merge. For divisibility by 4, residues 1 and 3 become indistinguishable, and the minimal machine has three states rather than four, because divisibility by 4 just means the string ends in two zeros.

Positional families

This is the family that separates candidates. Take the language of strings whose n-th symbol from the right is 1. Any two distinct blocks of n symbols differ at some position j from the left; append j minus 1 zeros and that position lands exactly in the n-th slot from the right, so the two blocks are separated. All 2^n blocks are pairwise inequivalent, so the minimal DFA needs 2^n states. An NFA needs only about n plus one, because it can guess where the marked position starts.

Now move the condition to the left end. For strings whose n-th symbol from the left is 1, the machine counts positions 1 to n, then either accepts everything after or rejects everything after. That is n counting states plus one accepting sink plus one dead sink, so about n plus 2. Same sentence, exponentially different answer, and that contrast is the classic setup.

Products and collapses

Two independent conditions combine by the product construction: residue moduli p and q give p times q states. The trap is assuming the product is always minimal. If one condition follows from the other, it collapses. Requiring two symbol counts to be congruent modulo 2 is really a condition on length parity alone, so four product states merge into two. Build the product, then check every pair of states with the same acceptance status for identical futures before writing the answer.

The dead state and the complement

A DFA in GATE is complete: every state has an outgoing edge on every symbol. So the moment some prefix makes acceptance impossible forever, a trap state exists and it counts. Positional-from-the-left languages need one. Substring and suffix languages do not, because any string can still be extended into the language.

Complement is where this bites hardest. Swapping accepting and non-accepting states on a complete DFA gives the complement, and the state count does not change, so the minimal DFA of a language and of its complement always have the same size. The trap is that an accepting absorbing state in the original becomes a non-accepting trap in the complement, and candidates who never drew it lose exactly one state.

Reversal behaves differently. Reverse every arrow, make the old accepting states initial and the old initial state accepting, and you have an NFA for the reversal. Determinizing that can cost an exponential, so the minimal DFA of the reverse can be much larger. Union and concatenation of two minimal DFAs also carry no guarantee of minimality.

NFA to DFA without the blow-up

Subset construction says an n-state NFA has an equivalent DFA with at most 2^n states, and the bound is tight because the n-th-symbol-from-the-right language attains it. In the exam, only reachable subsets matter. Start from the epsilon closure of the initial state, expand one subset at a time in a table, and stop when no new subset appears. Most questions settle at five or six subsets. Then minimize, because a reachable-subset DFA is frequently not minimal.

Regular expression equivalence

Two expressions are equivalent when they denote the same language, and the reliable test is to build the minimal DFA for each and compare. The fast exam version is three test strings: the empty string, the shortest string that must be in the language, and the shortest string that must be out. Most wrong options fail on one of those three.

Keep the identities straight. Star is idempotent, so starring a starred expression changes nothing. The star of a union equals the star of the concatenation of the two stars, which is why an expression can describe all strings while looking narrower. But the star of a concatenation is not the concatenation of stars: the first forces the symbols to alternate in pairs. The star of the empty language is the language containing only the empty string.

Closure properties

Regular languages are closed under union, intersection, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism and quotient. That is nearly everything, which is why questions attack the exceptions instead.

Pumping lemma as an adversary game

The lemma is a chain of alternating quantifiers, and the only safe way to use it is as a game with a fixed move order. The adversary picks a pumping length p, and you never get to see or choose it. You then pick a string w in the language of length at least p. The adversary splits w into x, y and z with the length of xy at most p and y non-empty. You pick an exponent i and show that xy raised to i, followed by z, is outside the language.

Two consequences follow. Choose w only after p is fixed, and choose it so that the first p symbols are uniform, which traps y inside that block. For a language matching the counts of two symbols, p copies of the first symbol followed by p copies of the second does exactly that, and any non-empty y then unbalances the counts. And pumping down with i equal to 0 is sometimes the only move that works, so try it before giving up.

The classic trap is the reverse implication. The lemma is necessary, not sufficient. There are non-regular languages that satisfy it, including a standard three-symbol language in which a count condition switches on only when the first symbol occurs exactly once. A language that survives your pumping attempt has proved nothing, and an option claiming that the lemma establishes regularity is always wrong.

Myhill-Nerode is usually faster and works in both directions. For the language matching counts of two symbols, the prefixes of one, two, three copies of the first symbol are pairwise separated by the matching block of the second, so there are infinitely many classes and no finite automaton exists. That argument takes two lines and cannot be run backwards by accident.

The traps in one list

• The dead state is a state. Draw it before counting.
• Product size is an upper bound, not the answer. Check for merges.
• The complement has the same minimal state count; the reversal need not.
• The n-th symbol from the right is exponential; from the left it is linear.
• Binary-value divisibility by an even modulus collapses below the modulus.
• A subset of a regular language need not be regular, and an infinite union of regular languages need not be regular.
• The star of a concatenation is not the concatenation of stars.
• The pumping lemma proves non-regularity only, and you must choose the string after the pumping length.

Rehearse these on paper by picking one language a day and writing its equivalence classes before drawing anything. The same discipline applied across subjects is in the guide to common mistakes that cost marks, and the evidence for which forms deserve the most drilling is in the note on important questions for 2027. The Theory of Computation chapter of the GATE CSE 2027 book carries the full year-by-year map of which automata forms appeared when, plus a worked bank of state-count and classification items with complete derivations.