Theory TIGER_Gen

(* Author: Basil Fürer *)

theory TIGER_Gen
  imports TIGER_Spec TIGER_Pred_Algebra "HOL-Library.While_Combinator"
begin

section ‹The DFA of a mode›

text ‹One DFA per mode reads all rules of the mode at once (regular vectors
  cite‹‹Sect.~6› in "brzozowski1964-derivatives-regular-expressions"›
  cite‹‹Sect.~4.3› in "owens2009-regex-derivatives-reexamined"›). Verbatim++
  builds one DFA per rule and names one DFA for all rules as future work
  cite‹‹Sect.~8.2› in "egolf2022-verbatim-plus-plus"›. A state is a
  finite set of pairs of a rule index and a partial derivative. It is the subset
  construction over partial derivatives cite‹‹Prop.~4.3› in
  "antimirov1996-partial-derivatives"›, tagged with rule indices. Transitions are indexed
  by the minterms of the mode's atoms cite‹‹Fig.~2› in
  "dantoni2014-minimization-symbolic-automata"›, and a state accepts with the least index
  of a nullable pair cite‹‹Sect.~7› in "paxson2026-flex-manual"›.

  The states are explored by a worklist over const‹while_option›, as in the closure of
  session‹Regular-Sets› (‹Equivalence_Checking›), generalized to a list of states
  numbered in the order of discovery. This is the ‹explore›/‹goto› construction of
  Owens et al. cite‹‹Sect.~3.3, Fig.~1› in "owens2009-regex-derivatives-reexamined"›,
  with minterms as letters where their Fig.~3 uses approximate derivative classes. Owens et
  al. traverse depth first and identify equivalent regexes; here the traversal is breadth
  first and states are equal only as sets of tagged partial derivatives. Exploration is
  total, since every reachable state is a set of pairs from a finite closure of the rules
  under partial derivatives
  (@{thm [source] finite_pderiv_closure}). Verbatim++ also explores by derivatives and
  makes no recursive call at a derivative that is already a row label
  cite‹‹Sect.~3, Def.~3.1› in "egolf2022-verbatim-plus-plus"›, but its exploration is bounded by
  fuel. Its table may stay partial, and missing entries are computed by derivatives at
  run time, so its Thm.~3.9, that the DFA accepts the language of the regex, does not
  depend on the fuel. Here the table is complete.

  We prove that exploration terminates, that a transition by a minterm is the step by any
  of its characters, that the generated tables follow these steps, and that the accepting
  rule of a word is the least rule whose language contains it. Nothing here is trusted:
  every lemma relates the generator output to const‹symbolic.lang›.›

subsection ‹Exploration by worklist›

text ‹The states reachable from ‹x› by a transition function ‹f› over the letters
  ‹as›:›

definition reach :: ‹('s ⇒ 'a ⇒ 's) ⇒ 'a list ⇒ 's ⇒ 's set› where
  ‹reach f as x = {foldl f x w | w. set w ⊆ set as}›

lemma start_in_reach: ‹x ∈ reach f as x›
  by (auto simp: reach_def intro: exI[of _ ‹[]›])

lemma step_in_reach:
  assumes ‹y ∈ reach f as x› ‹a ∈ set as›
  shows ‹f y a ∈ reach f as x›
proof -
  from assms(1) obtain w where ‹y = foldl f x w› ‹set w ⊆ set as›
    by (auto simp: reach_def)
  with assms(2) show ?thesis
    by (auto simp: reach_def intro!: exI[of _ ‹w @ [a]›])
qed

lemma reach_subset:
  assumes ‹x ∈ A› ‹⋀y a. ⟦ y ∈ A; a ∈ set as ⟧ ⟹ f y a ∈ A›
  shows ‹reach f as x ⊆ A›
proof -
  have ‹⟦ y ∈ A; set w ⊆ set as ⟧ ⟹ foldl f y w ∈ A› for y w
    using assms(2) by (induct w arbitrary: y) auto
  with assms(1) show ?thesis
    by (auto simp: reach_def)
qed

text ‹A worklist state ‹(Q, n)› holds the states found so far, in the order of
  discovery, of which the first ‹n› are processed. A step processes ‹Q ! n› and appends
  its new successors:›

definition add_new :: ‹'s list ⇒ 's ⇒ 's list› where
  ‹add_new Q y = (if y ∈ set Q then Q else Q @ [y])›

definition explore_step :: ‹('s ⇒ 'a ⇒ 's) ⇒ 'a list ⇒ 's list × nat ⇒ 's list × nat›
  where
  ‹explore_step f as = (λ(Q, n). (foldl add_new Q (map (f (Q ! n)) as), Suc n))›

definition explore :: ‹('s ⇒ 'a ⇒ 's) ⇒ 'a list ⇒ 's ⇒ ('s list × nat) option› where
  ‹explore f as x = while_option (λ(Q, n). n < length Q) (explore_step f as) ([x], 0)›

lemma foldl_add_new_append: ‹∃zs. foldl add_new Q ys = Q @ zs›
proof (induct ys arbitrary: Q)
  case (Cons y ys)
  have ‹add_new Q y = Q @ (if y ∈ set Q then [] else [y])›
    by (simp add: add_new_def)
  moreover obtain zs where ‹foldl add_new (add_new Q y) ys = add_new Q y @ zs›
    using Cons by blast
  ultimately show ?case
    by (metis append_assoc foldl_Cons)
qed simp

lemma set_foldl_add_new: ‹set (foldl add_new Q ys) = set Q ∪ set ys›
  by (induct ys arbitrary: Q) (auto simp: add_new_def)

lemma distinct_foldl_add_new: ‹distinct Q ⟹ distinct (foldl add_new Q ys)›
  by (induct ys arbitrary: Q) (auto simp: add_new_def)

text ‹The invariant of the worklist: the found states are distinct and reachable, the
  start comes first and the successors of the processed states are found:›

definition explore_inv :: ‹('s ⇒ 'a ⇒ 's) ⇒ 'a list ⇒ 's ⇒ 's list × nat ⇒ bool›
  where
  ‹explore_inv f as x = (λ(Q, n). distinct Q ∧ n ≤ length Q ∧ Q ≠ [] ∧ Q ! 0 = x ∧
    set Q ⊆ reach f as x ∧ (∀k < n. ∀a ∈ set as. f (Q ! k) a ∈ set Q))›

lemma explore_inv_start: ‹explore_inv f as x ([x], 0)›
  by (simp add: explore_inv_def start_in_reach)

lemma explore_inv_step:
  assumes ‹explore_inv f as x s› ‹case s of (Q, n) ⇒ n < length Q›
  shows ‹explore_inv f as x (explore_step f as s)›
proof (cases s)
  case (Pair Q n)
  let ?Q' = ‹foldl add_new Q (map (f (Q ! n)) as)›
  obtain zs where Q': ‹?Q' = Q @ zs›
    using foldl_add_new_append by blast
  then have set_zs: ‹set Q ∪ set zs = set Q ∪ f (Q ! n) ` set as›
    using set_foldl_add_new[of Q ‹map (f (Q ! n)) as›] by simp
  from assms Pair have inv: ‹explore_inv f as x (Q, n)› and ‹n < length Q›
    by simp_all
  then have ‹Q ! n ∈ reach f as x›
    by (auto simp: explore_inv_def)
  then have ‹f (Q ! n) ` set as ⊆ reach f as x›
    by (auto intro: step_in_reach)
  with inv set_zs have ‹set (Q @ zs) ⊆ reach f as x›
    by (simp add: explore_inv_def)
  moreover have ‹k < Suc n ⟹ a ∈ set as ⟹ f ((Q @ zs) ! k) a ∈ set (Q @ zs)› for k a
    using inv ‹n < length Q› set_zs by (auto simp: explore_inv_def nth_append less_Suc_eq)
  moreover from inv Q' have ‹distinct (Q @ zs)›
    using distinct_foldl_add_new[of Q ‹map (f (Q ! n)) as›] by (simp add: explore_inv_def)
  moreover from Pair Q' have ‹explore_step f as s = (Q @ zs, Suc n)›
    by (simp add: explore_step_def)
  ultimately show ?thesis
    using inv ‹n < length Q› by (simp add: explore_inv_def nth_append)
qed

text ‹A result of the worklist is the reachable set, closed under the transitions:›

lemma explore_result:
  assumes ‹explore f as x = Some (Q, n)›
  shows ‹n = length Q ∧ distinct Q ∧ Q ≠ [] ∧ Q ! 0 = x ∧ set Q = reach f as x ∧
    (∀q ∈ set Q. ∀a ∈ set as. f q a ∈ set Q)›
proof -
  have ‹explore_inv f as x (Q, n)›
    using explore_inv_step assms[unfolded explore_def] explore_inv_start
    by (rule while_option_rule)
  moreover from assms have ‹¬ n < length Q›
    unfolding explore_def by (auto dest: while_option_stop)
  ultimately have inv: ‹explore_inv f as x (Q, length Q)› and ‹n = length Q›
    by (auto simp: explore_inv_def)
  then have ‹∀k < length Q. ∀a ∈ set as. f (Q ! k) a ∈ set Q›
    by (simp add: explore_inv_def)
  then have closed: ‹∀q ∈ set Q. ∀a ∈ set as. f q a ∈ set Q›
    by (auto simp: in_set_conv_nth[of _ Q])
  with inv have ‹reach f as x ⊆ set Q›
    by (intro reach_subset) (auto simp: explore_inv_def intro: nth_mem)
  with inv closed ‹n = length Q› show ?thesis
    by (auto simp: explore_inv_def)
qed

text ‹The worklist terminates when the reachable set is finite (each step processes one
  more state, and the found states are distinct and reachable):›

lemma explore_Some:
  assumes ‹finite (reach f as x)›
  shows ‹∃Q. explore f as x = Some (Q, length Q)›
proof -
  have ‹∃t. explore f as x = Some t›
    unfolding explore_def
  proof (rule measure_while_option_Some[where P = ‹explore_inv f as x›
        and f = ‹λ(Q, n). card (reach f as x) - n›])
    fix t
    assume inv: ‹explore_inv f as x t› and b: ‹case t of (Q, n) ⇒ n < length Q›
    obtain Q n where t: ‹t = (Q, n)›
      by (cases t) blast
    from inv b have inv': ‹explore_inv f as x (explore_step f as t)›
      by (rule explore_inv_step)
    obtain Q' where step: ‹explore_step f as t = (Q', Suc n)›
      by (simp add: explore_step_def t)
    with inv' have ‹Suc n ≤ length Q'› ‹distinct Q'› ‹set Q' ⊆ reach f as x›
      by (auto simp: explore_inv_def)
    then have ‹Suc n ≤ card (reach f as x)›
      using card_mono[OF assms ‹set Q' ⊆ reach f as x›] distinct_card[OF ‹distinct Q'›]
      by simp
    with inv' step t show ‹explore_inv f as x (explore_step f as t) ∧
      (case explore_step f as t of (Q, n) ⇒ card (reach f as x) - n) <
      (case t of (Q, n) ⇒ card (reach f as x) - n)›
      by simp
  qed (rule explore_inv_start)
  then obtain Q n where ‹explore f as x = Some (Q, n)›
    by auto
  with explore_result[OF this] show ?thesis
    by blast
qed

text ‹The transition table of an explored list of states holds the index of each
  successor:›

primrec index_of :: ‹'s list ⇒ 's ⇒ nat› where
  ‹index_of [] y = 0›
| ‹index_of (z # Q) y = (if z = y then 0 else Suc (index_of Q y))›

lemma index_of_less: ‹y ∈ set Q ⟹ index_of Q y < length Q›
  by (induct Q) auto

lemma nth_index_of: ‹y ∈ set Q ⟹ Q ! index_of Q y = y›
  by (induct Q) auto

definition table :: ‹('s ⇒ 'a ⇒ 's) ⇒ 'a list ⇒ 's list ⇒ nat list list› where
  ‹table f as Q = map (λq. map (λa. index_of Q (f q a)) as) Q›

lemma table_correct:
  assumes ‹∀q ∈ set Q. ∀a ∈ set as. f q a ∈ set Q› ‹k < length Q› ‹j < length as›
  shows ‹table f as Q ! k ! j < length Q ∧ Q ! (table f as Q ! k ! j) = f (Q ! k) (as ! j)›
  using assms by (simp add: table_def index_of_less nth_index_of)

subsection ‹States, transitions and acceptance›

type_synonym 'p state = ‹(nat × 'p rexp) set›

text ‹The initial state pairs every rule with its regex. A transition by the class
  ‹S› takes the partial derivatives of every pair and keeps its rule index:›

definition init_state :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'p state› where
  ‹init_state rs = set (map (λi. (i, match (rs ! i))) [0 ..< length rs])›

definition delta :: ‹'p state ⇒ 'p set ⇒ 'p state› where
  ‹delta X S = (⋃(i, r) ∈ X. {i} × pderiv_cls S r)›

lemma mem_init_state[simp]:
  ‹(i, r) ∈ init_state rs ⟷ i < length rs ∧ r = match (rs ! i)›
  by (auto simp: init_state_def)

text ‹The empty state is dead:›

lemma delta_empty[simp]: ‹delta {} S = {}›
  by (simp add: delta_def)

text ‹A state accepts with the least rule index of a nullable pair
  cite‹‹Fig.~4, FirstToken› in "egolf2021-verbatim-verified-lexer"›:›

definition acc :: ‹'p state ⇒ nat option› where
  ‹acc X = (if ∃i r. (i, r) ∈ X ∧ nullable r
    then Some (LEAST i. ∃r. (i, r) ∈ X ∧ nullable r) else None)›

lemma acc_Some_iff:
  ‹acc X = Some i ⟷
    (∃r. (i, r) ∈ X ∧ nullable r) ∧ (∀j < i. ¬ (∃r. (j, r) ∈ X ∧ nullable r))›
  (is ‹_ ⟷ ?N i ∧ (∀j < i. ¬ ?N j)›)
proof
  assume ‹acc X = Some i›
  then have ‹∃i. ?N i› ‹i = (LEAST i. ?N i)›
    by (auto simp: acc_def split: if_splits)
  then show ‹?N i ∧ (∀j < i. ¬ ?N j)›
    using LeastI_ex[of ?N] not_less_Least[of _ ?N] by blast
next
  assume N: ‹?N i ∧ (∀j < i. ¬ ?N j)›
  have ‹(LEAST i. ?N i) = i›
  proof (rule Least_equality)
    show ‹?N i›
      using N by blast
  next
    fix j
    assume ‹?N j›
    with N show ‹i ≤ j›
      by (meson leI)
  qed
  with N show ‹acc X = Some i›
    by (auto simp: acc_def)
qed

lemma acc_None_iff: ‹acc X = None ⟷ (∀i. ¬ (∃r. (i, r) ∈ X ∧ nullable r))›
  by (auto simp: acc_def)

text ‹On a state given by a list, the least index is a minimum:›

lemma acc_code[code]:
  ‹acc (set xs) = (let ns = map fst (filter (nullable ∘ snd) xs) in
    if ns = [] then None else Some (Min (set ns)))›
proof -
  let ?P = ‹λi. ∃r. (i, r) ∈ set xs ∧ nullable r›
  have P: ‹{i. ?P i} = set (map fst (filter (nullable ∘ snd) xs))›
    by (auto intro: rev_image_eqI)
  show ?thesis
  proof (cases ‹∃i. ?P i›)
    case True
    with P have ‹(LEAST i. ?P i) = Min {i. ?P i}›
      by (subst Least_Min) auto
    with True P show ?thesis
      by (auto simp: acc_def Let_def filter_empty_conv)
  next
    case False
    then have ‹filter (nullable ∘ snd) xs = []›
      by (auto simp: filter_empty_conv)
    with False show ?thesis
      by (simp add: acc_def)
  qed
qed

subsection ‹The bound on the states›

lemma pderivs_cls_snoc: ‹pderivs_cls (Ss @ [S]) r = ⋃ (pderiv_cls S ` pderivs_cls Ss r)›
  by (induct Ss arbitrary: r) auto

lemma in_pderiv_closure_self: ‹r ∈ pderiv_closure r›
  by (auto simp: pderiv_closure_def intro: exI[of _ ‹[]›])

lemma pderiv_cls_subset_pderiv_closure:
  assumes ‹r ∈ pderiv_closure r0›
  shows ‹pderiv_cls S r ⊆ pderiv_closure r0›
proof -
  from assms obtain Ss where ‹r ∈ pderivs_cls Ss r0›
    by (auto simp: pderiv_closure_def)
  then have ‹pderiv_cls S r ⊆ pderivs_cls (Ss @ [S]) r0›
    by (auto simp: pderivs_cls_snoc)
  then show ?thesis
    by (auto simp: pderiv_closure_def)
qed

lemma atoms_pderiv_cls: ‹r' ∈ pderiv_cls S r ⟹ atoms r' ⊆ atoms r›
proof (induct r arbitrary: r')
  case (Plus r s)
  then show ?case
    by (auto dest!: Plus.hyps)
next
  case (Times r s)
  then show ?case
    by (auto split: if_splits dest!: Times.hyps)
next
  case (Star r)
  then show ?case
    by (auto dest!: Star.hyps)
qed (auto split: if_splits)

lemma atoms_pderivs_cls: ‹r' ∈ pderivs_cls Ss r ⟹ atoms r' ⊆ atoms r›
proof (induct Ss arbitrary: r)
  case (Cons S Ss)
  then obtain r'' where ‹r'' ∈ pderiv_cls S r› ‹r' ∈ pderivs_cls Ss r''›
    by auto
  with Cons.hyps have ‹atoms r' ⊆ atoms r''›
    by blast
  also from ‹r'' ∈ pderiv_cls S r› have ‹… ⊆ atoms r›
    by (rule atoms_pderiv_cls)
  finally show ?case .
qed simp

lemma atoms_if_in_pderiv_closure: ‹r' ∈ pderiv_closure r ⟹ atoms r' ⊆ atoms r›
  by (auto simp: pderiv_closure_def dest!: atoms_pderivs_cls)

text ‹Every state is a set of pairs of a rule index and a partial derivative of that
  rule's regex. These pairs are finitely many, at most the sum of the rules' alphabetic
  widths plus one each cite‹‹Thm.~3.4› in "antimirov1996-partial-derivatives"›:›

definition tagged_closure :: ‹('k, 'p, 'ch, 'm) rule list ⇒ (nat × 'p rexp) set› where
  ‹tagged_closure rs = (⋃i < length rs. {i} × pderiv_closure (match (rs ! i)))›

lemma finite_tagged_closure: ‹finite (tagged_closure rs)›
  by (simp add: tagged_closure_def finite_pderiv_closure)

lemma card_tagged_closure_le:
  ‹card (tagged_closure rs) ≤ (∑i < length rs. awidth (match (rs ! i)) + 1)›
proof -
  have ‹card (tagged_closure rs) ≤ (∑i < length rs. card (pderiv_closure (match (rs ! i))))›
    using card_UN_le[of ‹{..<length rs}› ‹λi. {i} × pderiv_closure (match (rs ! i))›]
    by (simp add: tagged_closure_def card_cartesian_product_singleton)
  also have ‹… ≤ (∑i < length rs. awidth (match (rs ! i)) + 1)›
    by (rule sum_mono) (rule card_pderiv_closure_le_awidth)
  finally show ?thesis .
qed

lemma init_state_subset: ‹init_state rs ⊆ tagged_closure rs›
  by (auto simp: tagged_closure_def in_pderiv_closure_self)

lemma delta_subset:
  assumes ‹X ⊆ tagged_closure rs›
  shows ‹delta X S ⊆ tagged_closure rs›
proof
  fix x
  assume ‹x ∈ delta X S›
  then obtain i r r' where ‹(i, r) ∈ X› ‹r' ∈ pderiv_cls S r› ‹x = (i, r')›
    by (auto simp: delta_def)
  with assms show ‹x ∈ tagged_closure rs›
    by (auto simp: tagged_closure_def dest: pderiv_cls_subset_pderiv_closure)
qed

lemma reach_subset_Pow: ‹reach delta Ss (init_state rs) ⊆ Pow (tagged_closure rs)›
  by (rule reach_subset) (auto simp: init_state_subset delta_subset)

text ‹Exploration of the states of a mode terminates, whatever the classes:›

theorem explore_dfa_Some: ‹∃Q. explore delta Ss (init_state rs) = Some (Q, length Q)›
  by (rule explore_Some, rule finite_subset[OF reach_subset_Pow]) (simp add: finite_tagged_closure)

subsection ‹The generator›

text ‹The generator explores the states of a mode over a list of classes and returns
  them with the transition table, indexed by state and class number, and the
  acceptance table. The states are for the proofs only (the runner reads the two
  tables):›

record 'p dfa =
  dfa_states :: ‹'p state list›
  dfa_trans :: ‹nat list list›
  dfa_accept :: ‹nat option list›

definition dfa :: ‹'p set list ⇒ ('k, 'p, 'ch, 'm) rule list ⇒ 'p dfa› where
  ‹dfa Ss rs = (let Q = fst (the (explore delta Ss (init_state rs))) in
    ⦇dfa_states = Q, dfa_trans = table delta Ss Q, dfa_accept = map acc Q⦈)›

lemma dfa_states_explored:
  ‹explore delta Ss (init_state rs) =
    Some (dfa_states (dfa Ss rs), length (dfa_states (dfa Ss rs)))›
  using explore_dfa_Some[of Ss rs] by (auto simp: dfa_def Let_def)

lemmas dfa_states_explore_result = explore_result[OF dfa_states_explored]

lemma dfa_states_subset: ‹X ∈ set (dfa_states (dfa Ss rs)) ⟹ X ⊆ tagged_closure rs›
  using dfa_states_explore_result[of Ss rs] reach_subset_Pow by blast

text ‹The number of states is bounded by the alphabetic widths of the rules:›

theorem length_dfa_states_le:
  ‹length (dfa_states (dfa Ss rs)) ≤ 2 ^ (∑i < length rs. awidth (match (rs ! i)) + 1)›
proof -
  let ?Q = ‹dfa_states (dfa Ss rs)›
  have ‹distinct ?Q›
    using dfa_states_explore_result[of Ss rs] by blast
  then have ‹length ?Q = card (set ?Q)›
    by (simp add: distinct_card)
  also have ‹… ≤ card (Pow (tagged_closure rs))›
    using dfa_states_subset by (intro card_mono) (auto simp: finite_tagged_closure)
  also have ‹… ≤ 2 ^ (∑i < length rs. awidth (match (rs ! i)) + 1)›
    using card_tagged_closure_le[of rs] by (simp add: card_Pow finite_tagged_closure)
  finally show ?thesis .
qed

lemma dfa_trans_eq: ‹dfa_trans (dfa Ss rs) = table delta Ss (dfa_states (dfa Ss rs))›
  by (simp add: dfa_def Let_def)

lemma length_dfa_trans: ‹length (dfa_trans (dfa Ss rs)) = length (dfa_states (dfa Ss rs))›
  by (simp add: dfa_def Let_def table_def)

lemma length_dfa_trans_row:
  ‹k < length (dfa_states (dfa Ss rs)) ⟹ length (dfa_trans (dfa Ss rs) ! k) = length Ss›
  by (simp add: dfa_def Let_def table_def)

lemma dfa_trans_correct:
  assumes ‹k < length (dfa_states (dfa Ss rs))› ‹j < length Ss›
  shows ‹dfa_trans (dfa Ss rs) ! k ! j < length (dfa_states (dfa Ss rs)) ∧
    dfa_states (dfa Ss rs) ! (dfa_trans (dfa Ss rs) ! k ! j) =
      delta (dfa_states (dfa Ss rs) ! k) (Ss ! j)›
proof -
  have ‹∀X ∈ set (dfa_states (dfa Ss rs)). ∀S ∈ set Ss. delta X S ∈ set (dfa_states (dfa Ss rs))›
    using dfa_states_explore_result[of Ss rs] by blast
  from table_correct[OF this assms] show ?thesis
    by (simp add: dfa_trans_eq)
qed

lemma dfa_accept_eq: ‹dfa_accept (dfa Ss rs) = map acc (dfa_states (dfa Ss rs))›
  by (simp add: dfa_def Let_def)

subsection ‹Correctness by character and by word›

context symbolic
begin

text ‹The step of a state by a character takes the partial derivatives by that
  character:›

definition delta_char :: ‹'p state ⇒ 'ch ⇒ 'p state› where
  ‹delta_char X c = (⋃(i, r) ∈ X. {i} × pderiv c r)›

lemma foldl_delta_char: ‹foldl delta_char X w = (⋃(i, r) ∈ X. {i} × pderivs w r)›
  by (induct w arbitrary: X) (auto simp: delta_char_def)

text ‹Reading ‹w› from the initial state reaches a nullable pair of rule ‹i› exactly
  when ‹w› is in the language of rule ‹i› (@{thm [source] Derivs_pderivs}):›

lemma nullable_in_foldl_delta_char_iff:
  ‹(∃r. (i, r) ∈ foldl delta_char (init_state rs) w ∧ nullable r) ⟷
    i < length rs ∧ w ∈ lang (match (rs ! i))›
proof -
  have ‹w ∈ lang r ⟷ [] ∈ Derivs w (lang r)› for r
    by (simp add: Derivs_def)
  then have ‹w ∈ lang r ⟷ (∃r' ∈ pderivs w r. nullable r')› for r
    by (simp add: Derivs_pderivs nullable_iff)
  then show ?thesis
    by (auto simp: foldl_delta_char Bex_def)
qed

lemma acc_foldl_delta_char_Some_iff:
  ‹acc (foldl delta_char (init_state rs) w) = Some i ⟷
    i < length rs ∧ w ∈ lang (match (rs ! i)) ∧ (∀j < i. w ∉ lang (match (rs ! j)))›
  unfolding acc_Some_iff nullable_in_foldl_delta_char_iff by auto

lemma acc_foldl_delta_char_None_iff:
  ‹acc (foldl delta_char (init_state rs) w) = None ⟷
    (∀i < length rs. w ∉ lang (match (rs ! i)))›
  unfolding acc_None_iff nullable_in_foldl_delta_char_iff by auto

text ‹On a nonempty word, the accepting rule is the first rule that matches it in the
  sense of const‹match_rule›:›

lemma acc_foldl_delta_char_match_rule:
  assumes ‹w ≠ []›
  shows ‹acc (foldl delta_char (init_state rs) w) = Some i ⟷
    i < length rs ∧ match_rule (rs ! i) w ∧ (∀j < i. ¬ match_rule (rs ! j) w)›
  using assms by (auto simp: acc_foldl_delta_char_Some_iff match_rule.simps)

text ‹The dead state stays dead:›

lemma foldl_delta_char_empty[simp]: ‹foldl delta_char {} w = {}›
  by (simp add: foldl_delta_char)

end

subsection ‹The DFA of a mode over its minterms›

text ‹The atoms of a mode, collected as ‹add_atoms› does in session‹Regular-Sets›
  (‹Equivalence_Checking›):›

primrec atom_list :: ‹'p rexp ⇒ 'p list› where
  ‹atom_list Zero = []›
| ‹atom_list One = []›
| ‹atom_list (Atom p) = [p]›
| ‹atom_list (Plus r s) = atom_list r @ atom_list s›
| ‹atom_list (Times r s) = atom_list r @ atom_list s›
| ‹atom_list (Star r) = atom_list r›

lemma set_atom_list[simp]: ‹set (atom_list r) = atoms r›
  by (induct r) auto

definition mode_atoms :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'p list› where
  ‹mode_atoms rs = remdups (concat (map (atom_list ∘ match) rs))›

lemma atoms_subset_mode_atoms: ‹i < length rs ⟹ atoms (match (rs ! i)) ⊆ set (mode_atoms rs)›
  by (auto simp: mode_atoms_def intro: nth_mem)

context eba
begin

definition mode_minterms :: ‹('k, 'p, 'ch, 'm) rule list ⇒ ('p set × 'p) list› where
  ‹mode_minterms rs = minterms (mode_atoms rs)›

definition mode_dfa :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'p dfa› where
  ‹mode_dfa rs = dfa (map fst (mode_minterms rs)) rs›

text ‹A transition by a minterm is the step by any character of it
  cite‹‹Prop.~1› in "dantoni2014-minimization-symbolic-automata"› cite‹‹Lemma~9› in "keil2014-symbolic-regex-inequalities"›:›

lemma delta_eq_delta_char:
  assumes ‹X ⊆ tagged_closure rs› ‹(S, μ) ∈ set (mode_minterms rs)› ‹sem μ c›
  shows ‹delta X S = delta_char X c›
proof -
  have ‹pderiv_cls S r = pderiv c r› if ‹(i, r) ∈ X› for i r
  proof -
    from that assms(1) have ‹i < length rs› ‹r ∈ pderiv_closure (match (rs ! i))›
      by (auto simp: tagged_closure_def)
    then have ‹atoms r ⊆ set (mode_atoms rs)›
      by (meson atoms_if_in_pderiv_closure atoms_subset_mode_atoms order_trans)
    with assms(2,3) show ?thesis
      by (simp add: pderiv_eq_pderiv_cls_minterm mode_minterms_def)
  qed
  then show ?thesis
    unfolding delta_def delta_char_def by (auto intro!: SUP_cong)
qed

text ‹The minterm of a character. The run-time lexer replaces it by a table lookup:›

definition minterm_index :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'ch ⇒ nat› where
  ‹minterm_index rs c =
    (LEAST k. k < length (mode_minterms rs) ∧ sem (snd (mode_minterms rs ! k)) c)›

lemma minterm_index:
  ‹minterm_index rs c < length (mode_minterms rs) ∧
    sem (snd (mode_minterms rs ! minterm_index rs c)) c›
proof -
  obtain S μ where ‹(S, μ) ∈ set (mode_minterms rs)› ‹sem μ c›
    using minterms_cover[of ‹mode_atoms rs› c] unfolding mode_minterms_def by blast
  then obtain k where ‹k < length (mode_minterms rs) ∧ sem (snd (mode_minterms rs ! k)) c›
    by (metis in_set_conv_nth snd_conv)
  then show ?thesis
    unfolding minterm_index_def by (rule LeastI)
qed

text ‹The tables run on a word, a character at a time through its minterm:›

definition dfa_run :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'ch list ⇒ nat› where
  ‹dfa_run rs w = foldl (λq c. dfa_trans (mode_dfa rs) ! q ! minterm_index rs c) 0 w›

lemma dfa_run_from_correct:
  assumes ‹q < length (dfa_states (mode_dfa rs))›
  shows ‹foldl (λq c. dfa_trans (mode_dfa rs) ! q ! minterm_index rs c) q w
      < length (dfa_states (mode_dfa rs)) ∧
    dfa_states (mode_dfa rs) ! foldl (λq c. dfa_trans (mode_dfa rs) ! q ! minterm_index rs c) q w
      = foldl delta_char (dfa_states (mode_dfa rs) ! q) w›
  using assms
proof (induct w arbitrary: q)
  case (Cons c w)
  let ?M = ‹mode_minterms rs›
  let ?Q = ‹dfa_states (mode_dfa rs)›
  let ?k = ‹minterm_index rs c›
  let ?q' = ‹dfa_trans (mode_dfa rs) ! q ! ?k›
  from minterm_index have k: ‹?k < length ?M› ‹sem (snd (?M ! ?k)) c›
    by blast+
  have q': ‹?q' < length ?Q ∧ ?Q ! ?q' = delta (?Q ! q) (fst (?M ! ?k))›
    using dfa_trans_correct[of q ‹map fst ?M› rs ?k] Cons.prems k(1)
    by (simp add: mode_dfa_def)
  have ‹?Q ! q ⊆ tagged_closure rs›
    using dfa_states_subset[OF nth_mem[OF Cons.prems[unfolded mode_dfa_def]]]
    by (simp add: mode_dfa_def)
  moreover have ‹(fst (?M ! ?k), snd (?M ! ?k)) ∈ set ?M›
    using k(1) by simp
  ultimately have ‹delta (?Q ! q) (fst (?M ! ?k)) = delta_char (?Q ! q) c›
    using k(2) by (rule delta_eq_delta_char)
  with q' Cons.hyps[of ?q'] show ?case
    by simp
qed simp

text ‹The state the tables reach on ‹w› is the step of the initial state by ‹w›:›

theorem dfa_run_correct:
  ‹dfa_run rs w < length (dfa_states (mode_dfa rs)) ∧
    dfa_states (mode_dfa rs) ! dfa_run rs w = foldl delta_char (init_state rs) w›
  using dfa_run_from_correct[of 0 rs w] dfa_states_explore_result[of _ rs]
  by (simp add: dfa_run_def mode_dfa_def)

text ‹The acceptance table names the least rule whose language contains the word read:›

theorem dfa_run_accept_Some_iff:
  ‹dfa_accept (mode_dfa rs) ! dfa_run rs w = Some i ⟷
    i < length rs ∧ w ∈ lang (match (rs ! i)) ∧ (∀j < i. w ∉ lang (match (rs ! j)))›
  using dfa_run_correct[of rs w]
  by (simp add: mode_dfa_def dfa_accept_eq acc_foldl_delta_char_Some_iff)

theorem dfa_run_accept_None_iff:
  ‹dfa_accept (mode_dfa rs) ! dfa_run rs w = None ⟷
    (∀i < length rs. w ∉ lang (match (rs ! i)))›
  using dfa_run_correct[of rs w]
  by (simp add: mode_dfa_def dfa_accept_eq acc_foldl_delta_char_None_iff)

end

end