Theoretical Automata & Regular Language Mathematics
Regular expressions correspond to Chomsky Type-3 Formal Grammars, evaluated via Non-Deterministic Finite Automata (NFA) converted to Deterministic Finite Automata (DFA) in $O(N)$ string matching complexity.
1. Kleene Star (*) & Plus (+) Algebraic Closures
L(R*)=⋃_i=0^∞ L(R)^i
andL(R⁺)=⋃_i=1^∞ L(R)^i
2. Finite State Transition Invariant
δ(q, c) ⊆ Qwhereq ∈ States, c ∈ Alphabet Σ
Step-by-Step Pattern Dissection (Email Validation)
Step 1: Local Part Validation
[a-zA-Z0-9._%+-]+: Matches 1 or more alphanumeric characters, dots, pluses, or hyphens before the '@'.Step 2: Domain Host & Top-Level Domain (TLD)
@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}: Matches domain hostname followed by an escaped dot and a TLD of minimum length 2.Step 3: Engine Execution & Capture Offsets
Match Status=Global match identified at indices [8, 30] and [34, 58]
Essential Metacharacters & Quantifiers Reference
| Token | Category | Function / Meaning | Example Match |
|---|---|---|---|
| . | Wildcard | Any single character except newline | c.t → cat, cot, c9t |
| \d / \D | Character Class | Digit [0-9] / Non-digit | \d{3} → 123 |
| \w / \W | Character Class | Word character [a-zA-Z0-9_] / Non-word | \w+ → user_name |
| ^ / $ | Anchor | Start of string/line / End of string/line | ^Start.*End$ |
| (?:...) | Grouping | Non-capturing group (optimizes memory) | (?:https|http) |