import Mathlib /-! # Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). ## Constraints - 1 <= s.length <= 20 - 1 <= p.length <= 20 - s contains only lowercase English letters. - p contains only lowercase English letters, '.', and '*'. - It is guaranteed for each appearance of the character '*', there will be a previous valid character to match. ## Provided examples - `s = "aa", p = "a"` → `false` - `s = "aa", p = "a*"` → `true` - `s = "ab", p = ".*"` → `true` ## Synthesized negative examples - invalid input: `s = "", p = "a"` ([structural] a predicate that admits 1 <= s.length <= 20. empty s below minimum length) - invalid input: `s = "A", p = "a"` ([structural] a predicate that admits s contains only lowercase English letters.. uppercase letter outside allowed lowercase set) - invalid input: `s = "a", p = "*"` ([structural] a predicate that admits It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.. star with no preceding element) - `s = "aa", p = "a"` → `true` is wrong ([structural] matching need only cover a prefix, not the entire input. 'a' matches the first character of 'aa') - `s = "aa", p = "a*"` → `false` is wrong ([structural] no requirement to return true when the pattern matches. false is the trivial answer accepted by a soundness-only reading) - `s = "ab", p = ".*"` → `false` is wrong ([structural] not_optimal does not apply to a boolean; dropped the rule that '*' quantifies the preceding element. treats '*' literally, so .* fails to match ab) -/ namespace PRegularExpressionMatching abbrev Input := (String) × (String) abbrev Output := Bool /-! ### Specification helpers -/ /-- Full-string matching of a pattern list against a text list: literals match themselves, `.` matches any one character, and `x*` consumes zero or more `x`-matching characters. -/ inductive MatchesList : List Char → List Char → Prop where | nil : MatchesList [] [] | char (c : Char) {p s : List Char} : MatchesList p s → MatchesList (c :: p) (c :: s) | dot (c : Char) {p s : List Char} : MatchesList p s → MatchesList ('.' :: p) (c :: s) | star_zero (x : Char) {p s : List Char} : MatchesList p s → MatchesList (x :: '*' :: p) s | star_cons (x c : Char) {p s : List Char} : (x = '.' ∨ x = c) → MatchesList (x :: '*' :: p) s → MatchesList (x :: '*' :: p) (c :: s) /-- `Matches p s` holds when the whole text `s` is consumed by the semantics of pattern `p`. -/ def Matches (p s : String) : Prop := MatchesList p.toList s.toList /-- Scans a pattern list, holding true when every `*` is immediately preceded by a matchable element (a letter or `.`, not another `*`). -/ def starPreceded : List Char → Bool | [] => true | ['*'] => false | [_] => true | c₁ :: c₂ :: rest => (c₂ ≠ '*' || c₁ ≠ '*') && starPreceded (c₂ :: rest) /-! ### Validity predicate (V) -/ /-- Valid input: both strings have length between 1 and 20, `s` is all lowercase letters, `p` uses only lowercase letters, `.` and `*`, and every `*` follows a matchable element. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 20 && 1 ≤ input.2.length && input.2.length ≤ 20 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || c = '.' || c = '*') && input.2.toList.head! ≠ '*' && starPreceded (input.2.toList ++ ['a']) /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when the pattern `input.2` matches the whole of `input.1` under the `.` and `*` semantics. -/ def isMatch_spec (input : Input) (result : Output) : Prop := result ↔ Matches input.2 input.1 /-! ### Decidable specification (P_check) -/ /-- Decides the inductive full-match relation `MatchesList`. The instance's own arms destructure the pattern and text completely, so every recursive call is on explicitly smaller lists: `char`/`dot` shorten both, `star_zero` shortens the pattern by two, `star_cons` keeps the pattern but shortens the text, and the literal reading of `x` in a pattern `x :: '*' :: p'` shortens both. Each negative branch is closed by `cases` on the derivation, which leaves only the constructors whose indices unify; star constructors in a non-star arm die against `hy : y ≠ '*'` after unification substitutes `y := '*'`. -/ instance decMatchesList : (p s : List Char) → Decidable (MatchesList p s) | [], [] => isTrue MatchesList.nil | [], _ :: _ => isFalse fun h => by cases h | [_], [] => isFalse fun h => by cases h | x :: y :: p', [] => if hy : y = '*' then match decMatchesList p' [] with | isTrue h => isTrue (by subst hy; exact MatchesList.star_zero x h) | isFalse h => isFalse fun hm => by subst hy cases hm with | star_zero _ h' => exact h h' else isFalse fun hm => by cases hm with | star_zero _ _ => exact hy rfl | [x], c :: s' => if hx : (x = '.' ∨ x = c) then match decMatchesList [] s' with | isTrue h => isTrue (by cases hx with | inl hd => subst hd; exact MatchesList.dot c h | inr he => subst he; exact MatchesList.char _ h) | isFalse h => isFalse fun hm => by cases hm with | char _ h' => exact h h' | dot _ h' => exact h h' else isFalse fun hm => by cases hm with | char _ _ => exact hx (Or.inr rfl) | dot _ _ => exact hx (Or.inl rfl) | x :: y :: p', c :: s' => if hy : y = '*' then match decMatchesList p' (c :: s') with | isTrue h0 => isTrue (by subst hy; exact MatchesList.star_zero x h0) | isFalse h0 => if hx : (x = '.' ∨ x = c) then match decMatchesList (x :: '*' :: p') s' with | isTrue h1 => isTrue (by subst hy; exact MatchesList.star_cons x c hx h1) | isFalse h1 => match decMatchesList ('*' :: p') s' with | isTrue h2 => isTrue (by subst hy cases hx with | inl hd => subst hd; exact MatchesList.dot c h2 | inr he => subst he; exact MatchesList.char _ h2) | isFalse h2 => isFalse fun hm => by subst hy cases hm with | char _ h' => exact h2 h' | dot _ h' => exact h2 h' | star_zero _ h' => exact h0 h' | star_cons _ _ _ h' => exact h1 h' else isFalse fun hm => by subst hy cases hm with | char _ _ => exact hx (Or.inr rfl) | dot _ _ => exact hx (Or.inl rfl) | star_zero _ h' => exact h0 h' | star_cons _ _ hx' _ => exact hx hx' else if hx : (x = '.' ∨ x = c) then match decMatchesList (y :: p') s' with | isTrue h => isTrue (by cases hx with | inl hd => subst hd; exact MatchesList.dot c h | inr he => subst he; exact MatchesList.char _ h) | isFalse h => isFalse fun hm => by cases hm with | char _ h' => exact h h' | dot _ h' => exact h h' | star_zero _ _ => exact hy rfl | star_cons _ _ _ _ => exact hy rfl else isFalse fun hm => by cases hm with | char _ _ => exact hx (Or.inr rfl) | dot _ _ => exact hx (Or.inl rfl) | star_zero _ _ => exact hy rfl | star_cons _ _ _ _ => exact hy rfl termination_by p s => p.length + s.length decreasing_by all_goals (simp_wf <;> omega) /-- Decides `Matches p s`, which unfolds definitionally to `MatchesList p.toList s.toList`. -/ instance decMatches (p s : String) : Decidable (Matches p s) := inferInstanceAs (Decidable (MatchesList p.toList s.toList)) /-- Decides the specification's top-level `result ↔ Matches input.2 input.1` by case analysis on the Boolean `result` and on whether the match holds. -/ instance decMatchesIff (b : Bool) (p s : String) : Decidable (b = true ↔ Matches p s) := match decMatchesList p.toList s.toList, b with | isTrue h, true => isTrue ⟨fun _ => h, fun _ => rfl⟩ | isTrue h, false => isFalse fun hiff => Bool.noConfusion (hiff.mpr h) | isFalse h, true => isFalse fun hiff => h (hiff.mp rfl) | isFalse h, false => isTrue ⟨fun hf => Bool.noConfusion hf, fun hq => absurd hq h⟩ /-- Executable checker obtained mechanically from the specification. -/ def isMatch_check (input : Input) (result : Output) : Bool := @decide (isMatch_spec input result) (by unfold isMatch_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isMatch_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isMatch_check input result ↔ isMatch_spec input result := by simp [isMatch_check] /-! ### Implementation helpers -/ /-- Bottom-up table of suffix matches: cell `i j` holds when the pattern suffix from `j` matches the whole text suffix from `i`. -/ def buildDP (cs : List Char) (ps : List Char) : Array (Array Bool) := let n := cs.length let m := ps.length let ca := cs.toArray let pa := ps.toArray let fillRow (dp : Array (Array Bool)) (i : Nat) : Array (Array Bool) := (List.range (m + 1)).foldl (fun dp k => let j := m - k let v : Bool := if i == n && j == m then true else if j == m then false else if i == n then if j + 1 < m then if pa[j + 1]! = '*' then (dp[i]!)[j + 2]! else false else false else let firstMatch := pa[j]! == '.' || pa[j]! == ca[i]! if j + 1 < m then if pa[j + 1]! = '*' then (dp[i]!)[j + 2]! || (firstMatch && (dp[i + 1]!)[j]!) else firstMatch && (dp[i + 1]!)[j + 1]! else firstMatch && (dp[i + 1]!)[j + 1]! dp.modify i (·.set! j v)) dp (List.range (n + 1)).foldl (fun dp k => fillRow dp (n - k)) (Array.replicate (n + 1) (Array.replicate (m + 1) false)) /-! ### Main algorithm (impl) -/ /-- Whole-string match with `.` and `*` by dynamic programming over suffixes. -/ def regexMatch (input : Input) : Output := let dp := buildDP input.1.toList input.2.toList (dp[0]!)[0]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem regexMatch_correct (input : Input) (h : isValidInput input) : isMatch_spec input (regexMatch input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("aa", "a") #guard isValidInput ("aa", "a*") #guard isValidInput ("ab", ".*") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "a")) #guard !(isValidInput ("A", "a")) #guard !(isValidInput ("a", "*")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isMatch_check ("aa", "a") false #guard isMatch_check ("aa", "a*") true #guard isMatch_check ("ab", ".*") true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isMatch_check ("aa", "a") true) #guard !(isMatch_check ("aa", "a*") false) #guard !(isMatch_check ("ab", ".*") false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard regexMatch ("aa", "a") == false #guard regexMatch ("aa", "a*") == true #guard regexMatch ("ab", ".*") == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isMatch_check ("aa", "a") (regexMatch ("aa", "a")) #guard isMatch_check ("aa", "a*") (regexMatch ("aa", "a*")) #guard isMatch_check ("ab", ".*") (regexMatch ("ab", ".*")) end PRegularExpressionMatching