Theory LR_Restrict

(* Author: Basil Fürer *)

theory LR_Restrict
  imports TIGER_Grammar_Model.Grammar_Base "HOL-Library.While_Combinator"
begin

section ‹Restricting the trees of a grammar by a tree automaton›

text ‹A tree automaton ‹A› selects the trees of an indentation grammar
  ‹G› it accepts; this theory computes a grammar ‹G'› whose trees are,
  up to renaming and unit chains, exactly those.  This is the construction of
  Adams and Might cite‹‹Sect.~3› in "adams2017-tree-automata"›: label the
  productions, intersect with the automaton, and read the product back as a
  grammar.  The theorems are text‹restrict_sound›, text‹restrict_complete›
  and text‹restrict_ilang›, for any ‹G'› that meets ‹restrict_ok›, and
  text‹restrict_gen_correct› (at the end): the executable ‹restrict_gen›
  produces such a ‹G'›.  The paper states the construction without a
  proof of this correspondence; its Sect.~6 proves other properties.›

subsection ‹The automaton and its runs›

text ‹‹prec_aut› is a deterministic top-down tree automaton whose labels
  are the productions of ‹G› cite‹‹Sect.~2.2› in "adams2017-tree-automata"›:
  in state ‹q›, ‹ok› says whether a production may label the node, and
  ‹step› gives the state of its ‹k›-th child.  The paper notes that
  deterministic top-down automata are strictly weaker than the general ones;
  the precedence automata used here are of this kind.  ‹prec_run› is
  ‹wf_ptree› with the automaton's checks added at every node.›

type_synonym ('n, 't) alt = ‹'n × ('n, 't) rhs›

record ('n, 't, 'q) prec_aut =
  ok   :: ‹'q ⇒ ('n, 't) alt ⇒ bool›
  step :: ‹'q ⇒ ('n, 't) alt ⇒ nat ⇒ 'q›

inductive prec_run ::
  ‹('n, 't) is_cfg ⇒ ('n, 't, 'q) prec_aut ⇒ 'q ⇒ ('m, 'ch, 'n, 't) ptree ⇒ bool›
  for G A where
  prec_leaf: ‹prec_run G A q (PLeaf t)›
| prec_node: ‹(n, r) ∈ set (iprods G) ⟹ ok A q (n, r) ⟹
    length ts = length r ⟹
    (⋀k. k < length r ⟹ fst (proot (ts ! k)) = fst (r ! k) ∧
      irel_sat (snd (r ! k)) (snd (proot (ts ! k))) i ∧
      prec_run G A (step A q (n, r) k) (ts ! k)) ⟹
    prec_run G A q (PNode n i ts)›

subsection ‹The restricted grammar and its correctness›

text ‹The nonterminals of ‹G'› stand for pairs of a nonterminal of ‹G›
  and an automaton state, the Cartesian product of
  cite‹‹Sect.~3.1.3› in "adams2017-tree-automata"›; ‹orig› forgets the state.
  ‹G'› may also contain unit productions ‹n → m› with
  ‹orig n = orig m›, and ‹plain› removes them when it maps a tree of
  ‹G'› back to one of ‹G›.  The locale ‹restrict_ok› collects what the
  proofs need of ‹G'›.›

fun usym :: ‹('n' ⇒ 'n) ⇒ ('n', 't) sym ⇒ ('n, 't) sym› where
  ‹usym orig (Nt n) = Nt (orig n)›
| ‹usym orig (Tm t) = Tm t›

definition urhs :: ‹('n' ⇒ 'n) ⇒ ('n', 't) rhs ⇒ ('n, 't) rhs› where
  ‹urhs orig = map (λ(X, r). (usym orig X, r))›

definition unit_alt :: ‹('n' ⇒ 'n) ⇒ ('n', 't) alt ⇒ 'n' ⇒ bool› where
  ‹unit_alt orig p m ⟷ snd p = [(Nt m, Eq)] ∧ orig m = orig (fst p)›

definition units :: ‹('n', 't) is_cfg ⇒ ('n' ⇒ 'n) ⇒ 'n' ⇒ 'n' ⇒ bool› where
  ‹units G' orig n m ⟷ (∃r. (n, r) ∈ set (iprods G') ∧ unit_alt orig (n, r) m)›

abbreviation units_star where ‹units_star G' orig ≡ (units G' orig)**›

fun plain :: ‹('n' ⇒ 'n) ⇒ ('m, 'ch, 'n', 't) ptree ⇒ ('m, 'ch, 'n, 't) ptree› where
  ‹plain orig (PLeaf t) = PLeaf t›
| ‹plain orig (PNode n i [PNode m j us]) =
     (if orig m = orig n then plain orig (PNode m j us)
      else PNode (orig n) i [plain orig (PNode m j us)])›
| ‹plain orig (PNode n i ts) = PNode (orig n) i (map (plain orig) ts)›

fun plain_ast :: ‹('n' ⇒ 'n) ⇒ ('m, 'ch, 'n', 't) ast ⇒ ('m, 'ch, 'n, 't) ast› where
  ‹plain_ast orig (Leaf t) = Leaf t›
| ‹plain_ast orig (Node n [Node m us]) =
     (if orig m = orig n then plain_ast orig (Node m us)
      else Node (orig n) [plain_ast orig (Node m us)])›
| ‹plain_ast orig (Node n ts) = Node (orig n) (map (plain_ast orig) ts)›

lemma pyield_plain[simp]: ‹pyield (plain orig t) = pyield t›
  by (induction orig t rule: plain.induct) (auto intro!: arg_cong[of _ _ concat])

lemma erase_plain: ‹erase (plain orig t) = plain_ast orig (erase t)›
  by (induction orig t rule: plain.induct) auto

lemma plain_node:
  assumes ‹⋀m j us. ts = [PNode m j us] ⟹ orig m ≠ orig n›
  shows ‹plain orig (PNode n i ts) = PNode (orig n) i (map (plain orig) ts)›
  using assms by (cases ‹(orig, PNode n i ts)› rule: plain.cases) auto

definition no_self_unit :: ‹('n, 't) is_cfg ⇒ bool› where
  ‹no_self_unit G ⟷ (∀n r. (n, [(Nt n, r)]) ∉ set (iprods G))›

lemma prec_run_wf: ‹prec_run G A q t ⟹ wf_ptree G t›
proof (induction rule: prec_run.induct)
  case (prec_leaf t)
  show ?case by (rule wf_leaf)
next
  case (prec_node n r q ts i)
  show ?case
    by (rule wf_node[OF prec_node.hyps(1)]) (use prec_node.hyps(3) prec_node.IH in ‹auto simp: list_all2_conv_all_nth›)
qed

locale restrict_ok =
  fixes G :: ‹('n, 't) is_cfg› and A :: ‹('n, 't, 'q) prec_aut› and q0 :: 'q
    and Q :: ‹'q set› and cls :: ‹'q ⇒ 'n'›
    and G' :: ‹('n', 't) is_cfg› and orig :: ‹'n' ⇒ 'n›
  assumes start: ‹q0 ∈ Q› ‹cls q0 = istart G'› ‹orig (istart G') = istart G›
      ‹istart_ind G' = istart_ind G›
    and no_self: ‹no_self_unit G›
    and closed: ‹q ∈ Q ⟹ (n, r) ∈ set (iprods G) ⟹ n = orig (cls q) ⟹ ok A q (n, r) ⟹
        k < length r ⟹ fst (r ! k) = Nt x ⟹
        step A q (n, r) k ∈ Q ∧ orig (cls (step A q (n, r) k)) = x›
    and sound: ‹q ∈ Q ⟹ units_star G' orig (cls q) m ⟹ (m, r') ∈ set (iprods G') ⟹
        ¬ (∃c. unit_alt orig (m, r') c) ⟹
        (orig m, urhs orig r') ∈ set (iprods G) ∧ ok A q (orig m, urhs orig r') ∧
        (∀k c. k < length r' ⟶ fst (r' ! k) = Nt c ⟶
           c = cls (step A q (orig m, urhs orig r') k))›
    and complete: ‹q ∈ Q ⟹ (orig (cls q), r) ∈ set (iprods G) ⟹ ok A q (orig (cls q), r) ⟹
        ∃m r'. units_star G' orig (cls q) m ∧ (m, r') ∈ set (iprods G') ∧ orig m = orig (cls q) ∧
          urhs orig r' = r ∧ (∀k c. k < length r' ⟶ fst (r' ! k) = Nt c ⟶
             c = cls (step A q (orig (cls q), r) k))›
begin

lemma units_star_orig: ‹(units G' orig)** n m ⟹ orig m = orig n›
  by (induction rule: rtranclp_induct) (auto simp: units_def unit_alt_def)

lemma units_wrap:
  assumes ‹(units G' orig)** n m›
  shows ‹wf_ptree G' s ⟹ proot s = (Nt m, i) ⟹
    ∃t'. wf_ptree G' t' ∧ proot t' = (Nt n, i) ∧ plain orig t' = plain orig s›
  using assms
proof (induction rule: converse_rtranclp_induct)
  case base
  then show ?case by blast
next
  case (step n n2)
  then obtain t' where t': ‹wf_ptree G' t'› ‹proot t' = (Nt n2, i)› ‹plain orig t' = plain orig s›
    by blast
  from step.hyps(1) obtain r where r: ‹(n, r) ∈ set (iprods G')› ‹r = [(Nt n2, Eq)]›
    ‹orig n2 = orig n› by (auto simp: units_def unit_alt_def)
  from t'(2) obtain us where us: ‹t' = PNode n2 i us› by (cases t') auto
  have ‹wf_ptree G' (PNode n i [t'])›
    using wf_node[OF r(1), of i ‹[t']›] r(2) t' by simp
  with us r(3) t'(3) show ?case
    by (intro exI[of _ ‹PNode n i [t']›]) simp
qed

lemma urhs_nth:
  ‹k < length r' ⟹ urhs orig r' ! k = (usym orig (fst (r' ! k)), snd (r' ! k))›
  by (auto simp: urhs_def case_prod_beta)

lemma length_urhs[simp]: ‹length (urhs orig r') = length r'›
  by (simp add: urhs_def)

lemma usym_Nt: ‹usym orig X = Nt x ⟹ ∃c. X = Nt c ∧ orig c = x›
  by (cases X) auto

lemma usym_Tm: ‹usym orig X = Tm t ⟹ X = Tm t›
  by (cases X) auto

theorem restrict_sound:
  fixes t' :: ‹('m, 'ch, 'n', 't) ptree›
  assumes ‹wf_ptree G' t'›
  shows ‹⋀n' q. fst (proot t') = Nt n' ⟹ q ∈ Q ⟹ units_star G' orig (cls q) n' ⟹
    prec_run G A q (plain orig t') ∧
    proot (plain orig t') = (Nt (orig n'), snd (proot t'))›
  using assms
proof (induction rule: wf_ptree.induct)
  case (wf_leaf t)
  then show ?case by simp
next
  case (wf_node a rhs i pts)
  from wf_node.prems(1) have n: ‹n' = a› by simp
  note q = ‹q ∈ Q›
  have ustar: ‹units_star G' orig (cls q) a› using wf_node.prems(3) n by simp
  have len: ‹length pts = length rhs› using wf_node.IH by (simp add: list_all2_lengthD)
  have ih: ‹fst (proot (pts ! k)) = fst (rhs ! k) ∧
      irel_sat (snd (rhs ! k)) (snd (proot (pts ! k))) i ∧ wf_ptree G' (pts ! k) ∧
      (∀x xa. fst (proot (pts ! k)) = Nt x ⟶ xa ∈ Q ⟶ units_star G' orig (cls xa) x ⟶
        prec_run G A xa (plain orig (pts ! k)) ∧
        proot (plain orig (pts ! k)) = (Nt (orig x), snd (proot (pts ! k))))›
    if ‹k < length rhs› for k
    using list_all2_nthD[OF wf_node.IH that] by simp
  show ?case
  proof (cases ‹∃c. unit_alt orig (a, rhs) c›)
    case True
    then obtain c where c: ‹rhs = [(Nt c, Eq)]› ‹orig c = orig a›
      by (auto simp: unit_alt_def)
    with len obtain p where p: ‹pts = [p]› by (cases pts) auto
    from ih[of 0] c p have 1: ‹fst (proot p) = Nt c› ‹snd (proot p) = i› by auto
    then obtain us where u: ‹p = PNode c i us› by (cases p) auto
    have ustar': ‹units_star G' orig (cls q) c›
      using ustar wf_node.hyps c by (auto simp: units_def unit_alt_def intro: rtranclp.rtrancl_into_rtrancl)
    from ih[of 0] c p have ‹prec_run G A q (plain orig p)›
      ‹proot (plain orig p) = (Nt (orig c), i)› using q ustar' 1 by auto
    with c p u n show ?thesis by simp
  next
    case False
    from sound[OF q ustar wf_node.hyps False]
    have s: ‹(orig a, urhs orig rhs) ∈ set (iprods G)› ‹ok A q (orig a, urhs orig rhs)›
      ‹⋀k c. k < length rhs ⟹ fst (rhs ! k) = Nt c ⟹
         c = cls (step A q (orig a, urhs orig rhs) k)› by auto
    have pn: ‹plain orig (PNode a i pts) = PNode (orig a) i (map (plain orig) pts)›
    proof (rule plain_node, rule notI)
      fix m j us assume ‹pts = [PNode m j us]› ‹orig m = orig a›
      moreover from this(1) len obtain r1 where ‹rhs = [r1]›
        by (cases rhs) auto
      moreover from calculation ih[of 0] have ‹fst r1 = Nt m› by simp
      ultimately have ‹(orig a, [(Nt (orig a), snd r1)]) ∈ set (iprods G)›
        using s(1) by (cases r1) (simp add: urhs_def)
      with no_self show False by (auto simp: no_self_unit_def)
    qed
    have ‹prec_run G A q (PNode (orig a) i (map (plain orig) pts))›
    proof (rule prec_node[OF s(1,2)])
      show ‹length (map (plain orig) pts) = length (urhs orig rhs)› using len by simp
    next
      fix k assume k: ‹k < length (urhs orig rhs)›
      then have k': ‹k < length rhs› by simp
      note ihk = ih[OF k']
      have un: ‹urhs orig rhs ! k = (usym orig (fst (rhs ! k)), snd (rhs ! k))›
        using urhs_nth[OF k'] .
      show ‹fst (proot (map (plain orig) pts ! k)) = fst (urhs orig rhs ! k) ∧
        irel_sat (snd (urhs orig rhs ! k)) (snd (proot (map (plain orig) pts ! k))) i ∧
        prec_run G A (step A q (orig a, urhs orig rhs) k) (map (plain orig) pts ! k)›
      proof (cases ‹fst (rhs ! k)›)
        case (Nt c)
        have rx: ‹fst (urhs orig rhs ! k) = Nt (orig c)› using un Nt by simp
        have orig_a: ‹orig a = orig (cls q)› using units_star_orig[OF ustar] .
        have st: ‹step A q (orig a, urhs orig rhs) k ∈ Q›
          using closed[OF q s(1) orig_a s(2), of k ‹orig c›] k rx by simp
        have ‹c = cls (step A q (orig a, urhs orig rhs) k)› using s(3)[OF k' Nt] .
        with ihk Nt st have
          ‹prec_run G A (step A q (orig a, urhs orig rhs) k) (plain orig (pts ! k))›
          ‹proot (plain orig (pts ! k)) = (Nt (orig c), snd (proot (pts ! k)))›
          by (metis rtranclp.rtrancl_refl)+
        with ihk un Nt k' len show ?thesis by simp
      next
        case (Tm x)
        with ihk obtain tk where ‹pts ! k = PLeaf tk› ‹tok tk = x›
          by (auto simp: fst_proot_Tm_iff)
        with ihk un Tm k' len show ?thesis by (auto intro: prec_leaf)
      qed
    qed
    with pn n show ?thesis by simp
  qed
qed

theorem restrict_complete:
  fixes t :: ‹('m, 'ch, 'n, 't) ptree›
  assumes ‹prec_run G A q t› ‹q ∈ Q› ‹fst (proot t) = Nt (orig (cls q))›
  shows ‹∃t'. wf_ptree G' t' ∧ proot t' = (Nt (cls q), snd (proot t)) ∧ plain orig t' = t›
  using assms
proof (induction rule: prec_run.induct)
  case (prec_leaf t)
  then show ?case by simp
next
  case (prec_node n r q ts i)
  have nq: ‹n = orig (cls q)› using prec_node.prems(2) by simp
  note q = prec_node.prems(1)
  have g: ‹(orig (cls q), r) ∈ set (iprods G)› and o: ‹ok A q (orig (cls q), r)›
    using prec_node.hyps(1,2) nq by simp_all
  from complete[OF q g o] obtain m r' where m:
    ‹units_star G' orig (cls q) m› ‹(m, r') ∈ set (iprods G')› ‹orig m = orig (cls q)›
    ‹urhs orig r' = r›
    ‹⋀k c. k < length r' ⟹ fst (r' ! k) = Nt c ⟹ c = cls (step A q (orig (cls q), r) k)›
    by blast
  have lr: ‹length r' = length r› using m(4) by auto
  define P where ‹P k s ⟷ wf_ptree G' s ∧ fst (proot s) = fst (r' ! k) ∧
    snd (proot s) = snd (proot (ts ! k)) ∧ plain orig s = ts ! k›
    for k and s :: ‹('m, 'ch, 'n', 't) ptree›
  have ex: ‹∃s. P k s› if k: ‹k < length r› for k
  proof (cases ‹fst (r' ! k)›)
    case (Nt c)
    have k': ‹k < length r'› using k lr by simp
    have rk: ‹fst (r ! k) = Nt (orig c)›
      using urhs_nth[OF k'] m(4) Nt by simp
    have c: ‹c = cls (step A q (orig (cls q), r) k)› using m(5)[OF k' Nt] .
    from closed[OF q g refl o k rk]
    have st: ‹step A q (orig (cls q), r) k ∈ Q› by blast
    from prec_node.IH[OF k] have ‹fst (proot (ts ! k)) = fst (r ! k)› by blast
    with prec_node.IH[OF k] st rk c nq obtain s where
      ‹wf_ptree G' s› ‹proot s = (Nt c, snd (proot (ts ! k)))› ‹plain orig s = ts ! k›
      by (metis (no_types, lifting))
    with Nt show ?thesis by (auto simp: P_def)
  next
    case (Tm x)
    have k': ‹k < length r'› using k lr by simp
    have rk: ‹fst (r ! k) = Tm x› using urhs_nth[OF k'] m(4) Tm by simp
    from prec_node.IH[OF k] rk obtain tk where lf: ‹ts ! k = PLeaf tk› ‹tok tk = x›
      by (auto simp: fst_proot_Tm_iff)
    show ?thesis unfolding P_def using lf Tm
      by (intro exI[of _ ‹PLeaf tk›]) (auto intro: wf_leaf)
  qed
  then obtain f where f: ‹⋀k. k < length r ⟹ P k (f k)› by metis
  define ts' where ‹ts' = map f [0..<length r]›
  have lts': ‹length ts' = length r'› using lr by (simp add: ts'_def)
  have nth: ‹ts' ! k = f k› if ‹k < length r› for k using that by (simp add: ts'_def)
  have sat: ‹irel_sat (snd (r' ! k)) (snd (proot (ts' ! k))) i› if k: ‹k < length r'› for k
  proof -
    have ‹k < length r› using k lr by simp
    with prec_node.IH[OF this] f[OF this] nth[OF this] urhs_nth[OF k] m(4)
    show ?thesis by (simp add: P_def)
  qed
  have wf: ‹wf_ptree G' (PNode m i ts')›
  proof (rule wf_node[OF m(2)])
    show ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧ irel_sat (snd Xr) (snd (proot pt)) i ∧
        wf_ptree G' pt) r' ts'›
      using lts' f nth sat lr by (auto simp: list_all2_conv_all_nth P_def)
  qed
  have pl: ‹plain orig (PNode m i ts') = PNode (orig m) i (map (plain orig) ts')›
  proof (rule plain_node, rule notI)
    fix m2 j us assume a: ‹ts' = [PNode m2 j us]› ‹orig m2 = orig m›
    with lts' obtain r1 where r1: ‹r' = [r1]› by (cases r') auto
    with lr have l1: ‹length r = 1› by simp
    have ‹P 0 (PNode m2 j us)› using f[of 0] nth[of 0] a l1 by simp
    then have ‹fst r1 = Nt m2› using r1 by (simp add: P_def)
    then have ‹r = [(Nt (orig m), snd r1)]› using m(4) r1 a(2)
      by (cases r1) (auto simp: urhs_def)
    with g m(3) no_self show False by (auto simp: no_self_unit_def)
  qed
  have ts: ‹map (plain orig) ts' = ts›
    by (rule nth_equalityI) (use prec_node.hyps(3) lr f nth lts' in ‹auto simp: P_def›)
  from units_wrap[OF m(1) wf, of i]
  obtain t' where ‹wf_ptree G' t'› ‹proot t' = (Nt (cls q), i)›
    ‹plain orig t' = plain orig (PNode m i ts')› by auto
  with pl ts m(3) nq show ?case by (intro exI[of _ t']) simp
qed

lemma ilang_iff_ptree:
  ‹w ∈ ilang H ⟷ (∃pt. wf_ptree H pt ∧ proot pt = (Nt (istart H), istart_ind H) ∧ pyield pt = w)›
  by (simp add: ilang_derives derives_iff_ptree)

theorem restrict_ilang:
  ‹w ∈ ilang G' ⟷
   (∃t. prec_run G A q0 t ∧ proot t = (Nt (istart G), istart_ind G) ∧ pyield t = w)›
  unfolding ilang_iff_ptree
proof
  assume ‹∃pt. wf_ptree G' pt ∧ proot pt = (Nt (istart G'), istart_ind G') ∧ pyield pt = w›
  then obtain pt where pt: ‹wf_ptree G' pt› ‹proot pt = (Nt (istart G'), istart_ind G')›
    ‹pyield pt = w› by blast
  have ‹prec_run G A q0 (plain orig pt) ∧
      proot (plain orig pt) = (Nt (orig (istart G')), snd (proot pt))›
    by (rule restrict_sound[OF pt(1)]) (use pt(2) start in auto)
  with pt start show ‹∃t. prec_run G A q0 t ∧ proot t = (Nt (istart G), istart_ind G) ∧ pyield t = w›
    by (intro exI[of _ ‹plain orig pt›]) simp
next
  assume ‹∃t. prec_run G A q0 t ∧ proot t = (Nt (istart G), istart_ind G) ∧ pyield t = w›
  then obtain t where t: ‹prec_run G A q0 t› ‹proot t = (Nt (istart G), istart_ind G)›
    ‹pyield t = w› by blast
  from restrict_complete[OF t(1)] t(2) start obtain t' where
    ‹wf_ptree G' t'› ‹proot t' = (Nt (istart G'), istart_ind G')› ‹plain orig t' = t› by auto
  with t(3) pyield_plain[of orig t']
  show ‹∃pt. wf_ptree G' pt ∧ proot pt = (Nt (istart G'), istart_ind G') ∧ pyield pt = w›
    by metis
qed

end

section ‹Reachability by a worklist›

text ‹The reachable automaton states, and later the reachable classes, are
  collected by a worklist over const‹while_option›.›

fun reach_step :: ‹('a ⇒ 'a list) ⇒ 'a list × 'a list ⇒ 'a list × 'a list› where
  ‹reach_step f (x # ws, vs) = (if x ∈ set vs then (ws, vs) else (f x @ ws, x # vs))›
| ‹reach_step f ([], vs) = ([], vs)›

definition reach :: ‹('a ⇒ 'a list) ⇒ 'a ⇒ 'a list› where
  ‹reach f x = rev (snd (the (while_option (λs. fst s ≠ []) (reach_step f) ([x], []))))›

definition steps :: ‹('a ⇒ 'a list) ⇒ ('a × 'a) set› where
  ‹steps f = {(x, y). y ∈ set (f x)}›

lemma steps_closed:
  assumes ‹z ∈ (steps f)* `` {x}› ‹y ∈ set (f z)›
  shows ‹y ∈ (steps f)* `` {x}›
proof -
  have ‹(z, y) ∈ steps f› using assms(2) by (simp add: steps_def)
  with assms(1) show ?thesis by (auto intro: rtrancl_into_rtrancl)
qed

lemma reach_terminates:
  assumes fin: ‹finite ((steps f)* `` {x})›
  shows ‹∃t. while_option (λs. fst s ≠ []) (reach_step f) ([x], []) = Some t›
proof -
  let ?C = ‹(steps f)* `` {x}›
  let ?P = ‹λs. set (fst s) ⊆ ?C ∧ set (snd s) ⊆ ?C›
  let ?R = ‹inv_image (less_than <*lex*> less_than)
     (λs. (card (?C - set (snd s)), length (fst s)))›
  show ?thesis
  proof (rule wf_rel_while_option_Some[where R = ?R and P = ?P])
    show ‹wf ?R› by auto
  next
    fix s assume s: ‹?P s ∧ fst s ≠ []›
    obtain y ws vs where e: ‹s = (y # ws, vs)› using s by (cases s; cases ‹fst s›) auto
    show ‹(reach_step f s, s) ∈ ?R›
    proof (cases ‹y ∈ set vs›)
      case True then show ?thesis by (simp add: e)
    next
      case False
      with s e have ‹y ∈ ?C - set vs› by auto
      then have ‹card (?C - insert y (set vs)) < card (?C - set vs)›
        using fin by (metis Diff_insert card_Diff1_less finite_Diff)
      with False show ?thesis by (simp add: e)
    qed
  next
    fix s assume s: ‹?P s ∧ fst s ≠ []›
    obtain y ws vs where e: ‹s = (y # ws, vs)› using s by (cases s; cases ‹fst s›) auto
    with s steps_closed[of y f x] show ‹?P (reach_step f s)› by auto
  next
    show ‹?P ([x], [])› by simp
  qed
qed

lemma reach_spec:
  assumes fin: ‹finite ((steps f)* `` {x})›
  shows ‹x ∈ set (reach f x)› ‹⋀y z. y ∈ set (reach f x) ⟹ z ∈ set (f y) ⟹ z ∈ set (reach f x)›
    ‹set (reach f x) ⊆ (steps f)* `` {x}›
proof -
  from reach_terminates[OF fin] obtain t where t:
    ‹while_option (λs. fst s ≠ []) (reach_step f) ([x], []) = Some t› by blast
  let ?C = ‹(steps f)* `` {x}›
  let ?P = ‹λs. (x ∈ set (fst s) ∪ set (snd s)) ∧
     (∀y ∈ set (snd s). set (f y) ⊆ set (fst s) ∪ set (snd s)) ∧ set (snd s) ⊆ ?C ∧ set (fst s) ⊆ ?C›
  have ‹?P t›
  proof (rule while_option_rule[OF _ t])
    fix s assume s: ‹?P s› ‹fst s ≠ []›
    obtain y ws vs where e: ‹s = (y # ws, vs)› using s(2) by (cases s; cases ‹fst s›) auto
    have ‹set (f y) ⊆ ?C› using s e steps_closed[of y f x] by auto
    with s(1) e show ‹?P (reach_step f s)› by auto
  next
    show ‹?P ([x], [])› by simp
  qed
  moreover have ‹fst t = []› using while_option_stop[OF t] by simp
  ultimately show ‹x ∈ set (reach f x)› ‹set (reach f x) ⊆ ?C›
    ‹⋀y z. y ∈ set (reach f x) ⟹ z ∈ set (f y) ⟹ z ∈ set (reach f x)›
    by (auto simp: reach_def t)
qed

section ‹Moore's partition refinement›

text ‹The product has duplicate nonterminals.  Adams and Might remove them
  by tree-automaton minimisation cite‹‹Sect.~3.1.3, Fig.~11b› in "adams2017-tree-automata"›.
  Here the reachable states are partitioned by Moore-style refinement: two
  states share a class when they have the same nonterminal and the same rows
  of productions and child classes.›

fun first_ix :: ‹'a ⇒ 'a list ⇒ nat› where
  ‹first_ix x [] = 0›
| ‹first_ix x (y # ys) = (if x = y then 0 else Suc (first_ix x ys))›

lemma first_ix_nth: ‹x ∈ set xs ⟹ first_ix x xs < length xs ∧ xs ! first_ix x xs = x›
  by (induction xs) auto

definition number :: ‹'a list ⇒ nat list› where
  ‹number xs = map (λx. first_ix x xs) xs›

lemma number_eq:
  assumes ‹i < length xs› ‹j < length xs› ‹number xs ! i = number xs ! j›
  shows ‹xs ! i = xs ! j›
proof -
  have a: ‹xs ! first_ix (xs ! i) xs = xs ! i›
    using first_ix_nth[OF nth_mem[OF assms(1)]] by blast
  have b: ‹xs ! first_ix (xs ! j) xs = xs ! j›
    using first_ix_nth[OF nth_mem[OF assms(2)]] by blast
  have ‹first_ix (xs ! i) xs = first_ix (xs ! j) xs›
    using assms by (simp add: number_def)
  with a b show ?thesis by metis
qed

type_synonym 'l mtab = ‹('l × nat option list) list list›

definition sg :: ‹'k list ⇒ 'l mtab ⇒ nat list ⇒ nat ⇒ 'k × ('l × nat option list) list› where
  ‹sg K T π i = (K ! i, map (λ(l, ks). (l, map (map_option ((!) π)) ks)) (T ! i))›

definition refine :: ‹'k list ⇒ 'l mtab ⇒ nat list ⇒ nat list› where
  ‹refine K T π = number (map (sg K T π) [0..<length T])›

fun moore :: ‹'k list ⇒ 'l mtab ⇒ nat ⇒ nat list ⇒ nat list› where
  ‹moore K T 0 π = [0..<length T]›
| ‹moore K T (Suc f) π =
     (let π' = refine K T π in if π' = π then π else moore K T f π')›

definition mstable :: ‹'k list ⇒ 'l mtab ⇒ nat list ⇒ bool› where
  ‹mstable K T π ⟷ length π = length T ∧
     (∀i j. i < length T ⟶ j < length T ⟶ π ! i = π ! j ⟶ sg K T π i = sg K T π j)›

lemma mstable_moore: ‹mstable K T (moore K T f π)›
proof (induction f arbitrary: π)
  case 0
  have ‹sg K T [0..<length T] i = sg K T [0..<length T] j›
    if ‹i < length T› ‹j < length T› ‹[0..<length T] ! i = [0..<length T] ! j› for i j
  proof -
    from that have ‹i = j› by simp
    then show ?thesis by (rule arg_cong)
  qed
  then show ?case unfolding mstable_def moore.simps by simp
next
  case (Suc f)
  show ?case
  proof (cases ‹refine K T π = π›)
    case False
    with Suc show ?thesis by (simp add: Let_def)
  next
    case True
    have ‹sg K T π i = sg K T π j›
      if ‹i < length T› ‹j < length T› ‹π ! i = π ! j› for i j
      using number_eq[of i ‹map (sg K T π) [0..<length T]› j] that True
      by (simp add: refine_def)
    moreover have ‹length π = length T›
      using arg_cong[OF True, of length] by (simp add: refine_def number_def)
    ultimately have ‹mstable K T π› unfolding mstable_def by blast
    moreover have ‹moore K T (Suc f) π = π› using True by (simp add: Let_def)
    ultimately show ?thesis by (simp only:)
  qed
qed

definition mclass :: ‹'k list ⇒ 'l mtab ⇒ nat list› where
  ‹mclass K T = moore K T (Suc (length T)) (replicate (length T) 0)›

lemma mstable_mclass: ‹mstable K T (mclass K T)›
  unfolding mclass_def by (rule mstable_moore)

section ‹From a partition to a grammar›

type_synonym cell = ‹nat × nat option list›

definition ralts :: ‹('n, 't) is_cfg ⇒ ('n, 't, 'q) prec_aut ⇒ ('q ⇒ 'n) ⇒ 'q ⇒ nat list› where
  ‹ralts G A nt q = filter (λl. fst (iprods G ! l) = nt q ∧ ok A q (iprods G ! l))
     [0..<length (iprods G)]›

lemma set_ralts: ‹l ∈ set (ralts G A nt q) ⟷
    l < length (iprods G) ∧ fst (iprods G ! l) = nt q ∧ ok A q (iprods G ! l)›
  by (auto simp: ralts_def)

definition ckid :: ‹('n, 't, 'q) prec_aut ⇒ ('q ⇒ nat) ⇒ 'q ⇒ ('n, 't) alt ⇒ nat ⇒ nat option› where
  ‹ckid A cl q p k = (case fst (snd p ! k) of Nt _ ⇒ Some (cl (step A q p k)) | Tm _ ⇒ None)›

text ‹The cover replaces the productions of a class by unit productions to
  classes of the same nonterminal whose production sets are strict subsets,
  largest first and pairwise disjoint.  This is the epsilon-introduction
  heuristic of cite‹‹Sect.~3.1.3, Fig.~11c› in "adams2017-tree-automata"›,
  which turns the product into the usual ‹Exp›/‹Term›/‹Factor› chain.›

definition ccands :: ‹(nat ⇒ cell list) ⇒ (nat ⇒ 'k) ⇒ nat list ⇒ nat ⇒ nat list› where
  ‹ccands as key C c = rev (sort_key (λb. length (as b))
     (filter (λb. b ≠ c ∧ key b = key c ∧ 2 ≤ length (as b) ∧ set (as b) ⊂ set (as c)) C))›

fun cstep :: ‹(nat ⇒ cell list) ⇒ cell list × nat list ⇒ nat ⇒ cell list × nat list› where
  ‹cstep as (left, us) b = (if set (as b) ⊆ set left
     then (filter (λa. a ∉ set (as b)) left, b # us) else (left, us))›

definition ccover :: ‹(nat ⇒ cell list) ⇒ (nat ⇒ 'k) ⇒ nat list ⇒ nat ⇒ cell list × nat list› where
  ‹ccover as key C c = foldl (cstep as) (as c, []) (ccands as key C c)›

lemma cstep_foldl:
  ‹foldl (cstep as) (l0, u0) bs = (l, u) ⟹
   set l ∪ (⋃x ∈ set u. set (as x)) = set l0 ∪ (⋃x ∈ set u0. set (as x)) ∧
   set l ⊆ set l0 ∧ set u ⊆ set u0 ∪ set bs›
proof (induction bs arbitrary: l0 u0)
  case (Cons b bs)
  show ?case
  proof (cases ‹set (as b) ⊆ set l0›)
    case True
    with Cons.prems have ‹foldl (cstep as) (filter (λa. a ∉ set (as b)) l0, b # u0) bs = (l, u)›
      by simp
    from Cons.IH[OF this] True show ?thesis by auto
  next
    case False
    with Cons.prems have ‹foldl (cstep as) (l0, u0) bs = (l, u)› by simp
    from Cons.IH[OF this] show ?thesis by auto
  qed
qed simp

definition sub :: ‹(nat ⇒ 'n') ⇒ ('n, 't) rhs ⇒ nat option list ⇒ ('n', 't) rhs› where
  ‹sub nm r ks = map2 (λ(X, i) k. (case X of Nt _ ⇒ Nt (nm (the k)) | Tm t ⇒ Tm t, i)) r ks›

lemma length_sub: ‹length ks = length r ⟹ length (sub nm r ks) = length r›
  by (simp add: sub_def)

lemma sub_nth: ‹length ks = length r ⟹ k < length r ⟹ sub nm r ks ! k =
    (case fst (r ! k) of Nt _ ⇒ Nt (nm (the (ks ! k))) | Tm t ⇒ Tm t, snd (r ! k))›
  by (simp add: sub_def split: prod.split)

lemma set_map_filter_id: ‹x ∈ set (List.map_filter id ks) ⟷ Some x ∈ set ks›
  by (induction ks) (auto split: option.split)

definition cnext :: ‹(nat ⇒ cell list) ⇒ (nat ⇒ 'k) ⇒ nat list ⇒ nat ⇒ nat list› where
  ‹cnext as key C c = (let cv = ccover as key C c in
     snd cv @ concat (map (λa. List.map_filter id (snd a)) (fst cv)))›

definition cprods :: ‹('n × ('n, 't) rhs) list ⇒ (nat ⇒ cell list) ⇒ (nat ⇒ 'k) ⇒ nat list ⇒
    (nat ⇒ 'n') ⇒ nat list ⇒ ('n' × ('n', 't) rhs) list› where
  ‹cprods P as key C nm L = concat (map (λc. let cv = ccover as key C c in
     map (λa. (nm c, sub nm (snd (P ! fst a)) (snd a))) (fst cv) @
     map (λu. (nm c, [(Nt (nm u), Eq)])) (snd cv)) L)›

locale class_gram0 =
  fixes G :: ‹('n, 't) is_cfg› and A :: ‹('n, 't, 'q) prec_aut› and nt :: ‹'q ⇒ 'n›
    and q0 :: 'q and ss :: ‹'q set› and cl :: ‹'q ⇒ nat›
    and as :: ‹nat ⇒ cell list› and key :: ‹nat ⇒ 'k› and C :: ‹nat list›
    and nm :: ‹nat ⇒ 'n'› and orig :: ‹'n' ⇒ 'n›
  assumes q0: ‹q0 ∈ ss› ‹nt q0 = istart G›
    and no_self: ‹no_self_unit G›
    and kids: ‹q ∈ ss ⟹ p ∈ set (iprods G) ⟹ fst p = nt q ⟹ ok A q p ⟹
        k < length (snd p) ⟹ fst (snd p ! k) = Nt x ⟹
        step A q p k ∈ ss ∧ nt (step A q p k) = x›
    and as_spec: ‹q ∈ ss ⟹ as (cl q) = map (λl. (l, map (ckid A cl q (iprods G ! l))
        [0..<length (snd (iprods G ! l))])) (ralts G A nt q)›
    and C_spec: ‹set C = cl ` ss›
    and orig_nm: ‹orig (nm (cl q)) = nt q ∨ q ∉ ss›
    and key_nm: ‹c ∈ set C ⟹ d ∈ set C ⟹ key c = key d ⟹ orig (nm c) = orig (nm d)›
    and key_nm': ‹c ∈ set C ⟹ d ∈ set C ⟹ orig (nm c) = orig (nm d) ⟹ key c = key d›
    and nm_inj: ‹inj_on nm (set C)›
begin

abbreviation ‹lft c ≡ fst (ccover as key C c)›
abbreviation ‹uss c ≡ snd (ccover as key C c)›

lemma cover:
  ‹set (as c) = set (lft c) ∪ (⋃u ∈ set (uss c). set (as u))›
  ‹set (lft c) ⊆ set (as c)›
  ‹u ∈ set (uss c) ⟹ u ∈ set C ∧ key u = key c ∧ set (as u) ⊂ set (as c)›
proof -
  obtain l v where e: ‹ccover as key C c = (l, v)› by fastforce
  from cstep_foldl[OF e[unfolded ccover_def]]
  show ‹set (as c) = set (lft c) ∪ (⋃u ∈ set (uss c). set (as u))›
    ‹set (lft c) ⊆ set (as c)›
    ‹u ∈ set (uss c) ⟹ u ∈ set C ∧ key u = key c ∧ set (as u) ⊂ set (as c)›
    by (auto simp: e ccands_def)
qed

lemma as_mem:
  assumes ‹q ∈ ss› ‹(l, ks) ∈ set (as (cl q))›
  shows ‹l < length (iprods G)› ‹fst (iprods G ! l) = nt q› ‹ok A q (iprods G ! l)›
    ‹ks = map (ckid A cl q (iprods G ! l)) [0..<length (snd (iprods G ! l))]›
  using assms by (auto simp: as_spec set_ralts)

lemma alt_kid:
  assumes q: ‹q ∈ ss› and a: ‹(l, ks) ∈ set (as (cl q))›
    and k: ‹k < length (snd (iprods G ! l))› and x: ‹fst (snd (iprods G ! l) ! k) = Nt x›
  shows ‹ks ! k = Some (cl (step A q (iprods G ! l) k))›
    ‹step A q (iprods G ! l) k ∈ ss› ‹nt (step A q (iprods G ! l) k) = x›
proof -
  note m = as_mem[OF q a]
  show ‹ks ! k = Some (cl (step A q (iprods G ! l) k))›
    using k x by (simp add: m(4) ckid_def)
  from kids[OF q nth_mem[OF m(1)] m(2) m(3) k x]
  show ‹step A q (iprods G ! l) k ∈ ss› ‹nt (step A q (iprods G ! l) k) = x› by auto
qed

lemma length_kids:
  assumes ‹q ∈ ss› ‹(l, ks) ∈ set (as (cl q))›
  shows ‹length ks = length (snd (iprods G ! l))›
  by (subst as_mem(4)[OF assms]) simp

lemma urhs_sub:
  assumes q: ‹q ∈ ss› and a: ‹(l, ks) ∈ set (as (cl q))›
  shows ‹urhs orig (sub nm (snd (iprods G ! l)) ks) = snd (iprods G ! l)›
proof (rule nth_equalityI)
  note len = length_kids[OF q a]
  show ‹length (urhs orig (sub nm (snd (iprods G ! l)) ks)) = length (snd (iprods G ! l))›
    by (simp add: urhs_def length_sub[OF len])
  fix k assume ‹k < length (urhs orig (sub nm (snd (iprods G ! l)) ks))›
  then have k: ‹k < length (snd (iprods G ! l))› by (simp add: urhs_def length_sub[OF len])
  show ‹urhs orig (sub nm (snd (iprods G ! l)) ks) ! k = snd (iprods G ! l) ! k›
  proof (cases ‹fst (snd (iprods G ! l) ! k)›)
    case (Nt x)
    note kid = alt_kid[OF q a k Nt]
    have ‹orig (nm (cl (step A q (iprods G ! l) k))) = x› using orig_nm kid(2,3) by metis
    with k Nt kid(1) show ?thesis
      by (cases ‹snd (iprods G ! l) ! k›)
        (simp add: urhs_def length_sub[OF len] sub_nth[OF len])
  next
    case (Tm t)
    with k show ?thesis
      by (cases ‹snd (iprods G ! l) ! k›)
        (simp add: urhs_def length_sub[OF len] sub_nth[OF len])
  qed
qed

lemma cnext_in_C:
  assumes ‹c ∈ set C› ‹x ∈ set (cnext as key C c)›
  shows ‹x ∈ set C›
proof -
  from assms(1) C_spec obtain q where q: ‹q ∈ ss› ‹c = cl q› by auto
  from assms(2) consider ‹x ∈ set (uss c)› | l ks where ‹(l, ks) ∈ set (lft c)› ‹Some x ∈ set ks›
    by (fastforce simp: cnext_def Let_def set_map_filter_id)
  then show ?thesis
  proof cases
    case 1
    then show ?thesis using cover(3) by blast
  next
    case 2
    then have a: ‹(l, ks) ∈ set (as (cl q))› using cover(2) q(2) by blast
    from 2(2) obtain k where k: ‹k < length ks› ‹ks ! k = Some x› by (auto simp: in_set_conv_nth)
    have k': ‹k < length (snd (iprods G ! l))› using k length_kids[OF q(1) a] by simp
    show ?thesis
    proof (cases ‹fst (snd (iprods G ! l) ! k)›)
      case (Nt y)
      note kid = alt_kid[OF q(1) a k' Nt]
      with k C_spec show ?thesis by auto
    next
      case (Tm t)
      with k k' show ?thesis by (simp add: as_mem(4)[OF q(1) a] ckid_def)
    qed
  qed
qed

end

locale class_gram = class_gram0 +
  fixes L :: ‹nat list›
  assumes L_sub: ‹set L ⊆ set C› and L_start: ‹cl q0 ∈ set L›
    and L_closed: ‹c ∈ set L ⟹ x ∈ set (cnext as key C c) ⟹ x ∈ set L›
begin

definition G' where
  ‹G' = ⦇iprods = cprods (iprods G) as key C nm L, istart = nm (cl q0), istart_ind = istart_ind G⦈›

lemma mem_G':
  ‹(m, r) ∈ set (iprods G') ⟷ (∃c ∈ set L. m = nm c ∧
     ((∃l ks. (l, ks) ∈ set (lft c) ∧ r = sub nm (snd (iprods G ! l)) ks) ∨
      (∃u ∈ set (uss c). r = [(Nt (nm u), Eq)])))›
proof -
  have a: ‹(m, r) ∈ (λa. (nm c, sub nm (snd (iprods G ! fst a)) (snd a))) ` set (lft c) ⟷
      m = nm c ∧ (∃l ks. (l, ks) ∈ set (lft c) ∧ r = sub nm (snd (iprods G ! l)) ks)› for c
    by force
  have b: ‹(m, r) ∈ (λu. (nm c, [(Nt (nm u), Eq)])) ` set (uss c) ⟷
      m = nm c ∧ (∃u ∈ set (uss c). r = [(Nt (nm u), Eq)])› for c
    by force
  show ?thesis by (simp add: G'_def cprods_def Let_def a b) blast
qed

lemma L_C: ‹c ∈ set L ⟹ c ∈ set C›
  using L_sub by blast

lemma left_not_unit:
  assumes c: ‹c ∈ set L› and a: ‹(l, ks) ∈ set (lft c)›
    and u: ‹unit_alt orig (nm c, sub nm (snd (iprods G ! l)) ks) m›
  shows False
proof -
  from L_C[OF c] C_spec obtain q where q: ‹q ∈ ss› ‹c = cl q› by auto
  have a': ‹(l, ks) ∈ set (as (cl q))› using a cover(2) q(2) by blast
  have r: ‹sub nm (snd (iprods G ! l)) ks = [(Nt m, Eq)]› and om: ‹orig m = orig (nm c)›
    using u by (auto simp: unit_alt_def)
  have ‹snd (iprods G ! l) = [(Nt (orig m), Eq)]›
    using urhs_sub[OF q(1) a'] by (simp add: r urhs_def)
  moreover have ‹fst (iprods G ! l) = orig m›
    using as_mem(2)[OF q(1) a'] om orig_nm q by metis
  ultimately have ‹(orig m, [(Nt (orig m), Eq)]) ∈ set (iprods G)›
    using nth_mem[OF as_mem(1)[OF q(1) a']] by (metis prod.collapse)
  with no_self show False by (simp add: no_self_unit_def)
qed

lemma unit_uss:
  assumes c: ‹c ∈ set L› and u: ‹units G' orig (nm c) m›
  shows ‹∃x ∈ set (uss c). m = nm x›
proof -
  from u obtain r where r: ‹(nm c, r) ∈ set (iprods G')› ‹unit_alt orig (nm c, r) m›
    by (auto simp: units_def)
  from r(1) obtain d where d: ‹d ∈ set L› ‹nm c = nm d›
    ‹(∃l ks. (l, ks) ∈ set (lft d) ∧ r = sub nm (snd (iprods G ! l)) ks) ∨
      (∃x ∈ set (uss d). r = [(Nt (nm x), Eq)])›
    by (auto simp: mem_G')
  have ‹c = d› using inj_onD[OF nm_inj d(2) L_C[OF c] L_C[OF d(1)]] .
  from d(3) show ?thesis
  proof (elim disjE exE conjE bexE)
    fix l ks assume ‹(l, ks) ∈ set (lft d)› ‹r = sub nm (snd (iprods G ! l)) ks›
    with c r(2) left_not_unit[of c l ks m] ‹c = d› show ?thesis by simp
  next
    fix x assume ‹x ∈ set (uss d)› ‹r = [(Nt (nm x), Eq)]›
    with r(2) ‹c = d› show ?thesis by (auto simp: unit_alt_def)
  qed
qed

lemma uss_L: ‹c ∈ set L ⟹ u ∈ set (uss c) ⟹ u ∈ set L›
  by (rule L_closed) (auto simp: cnext_def Let_def)

lemma uss_units:
  assumes ‹c ∈ set L› ‹u ∈ set (uss c)›
  shows ‹units G' orig (nm c) (nm u)›
proof -
  have ‹(nm c, [(Nt (nm u), Eq)]) ∈ set (iprods G')›
    using assms by (auto simp: mem_G')
  moreover have ‹orig (nm u) = orig (nm c)›
  proof -
    note cu = cover(3)[OF assms(2)]
    from cu have ‹u ∈ set C› ‹key u = key c› by auto
    from key_nm[OF this(1) L_C[OF assms(1)] this(2)] show ?thesis .
  qed
  ultimately show ?thesis by (auto simp: units_def unit_alt_def)
qed

lemma units_star_sub:
  assumes ‹units_star G' orig (nm c) m› ‹c ∈ set L›
  shows ‹∃d ∈ set L. m = nm d ∧ set (as d) ⊆ set (as c) ∧ orig (nm d) = orig (nm c)›
  using assms(1)
proof (induction rule: rtranclp_induct)
  case base
  from assms(2) show ?case by blast
next
  case (step y z)
  then obtain d where d: ‹d ∈ set L› ‹y = nm d› ‹set (as d) ⊆ set (as c)›
    ‹orig (nm d) = orig (nm c)› by blast
  with step(2) obtain x where x: ‹x ∈ set (uss d)› ‹z = nm x› using unit_uss by blast
  note cu = cover(3)[OF x(1)]
  have h1: ‹set (as x) ⊆ set (as d)› using cu by auto
  have h2: ‹orig (nm x) = orig (nm d)› using key_nm[of x d] cu L_C[OF d(1)] by blast
  show ?case using uss_L[OF d(1) x(1)] x(2) h1 h2 d(3,4)
    by (intro bexI[of _ x]) auto
qed

lemma chain:
  assumes ‹c ∈ set L› ‹a ∈ set (as c)›
  shows ‹∃m ∈ set L. units_star G' orig (nm c) (nm m) ∧ a ∈ set (lft m)›
  using assms
proof (induction ‹card (set (as c))› arbitrary: c rule: less_induct)
  case less
  from less.prems(2) cover(1)[of c] consider ‹a ∈ set (lft c)› | u where ‹u ∈ set (uss c)› ‹a ∈ set (as u)›
    by blast
  then show ?case
  proof cases
    case 1
    with less.prems(1) show ?thesis by blast
  next
    case 2
    have ‹card (set (as u)) < card (set (as c))›
      using cover(3)[OF 2(1)] by (simp add: psubset_card_mono)
    from less.hyps[OF this uss_L[OF less.prems(1) 2(1)] 2(2)] uss_units[OF less.prems(1) 2(1)]
    show ?thesis by (meson converse_rtranclp_into_rtranclp)
  qed
qed

theorem restrict_ok: ‹restrict_ok G A q0 {q ∈ ss. cl q ∈ set L} (λq. nm (cl q)) G' orig›
proof
  show ‹q0 ∈ {q ∈ ss. cl q ∈ set L}› using q0 L_start by simp
  show ‹nm (cl q0) = istart G'› by (simp add: G'_def)
  show ‹orig (istart G') = istart G› using orig_nm[of q0] q0 by (simp add: G'_def)
  show ‹istart_ind G' = istart_ind G› by (simp add: G'_def)
  show ‹no_self_unit G› by (rule no_self)
next
  fix q n r k x
  assume q: ‹q ∈ {q ∈ ss. cl q ∈ set L}› and p: ‹(n, r) ∈ set (iprods G)›
    and n: ‹n = orig (nm (cl q))› and o: ‹ok A q (n, r)› and k: ‹k < length r› and x: ‹fst (r ! k) = Nt x›
  have nq: ‹n = nt q› using n q orig_nm[of q] by simp
  from kids[of q ‹(n, r)› k x] q p nq o k x
  have s: ‹step A q (n, r) k ∈ ss› ‹nt (step A q (n, r) k) = x› by auto
  from p obtain l where l: ‹l < length (iprods G)› ‹iprods G ! l = (n, r)› by (auto simp: in_set_conv_nth)
  have ‹l ∈ set (ralts G A nt q)› using l nq o by (simp add: set_ralts)
  then obtain ks where a: ‹(l, ks) ∈ set (as (cl q))› using q by (fastforce simp: as_spec)
  from chain[OF _ a] q obtain m where m: ‹m ∈ set L› ‹(l, ks) ∈ set (lft m)› by auto
  have ‹ks ! k = Some (cl (step A q (n, r) k))› ‹k < length ks›
    using alt_kid(1)[of q l ks k x] length_kids[of q l ks] q a k x l by auto
  then have ‹Some (cl (step A q (n, r) k)) ∈ set ks› by (metis nth_mem)
  with m have ‹cl (step A q (n, r) k) ∈ set L›
    by (intro L_closed[OF m(1)]) (force simp: cnext_def Let_def set_map_filter_id)
  with s orig_nm[of ‹step A q (n, r) k›]
  show ‹step A q (n, r) k ∈ {q ∈ ss. cl q ∈ set L} ∧ orig (nm (cl (step A q (n, r) k))) = x› by auto
next
  fix q m r'
  assume q: ‹q ∈ {q ∈ ss. cl q ∈ set L}› and us: ‹units_star G' orig (nm (cl q)) m›
    and p: ‹(m, r') ∈ set (iprods G')› and nu: ‹¬ (∃c. unit_alt orig (m, r') c)›
  from units_star_sub[OF us] q obtain d where d: ‹d ∈ set L› ‹m = nm d›
    ‹set (as d) ⊆ set (as (cl q))› ‹orig (nm d) = orig (nm (cl q))› by auto
  from p d(2) obtain e where e: ‹e ∈ set L› ‹nm d = nm e›
    ‹(∃l ks. (l, ks) ∈ set (lft e) ∧ r' = sub nm (snd (iprods G ! l)) ks) ∨
      (∃x ∈ set (uss e). r' = [(Nt (nm x), Eq)])› by (auto simp: mem_G')
  have de: ‹d = e› using inj_onD[OF nm_inj e(2) L_C[OF d(1)] L_C[OF e(1)]] .
  have ‹∃l ks. (l, ks) ∈ set (lft d) ∧ r' = sub nm (snd (iprods G ! l)) ks›
  proof (rule ccontr)
    assume ‹∄l ks. (l, ks) ∈ set (lft d) ∧ r' = sub nm (snd (iprods G ! l)) ks›
    with e(3) de obtain x where x: ‹x ∈ set (uss d)› ‹r' = [(Nt (nm x), Eq)]› by auto
    have ‹orig (nm x) = orig (nm d)›
      using key_nm[of x d] L_C[OF d(1)] cover(3)[OF x(1)] by blast
    with nu x(2) d(2) show False by (auto simp: unit_alt_def)
  qed
  then obtain l ks where a: ‹(l, ks) ∈ set (lft d)› and r': ‹r' = sub nm (snd (iprods G ! l)) ks› by blast
  have q': ‹q ∈ ss› using q by simp
  have a': ‹(l, ks) ∈ set (as (cl q))› using a cover(2) d(3) by blast
  note mm = as_mem[OF q' a']
  have om: ‹orig m = nt q› using d(2,4) orig_nm[of q] q' by simp
  have pl: ‹(orig m, urhs orig r') = iprods G ! l›
    using mm(2) om urhs_sub[OF q' a'] by (simp add: r' prod_eq_iff)
  have ‹c = nm (cl (step A q (iprods G ! l) k))›
    if k: ‹k < length r'› and c: ‹fst (r' ! k) = Nt c› for k c
  proof -
    note len = length_kids[OF q' a']
    have k': ‹k < length (snd (iprods G ! l))› using k by (simp add: r' length_sub[OF len])
    show ?thesis
    proof (cases ‹fst (snd (iprods G ! l) ! k)›)
      case (Nt y)
      with c k' show ?thesis by (simp add: r' sub_nth[OF len k'] alt_kid(1)[OF q' a' k' Nt])
    next
      case (Tm t)
      with c k' show ?thesis by (simp add: r' sub_nth[OF len k'])
    qed
  qed
  then show ‹(orig m, urhs orig r') ∈ set (iprods G) ∧ ok A q (orig m, urhs orig r') ∧
      (∀k c. k < length r' ⟶ fst (r' ! k) = Nt c ⟶
         c = nm (cl (step A q (orig m, urhs orig r') k)))›
    using pl mm(1,3) by (simp add: nth_mem[OF mm(1), folded pl])
next
  fix q r
  assume q: ‹q ∈ {q ∈ ss. cl q ∈ set L}› and p: ‹(orig (nm (cl q)), r) ∈ set (iprods G)›
    and o: ‹ok A q (orig (nm (cl q)), r)›
  have q': ‹q ∈ ss› using q by simp
  have nq: ‹orig (nm (cl q)) = nt q› using q' orig_nm[of q] by simp
  from p obtain l where l: ‹l < length (iprods G)› ‹iprods G ! l = (nt q, r)›
    by (auto simp: nq in_set_conv_nth)
  have ‹l ∈ set (ralts G A nt q)› using l o nq by (simp add: set_ralts)
  then obtain ks where a: ‹(l, ks) ∈ set (as (cl q))› using q' by (fastforce simp: as_spec)
  from chain[OF _ a] q obtain m where m: ‹m ∈ set L› ‹units_star G' orig (nm (cl q)) (nm m)›
    ‹(l, ks) ∈ set (lft m)› by auto
  note len = length_kids[OF q' a]
  let ?r' = ‹sub nm r ks›
  have rr: ‹r = snd (iprods G ! l)› using l(2) by simp
  have ‹(nm m, ?r') ∈ set (iprods G')› unfolding mem_G' using m(1,3) rr by blast
  moreover have ‹orig (nm m) = orig (nm (cl q))› using units_star_sub[OF m(2)] q m(1)
    by (auto dest: inj_onD[OF nm_inj] L_C)
  moreover have ‹urhs orig ?r' = r› using urhs_sub[OF q' a] l(2) by simp
  moreover have ‹c = nm (cl (step A q (orig (nm (cl q)), r) k))›
    if k: ‹k < length ?r'› and c: ‹fst (?r' ! k) = Nt c› for k c
  proof -
    have len': ‹length ks = length r› using len l(2) by simp
    have k': ‹k < length r› using k by (simp add: length_sub[OF len'])
    have k'': ‹k < length (snd (iprods G ! l))› using k' l(2) by simp
    show ?thesis
    proof (cases ‹fst (r ! k)›)
      case (Nt y)
      have ‹ks ! k = Some (cl (step A q (iprods G ! l) k))›
        using alt_kid(1)[OF q' a k''] Nt l(2) by simp
      with c k' Nt show ?thesis by (simp add: sub_nth[OF len' k'] l(2) nq)
    next
      case (Tm t)
      with c k' show ?thesis by (simp add: sub_nth[OF len' k'])
    qed
  qed
  ultimately show ‹∃m r'. units_star G' orig (nm (cl q)) m ∧ (m, r') ∈ set (iprods G') ∧
      orig m = orig (nm (cl q)) ∧ urhs orig r' = r ∧
      (∀k c. k < length r' ⟶ fst (r' ! k) = Nt c ⟶
         c = nm (cl (step A q (orig (nm (cl q)), r) k)))›
    using m(2) by blast
qed

end

section ‹The whole construction›

text ‹‹restrict_gen› chains the steps: reachable states, classes,
  reachable classes, covered productions; the new names are the original
  name, ‹#› and the class number.›

lemma reach_within:
  assumes S: ‹finite S› ‹x ∈ S› ‹⋀y. y ∈ S ⟹ set (f y) ⊆ S›
  shows ‹(steps f)* `` {x} ⊆ S› ‹finite ((steps f)* `` {x})›
proof -
  have ‹(x, y) ∈ (steps f)* ⟹ y ∈ S› for y
    by (induction rule: rtrancl_induct) (use S in ‹auto simp: steps_def›)
  then show *: ‹(steps f)* `` {x} ⊆ S› by blast
  from finite_subset[OF * S(1)] show ‹finite ((steps f)* `` {x})› .
qed

fun enc :: ‹nat ⇒ string› where
  ‹enc n = (if n = 0 then [] else (if even n then CHR ''a'' else CHR ''b'') # enc (n div 2))›

declare enc.simps[simp del]

lemma enc_inj: ‹enc n = enc m ⟹ n = m›
proof (induction n arbitrary: m rule: enc.induct)
  case (1 n)
  show ?case
  proof (cases ‹n = 0›)
    case True
    with "1.prems" show ?thesis by (subst (asm) (1 2) enc.simps) (auto split: if_splits)
  next
    case False
    with "1.prems" have m: ‹m ≠ 0› by (subst (asm) (1 2) enc.simps) (auto split: if_splits)
    from "1.prems" False m have e: ‹even n ⟷ even m› and t: ‹enc (n div 2) = enc (m div 2)›
      by (subst (asm) (1 2) enc.simps; auto split: if_splits)+
    have ‹n div 2 = m div 2› using "1.IH"[OF False t] .
    with e show ?thesis by presburger
  qed
qed

lemma enc_hash: ‹CHR ''#'' ∉ set (enc n)›
proof (induction n rule: enc.induct)
  case (1 n)
  then show ?case by (subst enc.simps) auto
qed

definition orig_name :: ‹string ⇒ string› where
  ‹orig_name s = (case dropWhile (λc. c ≠ CHR ''#'') (rev s) of
     [] ⇒ s | _ # t ⇒ rev t)›

lemma orig_name_cut: ‹orig_name (k @ CHR ''#'' # enc c) = k›
proof -
  have ‹dropWhile (λc. c ≠ CHR ''#'') (rev (enc c) @ CHR ''#'' # rev k) = CHR ''#'' # rev k›
  proof -
    have ‹∀x ∈ set (enc c). x ≠ CHR ''#''› using enc_hash[of c] by blast
    then show ?thesis by (simp add: dropWhile_append3)
  qed
  then show ?thesis by (simp add: orig_name_def)
qed

definition rsucc :: ‹('n, 't) is_cfg ⇒ ('n, 't, 'q) prec_aut ⇒ ('q ⇒ 'n) ⇒ 'q ⇒ 'q list› where
  ‹rsucc G A nt q = concat (map (λl. concat (map (λk.
       case fst (snd (iprods G ! l) ! k) of Nt _ ⇒ [step A q (iprods G ! l) k] | Tm _ ⇒ [])
     [0..<length (snd (iprods G ! l))])) (ralts G A nt q))›

definition rtab :: ‹('n, 't) is_cfg ⇒ ('n, 't, 'q) prec_aut ⇒ ('q ⇒ 'n) ⇒ ('q ⇒ nat) ⇒ 'q list ⇒ nat mtab› where
  ‹rtab G A nt ix ss = map (λq. map (λl. (l, map (ckid A ix q (iprods G ! l))
     [0..<length (snd (iprods G ! l))])) (ralts G A nt q)) ss›

definition restrict_gen ::
  ‹(string, 't) is_cfg ⇒ (string, 't, 'q) prec_aut ⇒ ('q ⇒ string) ⇒ 'q ⇒ (string, 't) is_cfg› where
  ‹restrict_gen G A nt q0 =
    (let ss = reach (rsucc G A nt) q0;
         ix = (λq. first_ix q ss);
         T = rtab G A nt ix ss;
         K = map nt ss;
         π = mclass K T;
         cl = (λq. π ! ix q);
         AT = map (λi. snd (sg K T π i)) [0..<length T];
         as = (λc. AT ! first_ix c π);
         key = (λc. K ! first_ix c π);
         C = remdups (map cl ss);
         nm = (λc. key c @ CHR ''#'' # enc c);
         L = reach (cnext as key C) (cl q0)
     in ⦇iprods = cprods (iprods G) as key C nm L, istart = nm (cl q0), istart_ind = istart_ind G⦈)›

theorem restrict_gen_correct:
  fixes G :: ‹(string, 't) is_cfg› and A :: ‹(string, 't, 'q) prec_aut›
  assumes fin: ‹finite ((steps (rsucc G A nt))* `` {q0})›
    and start: ‹nt q0 = istart G›
    and no_self: ‹no_self_unit G›
    and nt_step: ‹⋀q p k x. p ∈ set (iprods G) ⟹ fst p = nt q ⟹ ok A q p ⟹
        k < length (snd p) ⟹ fst (snd p ! k) = Nt x ⟹ nt (step A q p k) = x›
  shows ‹∃Q (cls :: 'q ⇒ string). restrict_ok G A q0 Q cls (restrict_gen G A nt q0) orig_name›
proof -
  define ss where ‹ss = reach (rsucc G A nt) q0›
  define ix where ‹ix = (λq. first_ix q ss)›
  define T where ‹T = rtab G A nt ix ss›
  define K where ‹K = map nt ss›
  define π where ‹π = mclass K T›
  define cl where ‹cl = (λq. π ! ix q)›
  define AT where ‹AT = map (λi. snd (sg K T π i)) [0..<length T]›
  define as where ‹as = (λc. AT ! first_ix c π)›
  define key where ‹key = (λc. K ! first_ix c π)›
  define C where ‹C = remdups (map cl ss)›
  define nm where ‹nm = (λc. key c @ CHR ''#'' # enc c)›
  note st = reach_spec[OF fin, folded ss_def]
  have st_def: ‹length π = length T›
    ‹⋀i j. i < length T ⟹ j < length T ⟹ π ! i = π ! j ⟹ sg K T π i = sg K T π j›
    using mstable_mclass[of K T] unfolding mstable_def π_def by blast+
  have lenT: ‹length T = length ss› by (simp add: T_def rtab_def)
  have ixs: ‹ix q < length ss› ‹ss ! ix q = q› if ‹q ∈ set ss› for q
    using first_ix_nth[OF that] by (auto simp: ix_def)
  have rep: ‹first_ix (cl q) π < length T ∧ π ! first_ix (cl q) π = cl q› if ‹q ∈ set ss› for q
  proof -
    have ‹cl q ∈ set π› unfolding cl_def using ixs[OF that] st_def(1) lenT by simp
    from first_ix_nth[OF this] show ?thesis using st_def(1) by simp
  qed
  have sg_eq: ‹sg K T π (first_ix (cl q) π) = sg K T π (ix q)› if q: ‹q ∈ set ss› for q
    using st_def(2)[of ‹first_ix (cl q) π› ‹ix q›] rep[OF q] ixs[OF q] lenT by (simp add: cl_def)
  have key_cl: ‹key (cl q) = nt q› if q: ‹q ∈ set ss› for q
  proof -
    have ‹K ! first_ix (cl q) π = K ! ix q› using sg_eq[OF q] by (simp add: sg_def)
    also have ‹… = nt q› using ixs[OF q] by (simp add: K_def)
    finally show ?thesis by (simp add: key_def)
  qed
  have kid_eq: ‹map_option ((!) π) (ckid A ix q p k) = ckid A cl q p k› for q p k
    by (simp add: ckid_def cl_def split: sym.split)
  have as_cl: ‹as (cl q) = map (λl. (l, map (ckid A cl q (iprods G ! l))
      [0..<length (snd (iprods G ! l))])) (ralts G A nt q)› if q: ‹q ∈ set ss› for q
  proof -
    have ‹as (cl q) = snd (sg K T π (first_ix (cl q) π))›
      using rep[OF q] by (simp add: as_def AT_def)
    also have ‹… = snd (sg K T π (ix q))› by (simp only: sg_eq[OF q])
    also have ‹… = map (λ(l, ks). (l, map (map_option ((!) π)) ks))
        (map (λl. (l, map (ckid A ix q (iprods G ! l)) [0..<length (snd (iprods G ! l))])) (ralts G A nt q))›
      using ixs[OF q] by (simp add: sg_def T_def rtab_def)
    also have ‹… = map (λl. (l, map (ckid A cl q (iprods G ! l))
        [0..<length (snd (iprods G ! l))])) (ralts G A nt q)›
      by (simp add: comp_def kid_eq)
    finally show ?thesis .
  qed
  have kids: ‹step A q p k ∈ set ss ∧ nt (step A q p k) = x›
    if q: ‹q ∈ set ss› and p: ‹p ∈ set (iprods G)› ‹fst p = nt q› ‹ok A q p›
      and k: ‹k < length (snd p)› ‹fst (snd p ! k) = Nt x› for q p k x
  proof -
    from p(1) obtain l where l: ‹l < length (iprods G)› ‹iprods G ! l = p› by (auto simp: in_set_conv_nth)
    have ‹l ∈ set (ralts G A nt q)› using l p by (simp add: set_ralts)
    with l k have ‹step A q p k ∈ set (rsucc G A nt q)›
      by (force simp: rsucc_def)
    from st(2)[OF q this] nt_step[OF p k] show ?thesis by blast
  qed
  have orig_nm: ‹orig_name (nm c) = key c› for c
    by (simp add: nm_def orig_name_cut)
  have nm_inj: ‹inj_on nm (set C)›
  proof (rule inj_onI)
    fix c d assume e: ‹nm c = nm d›
    with orig_nm have ‹key c = key d› by metis
    with e have ‹enc c = enc d› by (simp add: nm_def)
    then show ‹c = d› by (rule enc_inj)
  qed
  have set_C: ‹set C = cl ` set ss› by (simp add: C_def)
  interpret g0: class_gram0 G A nt q0 ‹set ss› cl as key C nm orig_name
  proof
    show ‹q0 ∈ set ss› by (rule st(1))
    show ‹nt q0 = istart G› by (rule start)
    show ‹no_self_unit G› by (rule no_self)
    show ‹orig_name (nm (cl q)) = nt q ∨ q ∉ set ss› for q
      using orig_nm key_cl by metis
    show ‹inj_on nm (set C)› by (rule nm_inj)
    show ‹set C = cl ` set ss› by (rule set_C)
    show ‹orig_name (nm c) = orig_name (nm d)› if ‹key c = key d› for c d
      using that by (simp add: orig_nm)
    show ‹key c = key d› if ‹orig_name (nm c) = orig_name (nm d)› for c d
      using that by (simp add: orig_nm)
  qed (use kids as_cl in auto)
  define L where ‹L = reach (cnext as key C) (cl q0)›
  have C_in: ‹cl q0 ∈ set C› using st(1) set_C by auto
  have rw: ‹(steps (cnext as key C))* `` {cl q0} ⊆ set C›
    ‹finite ((steps (cnext as key C))* `` {cl q0})›
    using reach_within[of ‹set C› ‹cl q0› ‹cnext as key C›] C_in g0.cnext_in_C by auto
  note lr = reach_spec[OF rw(2), folded L_def]
  interpret g: class_gram G A nt q0 ‹set ss› cl as key C nm orig_name L
    by unfold_locales (use lr rw(1) in auto)
  have ‹restrict_gen G A nt q0 = g.G'›
    unfolding restrict_gen_def g.G'_def Let_def
    by (simp only: L_def nm_def C_def key_def as_def AT_def cl_def π_def K_def T_def ix_def ss_def)
  with g.restrict_ok show ?thesis by metis
qed

end