Finite-State Recognizers

Run both machines at once. The product automaton's states are pairs (p, q), one component per machine, and each input symbol advances both components. Mark a pair accepting when both components accept, and you have the intersection.

Determinism means exactly one successor for every state-and-symbol pair, so the transition rule must be total and no run can ever get stuck. Symbols a rule forbids are usually routed to a non-accepting trap state that absorbs the rest of the input.

Two states are distinguishable when some remaining input is accepted from one and rejected from the other; that string is the witness. States with no such witness behave identically on every future input and can be merged without changing the accepted language.

Acceptance is existential: the machine accepts a string when at least one run over it ends in an accepting state. Runs that die on a missing transition, or finish in a non-accepting state, simply contribute nothing.

The epsilon-closure of a state set is that set plus every state reachable from it by epsilon moves alone. Determinisation needs it because such moves consume no symbol, so those states are already live before the next symbol arrives.

A finite-state recogniser has finitely many states, so it cannot track unbounded nesting depth. The pumping lemma makes that concrete: repeating a block of opening brackets inside a long balanced witness yields an unbalanced string the pattern must still accept.

Flipping accepting states complements the language only for a deterministic, total machine. A missing transition leaves a rejected string with no state to flip, and flipping a nondeterministic machine answers "some run ends non-accepting" instead of "no run accepts".

Make each state a remainder. Three states hold the value-so-far modulo three; reading digit d in remainder r moves to (10r + d) mod 3, which simplifies to (r + d) mod 3. Remainder zero is the accepting state.

Start with two blocks, accepting states and non-accepting states, then repeatedly split any block whose members send some input letter into different blocks. When no split applies, each remaining block becomes one state of the minimal machine.

Each state of the deterministic machine is a whole set of nondeterministic states — exactly those a prefix could have reached. Transitions map a set to the union of its members' successors, the empty set is the trap, and a set accepts if any member does.

Choosing the decomposition is the adversary's move, not the prover's. The lemma promises only that some legal split exists, so a valid argument must defeat every split allowed by the constraints; defeating one convenient split proves nothing.

Turn equality into emptiness. Build the product of the two machines, mark a pair accepting when exactly one component accepts, and search for a reachable accepting pair. None found means the machines agree; the first one found hands you a disagreeing string.

Because the symbol that broke the match can itself begin the next one. Each state records the longest prefix of 1 1 0 that ends the input so far, so after 1 1 1 the machine must stay at two matched symbols rather than drop to zero.

Refinement merges states that behave identically; it never deletes states. An unreachable state can be distinguishable from every reachable one, so it survives as its own block and inflates the result, even though no input can visit it and the accepted language is unchanged.

Nondeterministically the machine guesses which symbol is the k-th from the end and needs only k+1 states. Deterministically nothing can guess, so it must remember which of the last k symbols were markers — and all 2^k combinations occur.

Repetition only adds opening brackets, which keeps the strict inequality true, so pumping upward never leaves the language. Deleting the block instead drops the opening count to the closing count or below, breaking the strict inequality and giving the contradiction.

Decide by comparing build cost against per-message cost. Combining pays when rules are stable and messages are many; running both in lockstep pays when rules change constantly, when negating the deny rule risks a state explosion, or when operators need to know which rule fired.

You gain a unique object: for one language the minimal acceptor is the same machine up to renaming, so agreement becomes an identity check. You pay in readability, unstable diffs, and a contract that covers acceptance only, never outputs or timing.

A failed attempt proves nothing: the pumping property follows from being finite-state checkable but does not imply it, so failing to refute a format is not evidence for it. Spend the argument where the answer changes a design and the rule is stable.

Finiteness is a cycle test on the useful part of the graph. Keep the states that are both reachable from the start and able to reach an accepting state; if that live sub-graph contains a cycle, the language is infinite, otherwise it is finite.

Count the situations the machine must tell apart, because each one is a state. A remainder rule needs one state per remainder, a parity rule two, a fixed pattern of length k needs k plus one, and a window of the last k symbols needs about s to the power k.

Because the language has n+2 Myhill-Nerode classes: one per prefix length from 0 to n, plus one for everything already too long. A machine with fewer states would place two classes on one state and then give their separating suffix the same verdict, which is impossible.

Take a witness of exactly p times p cells, where p is the pumping length. The prefix bound caps the pumped block at p cells, so one extra repetition lands the length strictly between two consecutive squares — a length the rule rejects but the lemma says is accepted.

Trade per-symbol work against memory. Simulation costs work proportional to the live state set but needs only that set; full determinisation costs one table lookup but up to 2^n states. Building subsets on demand splits the difference at the price of a bounded cache.