A REGULAR EXPRESSION IS A PATTERN THAT DESCRIBES A SET OF STRINGS. The definition is INDUCTIVE — three base cases and three constructors, and nothing else. ── THE BASE CASES ────────────────────────────────────────── ∅ denotes the EMPTY LANGUAGE { }, containing no strings at all ε denotes the language { ε }, containing exactly ONE string: the empty string a for each a ∈ Σ, denotes { a } NOTE THE DISTINCTION between ∅ and ε, which is a standard confusion: ∅ CONTAINS NOTHING; { ε } CONTAINS ONE THING that happens to have length zero. An empty box and a box containing an empty bag are different. ── THE OPERATORS, in increasing precedence ───────────────── UNION r + s (or r | s) L(r) ∪ L(s) CONCATENATION r s { xy : x ∈ L(r), y ∈ L(s) } KLEENE STAR r* zero or more copies of r concatenated PRECEDENCE: STAR binds tightest, then CONCATENATION, then UNION. So ab* + c means (a(b*)) + c and not a(b*+c) or (ab)*+c. Parentheses override this. KLEENE STAR ALWAYS INCLUDES ε, since "zero copies" is permitted: L(r*) = {ε} ∪ L(r) ∪ L(rr) ∪ … THE POSITIVE CLOSURE r⁺ = rr* means ONE or more, excluding ε unless ε ∈ L(r). ── THE ALGEBRAIC IDENTITIES ──────────────────────────────── These are used constantly in simplification questions: r + s = s + r union is COMMUTATIVE (r + s) + t = r + (s + t) union is associative r + r = r union is IDEMPOTENT r + ∅ = r ∅ is the union identity (rs)t = r(st) concatenation associative εr = rε = r ε is the concatenation identity ∅r = r∅ = ∅ ∅ ANNIHILATES r(s + t) = rs + rt distributive (s + t)r = sr + tr (r*)* = r* star is IDEMPOTENT ε* = ∅* = ε r* = ε + rr* = ε + r*r (r + ε)* = r* (r*s*)* = (r + s)* r*r* = r* NOTE THAT CONCATENATION IS **NOT** COMMUTATIVE: rs ≠ sr in general, since "ab" and "ba" are different strings. This is the identity students most often assume by mistake. ── WORKED EXAMPLES OF DESCRIPTION ────────────────────────── Over Σ = {a, b}: (a + b)* all strings, including ε (a + b)*abb all strings ENDING in "abb" a*b* any a's followed by any b's — NOTE this is NOT "equal numbers", which is not regular at all (a + b)*a(a + b)* strings containing at least one a (aa + ab + ba + bb)* strings of EVEN LENGTH b*(ab*ab*)* strings with an EVEN NUMBER of a's (a + b)*aa(a + b)* containing "aa" as a substring a(a + b)*b starting with a and ending with b (b + ab)*(a + ε) strings with no two consecutive a's THE TECHNIQUE FOR CONSTRUCTING ONE: describe the string as a SEQUENCE OF PHASES, then write each phase. "Even number of a's" becomes "some b's, then repeatedly (an a, some b's, another a, some b's)" — which is exactly b*(ab*ab*)*.

── FROM THEORY TO PRACTICE ───────────────────────────────── Real regex syntax adds shorthand that changes NOTHING about the expressive power — every construct below is definable from the three operators: . any single character r? zero or one = (r + ε) r+ one or more = rr* r{m,n} between m and n copies — a finite expansion [abc] a character class = (a + b + c) [a-z] a range [^abc] negated class ^ $ anchors to start / end of line \d \w \s digit, word character, whitespace THE CRITICAL EXCEPTION — BACKREFERENCES: \1 matches whatever the first capture group matched, so (a*)b\1 requires the same number of a's before and after the b. BACKREFERENCES ARE **NOT** REGULAR. They allow matching languages no finite automaton can recognise, which is why "regular expressions" in most programming languages are strictly more powerful than the theoretical object — and why they can no longer be compiled to a DFA, which is what makes them vulnerable to catastrophic backtracking. IN AN EXAM, "REGULAR EXPRESSION" MEANS THE THEORETICAL OBJECT: three operators and nothing else. ── WHAT REGULAR EXPRESSIONS CANNOT DESCRIBE ──────────────── Exactly what finite automata cannot recognise, since the two are equivalent: · { aⁿbⁿ } — matched counts · balanced or nested parentheses · palindromes · { ww : w ∈ Σ* } — a string repeated · strings of prime length THE PRACTICAL CONSEQUENCE, and it is a genuinely useful thing to know: HTML AND OTHER NESTED STRUCTURES CANNOT BE PARSED WITH REGULAR EXPRESSIONS. Nesting requires unbounded counting of open and closed tags, which is precisely what the model cannot do. A regex can extract a simple flat pattern from HTML; it cannot correctly parse the structure, and attempts to do so fail on inputs that are legal but deeply nested. THE RIGHT TOOL IS A PARSER BASED ON A CONTEXT-FREE GRAMMAR — the subject of the next section. ── SIMPLIFICATION, A COMMON EXAM TASK ────────────────────── Show that (a + b)* = (a*b*)*: ⊇ : every string of a*b* is over {a,b}, so (a*b*)* ⊆ (a+b)* ⊆ : any string over {a,b} can be written as a sequence of blocks each in a*b*, so (a+b)* ⊆ (a*b*)* Hence equal. Simplify (ε + a)*: (ε + a)* = a* since adding ε to the union changes nothing under star Simplify a*(ε + a): a*(ε + a) = a*ε + a*a = a* + a⁺ = a* since a⁺ ⊆ a* THE GENERAL METHOD: convert both sides to the SET OF STRINGS they denote and argue mutual containment. Symbol-pushing with the identities is faster when it works, but the set argument always works. ── THE FOUR EQUIVALENT DESCRIPTIONS ──────────────────────── A language is REGULAR if and only if it is described by ANY of these, and the equivalences are all constructive: REGULAR EXPRESSION DETERMINISTIC FINITE AUTOMATON NON-DETERMINISTIC FINITE AUTOMATON REGULAR GRAMMAR (right-linear: A → aB or A → a) THE CONVERGENCE OF FOUR INDEPENDENTLY MOTIVATED DEFINITIONS — an algebraic notation, two machine models and a grammar — ON EXACTLY THE SAME CLASS IS THE STRONGEST EVIDENCE THAT THE CLASS IS NATURAL rather than an artefact of how it was defined. This is the same kind of argument that later supports the Church-Turing thesis, and it is worth recognising the pattern. ── CLOSURE PROPERTIES ────────────────────────────────────── The regular languages are CLOSED under: union, concatenation, Kleene star (immediate from the definition) COMPLEMENT (swap accepting states of a DFA) INTERSECTION (by De Morgan: L₁ ∩ L₂ = ¬(¬L₁ ∪ ¬L₂), or directly by the PRODUCT CONSTRUCTION) difference, reversal, homomorphism CLOSURE UNDER COMPLEMENT AND INTERSECTION IS PROVED MOST EASILY ON DFAs, WHILE UNION AND STAR ARE EASIEST ON NFAs — which is exactly the freedom the equivalence theorem of the previous topic grants.