src/HOL/Datatype_Examples/Derivation_Trees/Gram_Lang.thy
changeset 63040 eb4ddd18d635
parent 61424 c3658c18b7bc
child 63167 0909deb8059b
equal deleted inserted replaced
63039:1a20fd9cf281 63040:eb4ddd18d635
   663   assume ?B thus ?A apply(intro inFr.Base) using assms by auto
   663   assume ?B thus ?A apply(intro inFr.Base) using assms by auto
   664 next
   664 next
   665   assume ?C then obtain tr where
   665   assume ?C then obtain tr where
   666   tr_tr0: "Inr tr \<in> cont tr0" and t_tr: "inFr (ns - {root tr0}) tr t"
   666   tr_tr0: "Inr tr \<in> cont tr0" and t_tr: "inFr (ns - {root tr0}) tr t"
   667   unfolding inFrr_def by auto
   667   unfolding inFrr_def by auto
   668   def tr1 \<equiv> "hsubst tr"
   668   define tr1 where "tr1 = hsubst tr"
   669   have 1: "inFr ns tr1 t" using t_tr unfolding tr1_def using inFr_hsubst_minus by auto
   669   have 1: "inFr ns tr1 t" using t_tr unfolding tr1_def using inFr_hsubst_minus by auto
   670   have "Inr tr1 \<in> cont (hsubst tr0)" unfolding tr1_def using tr_tr0 by auto
   670   have "Inr tr1 \<in> cont (hsubst tr0)" unfolding tr1_def using tr_tr0 by auto
   671   thus ?A using 1 inFr.Ind assms by (metis root_hsubst)
   671   thus ?A using 1 inFr.Ind assms by (metis root_hsubst)
   672 qed
   672 qed
   673 
   673 
   687 lemma reg_def2: "reg f tr \<longleftrightarrow> (\<forall> ns tr'. subtr ns tr' tr \<longrightarrow> tr' = f (root tr'))"
   687 lemma reg_def2: "reg f tr \<longleftrightarrow> (\<forall> ns tr'. subtr ns tr' tr \<longrightarrow> tr' = f (root tr'))"
   688 unfolding reg_def using subtr_mono by (metis subset_UNIV)
   688 unfolding reg_def using subtr_mono by (metis subset_UNIV)
   689 
   689 
   690 lemma regular_def2: "regular tr \<longleftrightarrow> (\<exists> f. reg f tr \<and> (\<forall> n. root (f n) = n))"
   690 lemma regular_def2: "regular tr \<longleftrightarrow> (\<exists> f. reg f tr \<and> (\<forall> n. root (f n) = n))"
   691 unfolding regular_def proof safe
   691 unfolding regular_def proof safe
   692   fix f assume f: "reg f tr"
   692   fix f
   693   def g \<equiv> "\<lambda> n. if inItr UNIV tr n then f n else deftr n"
   693   assume f: "reg f tr"
       
   694   define g where "g n = (if inItr UNIV tr n then f n else deftr n)" for n
   694   show "\<exists>g. reg g tr \<and> (\<forall>n. root (g n) = n)"
   695   show "\<exists>g. reg g tr \<and> (\<forall>n. root (g n) = n)"
   695   apply(rule exI[of _ g])
   696   apply(rule exI[of _ g])
   696   using f deftr_simps(1) unfolding g_def reg_def apply safe
   697   using f deftr_simps(1) unfolding g_def reg_def apply safe
   697     apply (metis (lifting) inItr.Base subtr_inItr subtr_rootL_in)
   698     apply (metis (lifting) inItr.Base subtr_inItr subtr_rootL_in)
   698     by (metis (full_types) inItr_subtr)
   699     by (metis (full_types) inItr_subtr)
  1167 (is "Lr ns n \<subseteq> {?F tns K | tns K. (n,tns) \<in> P \<and> ?\<phi> tns K}")
  1168 (is "Lr ns n \<subseteq> {?F tns K | tns K. (n,tns) \<in> P \<and> ?\<phi> tns K}")
  1168 proof safe
  1169 proof safe
  1169   fix ts assume "ts \<in> Lr ns n"
  1170   fix ts assume "ts \<in> Lr ns n"
  1170   then obtain tr where dtr: "wf tr" and r: "root tr = n" and tr: "regular tr"
  1171   then obtain tr where dtr: "wf tr" and r: "root tr = n" and tr: "regular tr"
  1171   and ts: "ts = Fr ns tr" unfolding Lr_def by auto
  1172   and ts: "ts = Fr ns tr" unfolding Lr_def by auto
  1172   def tns \<equiv> "(id \<oplus> root) ` (cont tr)"
  1173   define tns where "tns = (id \<oplus> root) ` (cont tr)"
  1173   def K \<equiv> "\<lambda> n'. Fr (ns - {n}) (subtrOf tr n')"
  1174   define K where "K n' = Fr (ns - {n}) (subtrOf tr n')" for n'
  1174   show "\<exists>tns K. ts = ?F tns K \<and> (n, tns) \<in> P \<and> ?\<phi> tns K"
  1175   show "\<exists>tns K. ts = ?F tns K \<and> (n, tns) \<in> P \<and> ?\<phi> tns K"
  1175   apply(rule exI[of _ tns], rule exI[of _ K]) proof(intro conjI allI impI)
  1176   apply(rule exI[of _ tns], rule exI[of _ K]) proof(intro conjI allI impI)
  1176     show "ts = Inl -` tns \<union> \<Union>{K n' |n'. Inr n' \<in> tns}"
  1177     show "ts = Inl -` tns \<union> \<Union>{K n' |n'. Inr n' \<in> tns}"
  1177     unfolding ts regular_Fr[OF tr n[unfolded r[symmetric]]]
  1178     unfolding ts regular_Fr[OF tr n[unfolded r[symmetric]]]
  1178     unfolding tns_def K_def r[symmetric]
  1179     unfolding tns_def K_def r[symmetric]
  1220    unfolding L_def mem_Collect_eq by auto
  1221    unfolding L_def mem_Collect_eq by auto
  1221   }
  1222   }
  1222   then obtain ftr where 0: "\<And> n'. Inr n' \<in> tns \<Longrightarrow>
  1223   then obtain ftr where 0: "\<And> n'. Inr n' \<in> tns \<Longrightarrow>
  1223   K n' = Fr (ns - {n}) (ftr n') \<and> wf (ftr n') \<and> root (ftr n') = n'"
  1224   K n' = Fr (ns - {n}) (ftr n') \<and> wf (ftr n') \<and> root (ftr n') = n'"
  1224   by metis
  1225   by metis
  1225   def tr \<equiv> "Node n ((id \<oplus> ftr) ` tns)"  def tr' \<equiv> "hsubst tr tr"
  1226   define tr where "tr = Node n ((id \<oplus> ftr) ` tns)"
       
  1227   define tr' where "tr' = hsubst tr tr"
  1226   have rtr: "root tr = n" and ctr: "cont tr = (id \<oplus> ftr) ` tns"
  1228   have rtr: "root tr = n" and ctr: "cont tr = (id \<oplus> ftr) ` tns"
  1227   unfolding tr_def by (simp, metis P cont_Node finite_imageI finite_in_P)
  1229   unfolding tr_def by (simp, metis P cont_Node finite_imageI finite_in_P)
  1228   have prtr: "prodOf tr = tns" apply(rule Inl_Inr_image_cong)
  1230   have prtr: "prodOf tr = tns" apply(rule Inl_Inr_image_cong)
  1229   unfolding ctr apply simp apply simp apply safe
  1231   unfolding ctr apply simp apply simp apply safe
  1230   using 0 unfolding image_def apply force apply simp by (metis 0 vimageI2)
  1232   using 0 unfolding image_def apply force apply simp by (metis 0 vimageI2)