Theory LR_Restrict
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 n⇩2)
then obtain t' where t': ‹wf_ptree G' t'› ‹proot t' = (Nt n⇩2, i)› ‹plain orig t' = plain orig s›
by blast
from step.hyps(1) obtain r where r: ‹(n, r) ∈ set (iprods G')› ‹r = [(Nt n⇩2, Eq)]›
‹orig n⇩2 = orig n› by (auto simp: units_def unit_alt_def)
from t'(2) obtain us where us: ‹t' = PNode n⇩2 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 r⇩1 where ‹rhs = [r⇩1]›
by (cases rhs) auto
moreover from calculation ih[of 0] have ‹fst r⇩1 = Nt m› by simp
ultimately have ‹(orig a, [(Nt (orig a), snd r⇩1)]) ∈ set (iprods G)›
using s(1) by (cases r⇩1) (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 m⇩2 j us assume a: ‹ts' = [PNode m⇩2 j us]› ‹orig m⇩2 = orig m›
with lts' obtain r⇩1 where r1: ‹r' = [r⇩1]› by (cases r') auto
with lr have l1: ‹length r = 1› by simp
have ‹P 0 (PNode m⇩2 j us)› using f[of 0] nth[of 0] a l1 by simp
then have ‹fst r⇩1 = Nt m⇩2› using r1 by (simp add: P_def)
then have ‹r = [(Nt (orig m), snd r⇩1)]› using m(4) r1 a(2)
by (cases r⇩1) (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