Theory TIGER_Lexer.TIGER_Regex

(* Author: Basil Fürer *)

theory TIGER_Regex
  imports "Regular-Sets.Derivatives"
begin

section ‹Symbolic regular expressions›

text ‹A symbolic regular expression is a typ‹'p rexp› of session‹Regular-Sets› whose
  atoms are syntactic predicates. A denotation ‹sem :: 'p ⇒ 'ch ⇒ bool› says which
  characters a predicate holds for cite‹‹Sect.~2› in
  "dantoni2014-minimization-symbolic-automata"›. We reuse the datatype rather than copy it
  (its const‹nullable›, const‹atoms› and partial derivatives then apply unchanged).

  Predicates are syntax, not functions (the generator compares regexes and decides
  satisfiability of predicates, and functions allow neither). The locale ‹symbolic› fixes
  ‹sem›, and ‹'ch› carries no type class. Definitions that need no denotation stay
  outside it.

  The language const‹lang› reads an atom as the characters its denotation holds for.

  This theory defines the derivative cite‹"brzozowski1964-derivatives-regular-expressions"›,
  the partial derivative cite‹"antimirov1996-partial-derivatives"› by a character and by a
  predicate class, proves both language-correct and proves that the partial derivatives
  of a regex are finitely many.›

abbreviation Pred :: ‹'p ⇒ 'p rexp› where
  ‹Pred ≡ Atom›

locale symbolic =
  fixes sem :: ‹'p ⇒ 'ch ⇒ bool›
begin

primrec lang :: ‹'p rexp ⇒ 'ch lang› where
  ‹lang Zero = {}›
| ‹lang One = {[]}›
| ‹lang (Pred p) = {[c] | c. sem p c}›
| ‹lang (Plus r s) = lang r ∪ lang s›
| ‹lang (Times r s) = lang r @@ lang s›
| ‹lang (Star r) = star (lang r)›

text ‹const‹Regular_Exp.lang› would read term‹Pred p› as the one-letter word ‹[p]›
  over the alphabet of predicates. const‹lang› is the symbolic reading.›

lemma nullable_iff: ‹nullable r ⟷ [] ∈ lang r›
  by (induct r) (auto simp: conc_def)

subsection ‹Derivative›

primrec deriv :: ‹'ch ⇒ 'p rexp ⇒ 'p rexp› where
  ‹deriv c Zero = Zero›
| ‹deriv c One = Zero›
| ‹deriv c (Pred p) = (if sem p c then One else Zero)›
| ‹deriv c (Plus r s) = Plus (deriv c r) (deriv c s)›
| ‹deriv c (Times r s) =
    (if nullable r then Plus (Times (deriv c r) s) (deriv c s)
     else Times (deriv c r) s)›
| ‹deriv c (Star r) = Times (deriv c r) (Star r)›

text ‹The derivative of ‹r› by ‹c› denotes the words ‹w› with ‹c # w ∈ lang r›
  cite‹‹Thm.~3.1› in "brzozowski1964-derivatives-regular-expressions"›:›

lemma Deriv_Pred[simp]: ‹Deriv c {[d] | d. P d} = (if P c then {[]} else {})›
  by (auto simp: Deriv_def)

lemma lang_deriv: ‹lang (deriv c r) = Deriv c (lang r)›
  by (induct r) (simp_all add: nullable_iff)

subsection ‹Partial derivatives›

primrec pderiv :: ‹'ch ⇒ 'p rexp ⇒ 'p rexp set› where
  ‹pderiv c Zero = {}›
| ‹pderiv c One = {}›
| ‹pderiv c (Pred p) = (if sem p c then {One} else {})›
| ‹pderiv c (Plus r s) = pderiv c r ∪ pderiv c s›
| ‹pderiv c (Times r s) =
    (if nullable r then Timess (pderiv c r) s ∪ pderiv c s
     else Timess (pderiv c r) s)›
| ‹pderiv c (Star r) = Timess (pderiv c r) (Star r)›

primrec pderivs :: ‹'ch list ⇒ 'p rexp ⇒ 'p rexp set› where
  ‹pderivs [] r = {r}›
| ‹pderivs (c # w) r = ⋃ (pderivs w ` pderiv c r)›

text ‹The partial derivatives of ‹r› by ‹c› are a set of regexes whose union denotes
  the derivative cite‹‹Def.~2.8, Prop.~2.10› in "antimirov1996-partial-derivatives"›.
  The proofs follow session‹Regular-Sets› (‹Derivatives›, @{thm [source]
  Derivatives.Deriv_pderiv} and @{thm [source] Derivatives.Derivs_pderivs}):›

lemma Deriv_pderiv: ‹Deriv c (lang r) = ⋃ (lang ` pderiv c r)›
  by (induct r) (auto simp: nullable_iff conc_UNION_distrib)

lemma Derivs_pderivs: ‹Derivs w (lang r) = ⋃ (lang ` pderivs w r)›
proof (induct w arbitrary: r)
  case (Cons c w)
  have ‹Derivs w (⋃ (lang ` pderiv c r)) =
    (⋃r' ∈ pderiv c r. Derivs w (lang r'))›
    by (auto simp: Derivs_def)
  then show ?case
    by (simp add: Deriv_pderiv Cons)
qed simp

end

subsection ‹Partial derivatives by a predicate class›

text ‹A class is a set ‹S› of predicates, read as the characters for which exactly the
  predicates in ‹S› hold (so it needs no denotation). The partial derivative by a class
  treats every atom in ‹S› as true cite‹‹Sect.~5.2, Thm.~12› in "keil2014-symbolic-regex-inequalities"›:›

primrec pderiv_cls :: ‹'p set ⇒ 'p rexp ⇒ 'p rexp set› where
  ‹pderiv_cls S Zero = {}›
| ‹pderiv_cls S One = {}›
| ‹pderiv_cls S (Pred p) = (if p ∈ S then {One} else {})›
| ‹pderiv_cls S (Plus r s) = pderiv_cls S r ∪ pderiv_cls S s›
| ‹pderiv_cls S (Times r s) =
    (if nullable r then Timess (pderiv_cls S r) s ∪ pderiv_cls S s
     else Timess (pderiv_cls S r) s)›
| ‹pderiv_cls S (Star r) = Timess (pderiv_cls S r) (Star r)›

primrec pderivs_cls :: ‹'p set list ⇒ 'p rexp ⇒ 'p rexp set› where
  ‹pderivs_cls [] r = {r}›
| ‹pderivs_cls (S # Ss) r = ⋃ (pderivs_cls Ss ` pderiv_cls S r)›

text ‹The partial derivative by a class is a union of session‹Regular-Sets› partial
  derivatives over the alphabet of predicates. This lifting lemma is the bridge to its
  finiteness theorem:›

lemma pderiv_cls_eq_UN: ‹pderiv_cls S r = (⋃p ∈ S. Derivatives.pderiv p r)›
  by (induct r) auto

lemma pderiv_empty_if_notin_atoms: ‹p ∉ atoms r ⟹ Derivatives.pderiv p r = {}›
  by (induct r) simp_all

lemma atoms_if_pderiv: ‹x ∈ Derivatives.pderiv p r ⟹ p ∈ atoms r›
  by (metis empty_iff pderiv_empty_if_notin_atoms)

lemma pderiv_cls_Int_atoms: ‹pderiv_cls (S ∩ atoms r) r = pderiv_cls S r›
  unfolding pderiv_cls_eq_UN by (auto dest: atoms_if_pderiv)

context symbolic
begin

definition sig :: ‹'p rexp ⇒ 'ch ⇒ 'p set› where
  ‹sig r c = {p ∈ atoms r. sem p c}›

text ‹The signature of ‹c› in ‹r› is the set of atoms of ‹r› that hold for ‹c›:›

lemma pderiv_eq_pderiv_cls: ‹pderiv c r = pderiv_cls {p. sem p c} r›
  by (induct r) simp_all

text ‹Characters with the same signature have the same partial derivatives
  cite‹‹Thm.~4.2› in "owens2009-regex-derivatives-reexamined"›, so the partial
  derivative by a class is the partial derivative by any of its characters:›

lemma pderiv_eq_pderiv_cls_sig: ‹pderiv c r = pderiv_cls (sig r c) r›
proof -
  have ‹sig r c = {p. sem p c} ∩ atoms r›
    by (auto simp: sig_def)
  then show ?thesis
    by (simp add: pderiv_eq_pderiv_cls pderiv_cls_Int_atoms)
qed

lemma pderiv_eq_if_sig_eq: ‹sig r c = sig r d ⟹ pderiv c r = pderiv d r›
  by (simp add: pderiv_eq_pderiv_cls_sig)

lemma Deriv_pderiv_cls:
  ‹sig r c = S ∩ atoms r ⟹ Deriv c (lang r) = ⋃ (lang ` pderiv_cls S r)›
  by (simp add: Deriv_pderiv pderiv_eq_pderiv_cls_sig pderiv_cls_Int_atoms)

lemma pderivs_eq_pderivs_cls: ‹pderivs w r = pderivs_cls (map (λc. {p. sem p c}) w) r›
  by (induct w arbitrary: r) (simp_all add: pderiv_eq_pderiv_cls)

end

subsection ‹Finiteness›

definition pderiv_closure :: ‹'p rexp ⇒ 'p rexp set› where
  ‹pderiv_closure r = (⋃Ss. pderivs_cls Ss r)›

text ‹The closure of ‹r› under partial derivatives by classes contains the partial
  derivatives by all words. It is a subset of the session‹Regular-Sets› partial
  derivatives of ‹r› over the alphabet of predicates, so @{thm [source]
  finite_pderivs_lang} and @{thm [source] card_pderivs_lang_UNIV_le_awidth} apply
  unchanged and no proof is copied cite‹‹Thm.~3.4› in "antimirov1996-partial-derivatives"›:›

lemma pderivs_cls_subset_pderivs_lang: ‹pderivs_cls Ss r ⊆ pderivs_lang UNIV r›
proof (induct Ss arbitrary: r)
  case (Cons S Ss)
  show ?case
  proof
    fix x
    assume ‹x ∈ pderivs_cls (S # Ss) r›
    then obtain p r' where ‹r' ∈ Derivatives.pderiv p r› ‹x ∈ pderivs_cls Ss r'›
      by (auto simp: pderiv_cls_eq_UN)
    with Cons obtain u where ‹r' ∈ Derivatives.pderiv p r› ‹x ∈ Derivatives.pderivs u r'›
      by (auto simp: pderivs_lang_def)
    then have ‹x ∈ Derivatives.pderivs (p # u) r›
      by auto
    then show ‹x ∈ pderivs_lang UNIV r›
      unfolding pderivs_lang_def by blast
  qed
qed (simp add: pderivs_lang_UNIV)

lemma pderiv_closure_subset_pderivs_lang: ‹pderiv_closure r ⊆ pderivs_lang UNIV r›
  using pderivs_cls_subset_pderivs_lang by (fastforce simp: pderiv_closure_def)

lemma finite_pderiv_closure: ‹finite (pderiv_closure r)›
  using pderiv_closure_subset_pderivs_lang finite_pderivs_lang by (rule finite_subset)

lemma card_pderiv_closure_le_awidth: ‹card (pderiv_closure r) ≤ awidth r + 1›
  using card_mono[OF finite_pderivs_lang pderiv_closure_subset_pderivs_lang]
    card_pderivs_lang_UNIV_le_awidth by (rule le_trans)

context symbolic
begin

lemma pderivs_subset_pderiv_closure: ‹pderivs w r ⊆ pderiv_closure r›
  by (auto simp: pderiv_closure_def pderivs_eq_pderivs_cls)

lemma finite_pderivs_UNIV: ‹finite (⋃w. pderivs w r)›
  by (rule finite_subset[OF UN_least finite_pderiv_closure]) (rule pderivs_subset_pderiv_closure)

end

end