Finite automata formulas

Regular expressions and finite automata. 14 formulas for GATE CS Theory of Computation, each with when to use it. Each is explained in the topic notes.

All 14 Finite automata formulas

COMPLEMENT OF A DFA LANGUAGE

L (M^{'}) = L (M)^{c} where M^{'} = (Q, Σ, δ, q_{0}, Q ∖ F)

Valid only for a complete DFA. Swapping the accepting states of an NFA does not in general complement its language.

PRODUCT CONSTRUCTION (UNION, INTERSECTION, DIFFERENCE)

∣ Q ∣ \leq m \cdot n states for L (M_{1}) \cap L (M_{2}), L (M_{1}) \cup L (M_{2}), L (M_{1}) ∖ L (M_{2})

Run complete DFAs with $m$ and $n$ states together; states are pairs. Accept when both components accept (intersection), at least one accepts (union), the first accepts and the second does not (difference), or exactly one accepts (symmetric difference).

NUMBER OF DFAS ON N STATES

# DFAs = n^{nk} \cdot 2^{n}

For a fixed set of $n$ labelled states, a fixed start state and an alphabet of $k$ symbols: each of the $nk$ transitions has $n$ choices, and $F$ is any of the $2^{n}$ subsets of $Q$ . This counts machines, not languages; many machines accept the same language. Example: $n = 2$ , $k = 2$ gives $2^{4} \cdot 2^{2} = 64$ .

REMOVING EPSILON-MOVES (EPSILON-NFA TO NFA)

δ^{'} (q, a) = ECLOSE (p \in ECLOSE (q) ⋃ δ (p, a)), q \in F^{'} ⟺ ECLOSE (q) \cap F \neq = \emptyset

Same states and start state. Each new edge stands for ' $ε$ -moves, then $a$ , then $ε$ -moves'; a state becomes accepting if an accepting state can be reached from it by $ε$ -moves alone.

SIZE BOUND OF THE SUBSET CONSTRUCTION

DFA states \leq 2^{n} for an NFA with n states

The bound is tight: the language 'the $n$ -th symbol from the right is 1' has an $(n + 1)$ -state NFA whose minimal DFA has $2^{n}$ states. Often far fewer subsets are reachable.

MINIMAL DFA SIZE (MYHILL–NERODE)

# states of the minimal complete DFA = # equivalence classes of x \sim_{L} y ⟺ \forall z : (x z \in L \Leftrightarrow y z \in L)

Each class of prefixes is one state. $L$ is regular exactly when there are finitely many classes.

IDENTITIES FOR $\EMPTYSET$ AND $\VAREPSILON$

r + \emptyset = r, r ε = ε r = r, r \emptyset = \emptyset r = \emptyset, \emptyset^{*} = ε^{*} = ε, r + r = r

Union is commutative and associative; concatenation is associative but not commutative.

IDENTITIES FOR STAR

(r^{*})^{*} = r^{*}, r r^{*} = r^{*} r = r^{+}, ε + r r^{*} = r^{*}, (r + ε)^{*} = r^{*}

$r^{+}$ means one or more repetitions.

STAR OF A UNION

(r + s)^{*} = (r^{*} s^{*})^{*} = (r^{*} + s^{*})^{*} = (r^{*} s)^{*} r^{*} = r^{*} (s r^{*})^{*}

All five denote the strings formed by any mixture of $r$ -strings and $s$ -strings. $(r + s)^{*}$ is NOT equal to $r^{*} + s^{*}$ .

SHIFTING IDENTITY

r (sr)^{*} = (r s)^{*} r

Both sides are $r$ followed by alternating $s$ , $r$ blocks. $(r s)^{*} \neq = (sr)^{*}$ in general.

DISTRIBUTIVITY

r (s + t) = r s + r t, (s + t) r = sr + t r

Concatenation distributes over union on both sides; union does not distribute over concatenation ( $r + s t \neq = (r + s) (r + t)$ in general).

ARDEN'S RULE

R = Q + R P \Rightarrow R = Q P^{*}, R = Q + P R \Rightarrow R = P^{*} Q

When $ε \in / L (P)$ the stated solution is the unique one. When $ε \in L (P)$ it is still a solution (the smallest) but not the only one. The first form fits Arden's method below, where each equation lists the strings that reach a state.

SIZE OF THOMPSON'S MACHINE

# states \leq 2 m for a regular expression with m symbols and operators

Linear in the length of the expression. Each symbol ( $a$ , $ε$ or $\emptyset$ ) and each union or star adds two states; concatenation adds none.

OUTPUT LENGTH

∣ out_{Moore} (w) ∣ = ∣ w ∣ + 1, ∣ out_{Mealy} (w) ∣ = ∣ w ∣

Holds for every input $w$ because both machines are deterministic and complete.

Where this was asked: 2018 (2), 2020 (2), 2022 (1), 2023 (3), 2024 (5), 2025 (3), 2026 (2). See the 18 previous-year questions on Finite automata. This shows what was asked, not what will be asked.

KEEP GOING

Finite automata: the notes and 18 solved previous-year questions