Regular languages formulas

Applies to a total DFA only. If some transitions are missing, first add a dead (trap) state and send every missing transition to it. The complement DFA has the same states, so the minimal total DFAs of $L$ and $L^c$ have the same number of states. Swapping accepting states in an NFA does not complement it: convert the NFA to a DFA first (the subset construction can need up to $2^n$ states for an $n$-state NFA).

For total DFAs with $m$ and $n$ states, the product has $mn$ states. A pair is accepting when both components accept for intersection, when either accepts for union, and when the first accepts and the second does not for difference.

Here $\hat{\delta }$ is the extended transition function on strings, with $\hat{\delta }(q,\epsilon )=q$. The new DFA has the same states, start state and accepting states as the DFA for $L$, and it accepts $h^{-1}(L)=\{w:h(w)\in L\}$.

The implication runs one way only. A language can satisfy the conditions and still be non-regular, so the lemma can prove non-regularity but never regularity. For example, $\{a^i{b}^j{c}^k:i=0\text{ or }j=k\}$ satisfies the lemma with $p=1$ (pump the first symbol), yet it is not regular: its intersection with $a{b}^{\ast }{c}^{\ast }$ is $\{a{b}^n{c}^n:n\ge 0\}$. The pumping length $p$ can be taken as the number of states of any DFA for $L$.

Unlike the pumping lemma, this is an iff. The number of classes equals the number of states of the minimal total DFA for $L$, counting the dead state if the minimal total DFA has one.