Regular Expressions

Math for CS · Axiom Academy

From formal theory to practical pattern matching A regular expression (regex) is a concise notation for describing regular languages. Every regex defines a language, and every regular language can be described by a regex. — the empty language (matches nothing) — the language (matches only the empty string) a for each — the language (matches the single symbol a ) Operations (if R and S are regexes): Union: (or ) — strings matching R or S Concatenation: (or RS ) — a string from R followed by a string from S Kleene star: R^* — zero or more repetitions of strings from R Precedence: Star binds tightest, then concatenation, then union. So means . The fundamental theorem connecting regex and automata: This means three equivalent characterizations of regular languages: Described by a regular expression Regex → NFA (Thompson's Construction) Build an NFA inductively from the regex structure: Base a : Two states with a single transition on a Union : New start state with -transitions to the NFAs for R and S Concatenation RS : Connect the accept state of R 's NFA to the start state of S 's NFA via Star R^* : Add -transition from accept back to start, plus a bypass -transition for the zero-repetition case NFA → Regex (State Elimination) Systematically remove states from the NFA, replacing transitions with regex labels that capture all paths through the eliminated state. When only start and accept states remain, the label on the transition between them is the regex.

This is the written version of the interactive lesson above. See the full Math for CS course.