KLEENE'S THEOREM (1956): A LANGUAGE IS DESCRIBED BY A REGULAR EXPRESSION IF AND ONLY IF IT IS ACCEPTED BY A FINITE AUTOMATON. The proof is in two directions, and BOTH ARE CONSTRUCTIVE — they are algorithms, not existence arguments, which is what makes them useful in practice. ── DIRECTION 1: REGULAR EXPRESSION → NFA ─────────────────── THOMPSON'S CONSTRUCTION, by induction on the structure of the expression. Each piece is built as an NFA with EXACTLY ONE START STATE AND EXACTLY ONE ACCEPTING STATE, which is what makes the pieces composable. BASE CASES: ∅ → two states, no transitions at all ε → two states joined by an ε-transition a → two states joined by an a-transition INDUCTIVE CASES, given machines N(r) and N(s): UNION r + s A new start state with ε-transitions into BOTH N(r) and N(s); their accepting states given ε-transitions to a new single accepting state. ┌─ε→ [N(r)] ─ε─┐ →○──┤ ├──→◎ └─ε→ [N(s)] ─ε─┘ THE NON-DETERMINISM IS THE CHOICE at the new start state — the machine tries both branches. CONCATENATION r s The accepting state of N(r) is joined by an ε-transition to the start state of N(s). →[N(r)] ─ε→ [N(s)]→◎ KLEENE STAR r* A new start and accept state, with FOUR ε-transitions: new start → N(r)'s start (enter the loop) N(r)'s accept → N(r)'s start (repeat) N(r)'s accept → new accept (exit) new start → new accept (SKIP ENTIRELY — this is what supplies ε ∈ L(r*)) THE FOURTH TRANSITION IS THE ONE STUDENTS OMIT, and without it the machine cannot accept the empty string, which r* must. THE SIZE GUARANTEE: an expression with n symbols yields an NFA with AT MOST 2n STATES — the construction adds at most two states per operator. It is LINEAR, which is why it is practical. ── DIRECTION 2: FINITE AUTOMATON → REGULAR EXPRESSION ────── Two standard methods. METHOD A — STATE ELIMINATION, the one to use in an exam. 1. Add a NEW start state with an ε-transition to the old start, and a NEW single accept state with ε-transitions from all old accepting states. (This guarantees the start has no incoming and the accept no outgoing transitions.) 2. Repeatedly REMOVE one intermediate state q at a time. For every pair of states p → q → r, replace the path with a direct transition labelled R(p,r) += R(p,q) · R(q,q)* · R(q,r) where R(q,q) is the label on q's self-loop (or ε if none). THE STAR ON THE SELF-LOOP IS THE HEART OF THE METHOD: it captures "go round the loop at q any number of times before leaving". 3. When only the new start and accept remain, the label on the single remaining transition IS the regular expression. THE ORDER OF ELIMINATION AFFECTS THE SIZE OF THE RESULT BUT NOT ITS CORRECTNESS. Eliminating the most-connected states last usually gives a shorter expression. METHOD B — ARDEN'S THEOREM, an algebraic alternative. Write one equation per state, expressing it as the set of strings reaching it. Then solve using: IF X = XA + B AND ε ∉ L(A), THEN X = BA* THE CONDITION ε ∉ L(A) IS ESSENTIAL: without it the solution is not unique, and this is the detail examiners check. ── A WORKED STATE ELIMINATION ────────────────────────────── DFA: states A (start), B (accepting); δ(A,0)=A, δ(A,1)=B, δ(B,0)=B, δ(B,1)=A. Add new start S →ε A, and new accept T with B →ε T. ELIMINATE A: A has a self-loop 0, is entered from S by ε and from B by 1, and leaves to B by 1. S → B gets ε · 0* · 1 = 0*1 B → B gets 1 · 0* · 1 added to its existing self-loop 0, giving 0 + 10*1 ELIMINATE B: now S → B → T with B's self-loop (0 + 10*1). S → T gets 0*1 · (0 + 10*1)* · ε RESULT: 0*1(0 + 10*1)* READ IT BACK: reach B for the first time with 0*1 (any zeros, then a one), then stay in B by either reading 0 or by going out to A and back with 10*1. THE EXPRESSION IS THE LANGUAGE OF BINARY STRINGS WITH AN ODD NUMBER OF 1s, which is what this machine recognises — B is entered on each odd 1.

── THE COMPLETE CONVERSION CYCLE ─────────────────────────── REGULAR EXPRESSION │ Thompson's construction (linear, easy) ▼ ε-NFA │ ε-closure removal ▼ NFA │ SUBSET CONSTRUCTION (may be exponential) ▼ DFA │ MINIMIZATION (O(n log n)) ▼ MINIMAL DFA ─────────────────────────┐ │ │ │ STATE ELIMINATION │ UNIQUE canonical ▼ │ form REGULAR EXPRESSION ◀────────────────┘ EVERY ARROW IS AN ALGORITHM. One can start anywhere and reach anywhere, which is the practical content of the equivalence. NOTE THE ASYMMETRY IN COST: RE → NFA is LINEAR and cheap. NFA → DFA may be EXPONENTIAL. DFA → RE can produce an expression EXPONENTIALLY LARGER than the machine. SO THE REPRESENTATIONS ARE EQUIVALENT IN POWER BUT NOT IN SIZE, and choosing the right one for a task is a real engineering decision rather than a matter of taste. ── WHAT THE THEOREM BUYS ─────────────────────────────────── 1. FREEDOM OF PROOF TECHNIQUE. To prove a property of regular languages, use whichever representation makes it easiest: · CLOSURE UNDER UNION, CONCATENATION AND STAR — trivial with regular expressions, since those ARE the operators. · CLOSURE UNDER COMPLEMENT — trivial with a DFA (swap accepting and non-accepting states), and awkward with a regular expression, which has no complement operator. · CLOSURE UNDER INTERSECTION — the product construction on two DFAs, or De Morgan from complement and union. THE ABILITY TO SWITCH IS NOT A CONVENIENCE — SOME OF THESE PROOFS ARE ESSENTIALLY IMPOSSIBLE IN THE WRONG REPRESENTATION. 2. DECISION PROCEDURES. Because every regular expression can be turned into a minimal DFA, these questions are all DECIDABLE: · MEMBERSHIP: does w ∈ L? Run the DFA. O(|w|). · EMPTINESS: is L = ∅? Is any accepting state reachable? · FINITENESS: is L finite? Is there a cycle on a path from start to an accepting state? · EQUIVALENCE: is L₁ = L₂? Minimize both and compare. · CONTAINMENT: is L₁ ⊆ L₂? Check L₁ ∩ ¬L₂ = ∅. CONTRAST WITH LATER SECTIONS: equivalence of context-free grammars is UNDECIDABLE, and almost every non-trivial question about Turing machines is undecidable. THE DECIDABILITY OF EVERYTHING HERE IS THE REWARD FOR THE MODEL'S WEAKNESS. 3. PRACTICAL COMPILATION. This is the pipeline inside every lexical analyser generator such as lex or flex: the user writes regular expressions for tokens, the tool builds an NFA per token, merges them, determinises, minimises, and emits a DFA table. THE ENTIRE THEORY IS EXECUTED, IN ORDER, EVERY TIME SUCH A TOOL RUNS. ── THE FOUR-WAY EQUIVALENCE RESTATED ─────────────────────── Collecting the results of this section, the following are all the same class of languages: REGULAR EXPRESSIONS DETERMINISTIC FINITE AUTOMATA NON-DETERMINISTIC FINITE AUTOMATA (with or without ε) REGULAR (right-linear) GRAMMARS FOUR FORMALISMS ARRIVED AT FROM FOUR DIFFERENT MOTIVATIONS — algebra, deterministic machines, non-deterministic machines and generative grammar — DEFINING EXACTLY ONE CLASS. When independent definitions converge like this, the class being defined is a real mathematical object rather than an artefact of notation, and it is the same style of evidence that later supports the Church-Turing thesis for computability itself.