theory Re1
imports "Main"
begin
section {* Sequential Composition of Sets *}
definition
Sequ :: "string set \<Rightarrow> string set \<Rightarrow> string set" ("_ ;; _" [100,100] 100)
where
"A ;; B = {s1 @ s2 | s1 s2. s1 \<in> A \<and> s2 \<in> B}"
text {* Two Simple Properties about Sequential Composition *}
lemma seq_empty [simp]:
shows "A ;; {[]} = A"
and "{[]} ;; A = A"
by (simp_all add: Sequ_def)
lemma seq_null [simp]:
shows "A ;; {} = {}"
and "{} ;; A = {}"
by (simp_all add: Sequ_def)
section {* Regular Expressions *}
datatype rexp =
NULL
| EMPTY
| CHAR char
| SEQ rexp rexp
| ALT rexp rexp
section {* Semantics of Regular Expressions *}
fun
L :: "rexp \<Rightarrow> string set"
where
"L (NULL) = {}"
| "L (EMPTY) = {[]}"
| "L (CHAR c) = {[c]}"
| "L (SEQ r1 r2) = (L r1) ;; (L r2)"
| "L (ALT r1 r2) = (L r1) \<union> (L r2)"
fun
nullable :: "rexp \<Rightarrow> bool"
where
"nullable (NULL) = False"
| "nullable (EMPTY) = True"
| "nullable (CHAR c) = False"
| "nullable (ALT r1 r2) = (nullable r1 \<or> nullable r2)"
| "nullable (SEQ r1 r2) = (nullable r1 \<and> nullable r2)"
lemma nullable_correctness:
shows "nullable r \<longleftrightarrow> [] \<in> (L r)"
apply (induct r)
apply(auto simp add: Sequ_def)
done
section {* Values *}
datatype val =
Void
| Char char
| Seq val val
| Right val
| Left val
section {* The string behind a value *}
fun flat :: "val \<Rightarrow> string"
where
"flat(Void) = []"
| "flat(Char c) = [c]"
| "flat(Left v) = flat(v)"
| "flat(Right v) = flat(v)"
| "flat(Seq v1 v2) = flat(v1) @ flat(v2)"
fun flats :: "val \<Rightarrow> string list"
where
"flats(Void) = [[]]"
| "flats(Char c) = [[c]]"
| "flats(Left v) = flats(v)"
| "flats(Right v) = flats(v)"
| "flats(Seq v1 v2) = (flats v1) @ (flats v2)"
section {* Relation between values and regular expressions *}
inductive Prf :: "val \<Rightarrow> rexp \<Rightarrow> bool" ("\<turnstile> _ : _" [100, 100] 100)
where
"\<lbrakk>\<turnstile> v1 : r1; \<turnstile> v2 : r2\<rbrakk> \<Longrightarrow> \<turnstile> Seq v1 v2 : SEQ r1 r2"
| "\<turnstile> v1 : r1 \<Longrightarrow> \<turnstile> Left v1 : ALT r1 r2"
| "\<turnstile> v2 : r2 \<Longrightarrow> \<turnstile> Right v2 : ALT r1 r2"
| "\<turnstile> Void : EMPTY"
| "\<turnstile> Char c : CHAR c"
fun mkeps :: "rexp \<Rightarrow> val"
where
"mkeps(EMPTY) = Void"
| "mkeps(SEQ r1 r2) = Seq (mkeps r1) (mkeps r2)"
| "mkeps(ALT r1 r2) = (if nullable(r1) then Left (mkeps r1) else Right (mkeps r2))"
lemma mkeps_nullable:
assumes "nullable(r)" shows "\<turnstile> mkeps r : r"
using assms
apply(induct rule: nullable.induct)
apply(auto intro: Prf.intros)
done
lemma mkeps_flat:
assumes "nullable(r)" shows "flat (mkeps r) = []"
using assms
apply(induct rule: nullable.induct)
apply(auto)
done
text {*
The value mkeps returns is always the correct POSIX
value.
*}
lemma Prf_flat_L:
assumes "\<turnstile> v : r" shows "flat v \<in> L r"
using assms
apply(induct)
apply(auto simp add: Sequ_def)
done
lemma L_flat_Prf:
"L(r) = {flat v | v. \<turnstile> v : r}"
apply(induct r)
apply(auto dest: Prf_flat_L simp add: Sequ_def)
apply (metis Prf.intros(4) flat.simps(1))
apply (metis Prf.intros(5) flat.simps(2))
apply (metis Prf.intros(1) flat.simps(5))
apply (metis Prf.intros(2) flat.simps(3))
apply (metis Prf.intros(3) flat.simps(4))
apply(erule Prf.cases)
apply(auto)
done
definition prefix :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubset> _" [100, 100] 100)
where
"s1 \<sqsubset> s2 \<equiv> \<exists>s3. s1 @ s3 = s2"
section {* Ordering of values *}
inductive ValOrd :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ \<succ>_ _" [100, 100, 100] 100)
where
"v2 \<succ>r2 v2' \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1 v2')"
| "\<lbrakk>v1 \<succ>r1 v1'; v1 \<noteq> v1'\<rbrakk> \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1' v2')"
| "length (flat v1) \<ge> length (flat v2) \<Longrightarrow> (Left v1) \<succ>(ALT r1 r2) (Right v2)"
| "length (flat v2) > length (flat v1) \<Longrightarrow> (Right v2) \<succ>(ALT r1 r2) (Left v1)"
| "v2 \<succ>r2 v2' \<Longrightarrow> (Right v2) \<succ>(ALT r1 r2) (Right v2')"
| "v1 \<succ>r1 v1' \<Longrightarrow> (Left v1) \<succ>(ALT r1 r2) (Left v1')"
| "Void \<succ>EMPTY Void"
| "(Char c) \<succ>(CHAR c) (Char c)"
section {* The ordering is reflexive *}
lemma ValOrd_refl:
assumes "\<turnstile> v : r"
shows "v \<succ>r v"
using assms
apply(induct)
apply(auto intro: ValOrd.intros)
done
section {* Posix definition *}
definition POSIX :: "val \<Rightarrow> rexp \<Rightarrow> bool"
where
"POSIX v r \<equiv> (\<turnstile> v : r \<and> (\<forall>v'. (\<turnstile> v' : r \<and> flat v = flat v') \<longrightarrow> v \<succ>r v'))"
(*
an alternative definition: might cause problems
with theorem mkeps_POSIX
*)
(*
definition POSIX2 :: "val \<Rightarrow> rexp \<Rightarrow> bool"
where
"POSIX2 v r \<equiv> \<turnstile> v : r \<and> (\<forall>v'. \<turnstile> v' : r \<longrightarrow> v \<succ>r v')"
*)
(*
definition POSIX3 :: "val \<Rightarrow> rexp \<Rightarrow> bool"
where
"POSIX3 v r \<equiv> \<turnstile> v : r \<and> (\<forall>v'. (\<turnstile> v' : r \<and> length (flat v') \<le> length(flat v)) \<longrightarrow> v \<succ>r v')"
*)
lemma POSIX_SEQ1:
assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2"
shows "POSIX v1 r1"
using assms
unfolding POSIX_def
apply(auto)
apply(drule_tac x="Seq v' v2" in spec)
apply(simp)
apply(erule impE)
apply(rule Prf.intros)
apply(simp)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)
apply(clarify)
by (metis ValOrd_refl)
lemma POSIX_SEQ2:
assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2"
shows "POSIX v2 r2"
using assms
unfolding POSIX_def
apply(auto)
apply(drule_tac x="Seq v1 v'" in spec)
apply(simp)
apply(erule impE)
apply(rule Prf.intros)
apply(simp)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)
done
lemma POSIX_ALT2:
assumes "POSIX (Left v1) (ALT r1 r2)"
shows "POSIX v1 r1"
using assms
unfolding POSIX_def
apply(auto)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(drule_tac x="Left v'" in spec)
apply(simp)
apply(drule mp)
apply(rule Prf.intros)
apply(auto)
apply(erule ValOrd.cases)
apply(simp_all)
done
lemma POSIX_ALT1a:
assumes "POSIX (Right v2) (ALT r1 r2)"
shows "POSIX v2 r2"
using assms
unfolding POSIX_def
apply(auto)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(drule_tac x="Right v'" in spec)
apply(simp)
apply(drule mp)
apply(rule Prf.intros)
apply(auto)
apply(erule ValOrd.cases)
apply(simp_all)
done
lemma POSIX_ALT1b:
assumes "POSIX (Right v2) (ALT r1 r2)"
shows "(\<forall>v'. (\<turnstile> v' : r2 \<and> flat v' = flat v2) \<longrightarrow> v2 \<succ>r2 v')"
using assms
apply(drule_tac POSIX_ALT1a)
unfolding POSIX_def
apply(auto)
done
lemma POSIX_ALT_I1:
assumes "POSIX v1 r1"
shows "POSIX (Left v1) (ALT r1 r2)"
using assms
unfolding POSIX_def
apply(auto)
apply (metis Prf.intros(2))
apply(rotate_tac 2)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)
apply(rule ValOrd.intros)
apply(auto)
apply(rule ValOrd.intros)
by simp
lemma POSIX_ALT_I2:
assumes "POSIX v2 r2" "\<forall>v'. \<turnstile> v' : r1 \<longrightarrow> length (flat v2) > length (flat v')"
shows "POSIX (Right v2) (ALT r1 r2)"
using assms
unfolding POSIX_def
apply(auto)
apply (metis Prf.intros)
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)
apply(rule ValOrd.intros)
apply metis
done
lemma mkeps_POSIX:
assumes "nullable r"
shows "POSIX (mkeps r) r"
using assms
apply(induct r)
apply(auto)[1]
apply(simp add: POSIX_def)
apply(auto)[1]
apply (metis Prf.intros(4))
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros)
apply(simp add: POSIX_def)
apply(auto)[1]
apply(simp add: POSIX_def)
apply(auto)[1]
apply (metis mkeps.simps(2) mkeps_nullable nullable.simps(5))
apply(rotate_tac 6)
apply(erule Prf.cases)
apply(simp_all)[5]
apply (simp add: mkeps_flat)
apply(case_tac "mkeps r1a = v1")
apply(simp)
apply (metis ValOrd.intros(1))
apply (rule ValOrd.intros(2))
apply metis
apply(simp)
apply(simp)
apply(erule disjE)
apply(simp)
apply (metis POSIX_ALT_I1)
apply(auto)
apply (metis POSIX_ALT_I1)
apply(simp add: POSIX_def)
apply(auto)[1]
apply (metis Prf.intros(3))
apply(rotate_tac 5)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: mkeps_flat)
apply(auto)[1]
apply (metis Prf_flat_L nullable_correctness)
apply(rule ValOrd.intros)
by metis
section {* Derivatives *}
fun
der :: "char \<Rightarrow> rexp \<Rightarrow> rexp"
where
"der c (NULL) = NULL"
| "der c (EMPTY) = NULL"
| "der c (CHAR c') = (if c = c' then EMPTY else NULL)"
| "der c (ALT r1 r2) = ALT (der c r1) (der c r2)"
| "der c (SEQ r1 r2) =
(if nullable r1
then ALT (SEQ (der c r1) r2) (der c r2)
else SEQ (der c r1) r2)"
fun
ders :: "string \<Rightarrow> rexp \<Rightarrow> rexp"
where
"ders [] r = r"
| "ders (c # s) r = ders s (der c r)"
section {* Injection function *}
fun injval :: "rexp \<Rightarrow> char \<Rightarrow> val \<Rightarrow> val"
where
"injval (CHAR d) c Void = Char d"
| "injval (ALT r1 r2) c (Left v1) = Left(injval r1 c v1)"
| "injval (ALT r1 r2) c (Right v2) = Right(injval r2 c v2)"
| "injval (SEQ r1 r2) c (Seq v1 v2) = Seq (injval r1 c v1) v2"
| "injval (SEQ r1 r2) c (Left (Seq v1 v2)) = Seq (injval r1 c v1) v2"
| "injval (SEQ r1 r2) c (Right v2) = Seq (mkeps r1) (injval r2 c v2)"
section {* Projection function *}
fun projval :: "rexp \<Rightarrow> char \<Rightarrow> val \<Rightarrow> val"
where
"projval (CHAR d) c _ = Void"
| "projval (ALT r1 r2) c (Left v1) = Left(projval r1 c v1)"
| "projval (ALT r1 r2) c (Right v2) = Right(projval r2 c v2)"
| "projval (SEQ r1 r2) c (Seq v1 v2) =
(if flat v1 = [] then Right(projval r2 c v2)
else if nullable r1 then Left (Seq (projval r1 c v1) v2)
else Seq (projval r1 c v1) v2)"
text {*
Injection value is related to r
*}
lemma v3:
assumes "\<turnstile> v : der c r" shows "\<turnstile> (injval r c v) : r"
using assms
apply(induct arbitrary: v rule: der.induct)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(case_tac "c = c'")
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis Prf.intros(5))
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis Prf.intros(2))
apply (metis Prf.intros(3))
apply(simp)
apply(case_tac "nullable r1")
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply (metis Prf.intros(1))
apply(auto)[1]
apply (metis Prf.intros(1) mkeps_nullable)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(rule Prf.intros)
apply(auto)[2]
done
lemma v3_proj:
assumes "\<turnstile> v : r" and "\<exists>s. (flat v) = c # s"
shows "\<turnstile> (projval r c v) : der c r"
using assms
apply(induct rule: Prf.induct)
prefer 4
apply(simp)
prefer 4
apply(simp)
apply (metis Prf.intros(4))
prefer 2
apply(simp)
apply (metis Prf.intros(2))
prefer 2
apply(simp)
apply (metis Prf.intros(3))
apply(auto)
apply(rule Prf.intros)
apply(simp)
apply (metis Prf_flat_L nullable_correctness)
apply(rule Prf.intros)
apply(rule Prf.intros)
apply (metis Cons_eq_append_conv)
apply(simp)
apply(rule Prf.intros)
apply (metis Cons_eq_append_conv)
apply(simp)
done
text {*
The string behind the injection value is an added c
*}
lemma v4:
assumes "\<turnstile> v : der c r" shows "flat (injval r c v) = c # (flat v)"
using assms
apply(induct arbitrary: v rule: der.induct)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(case_tac "c = c'")
apply(simp)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(case_tac "nullable r1")
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply (metis mkeps_flat)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
done
lemma v4_proj:
assumes "\<turnstile> v : r" and "\<exists>s. (flat v) = c # s"
shows "c # flat (projval r c v) = flat v"
using assms
apply(induct rule: Prf.induct)
prefer 4
apply(simp)
prefer 4
apply(simp)
prefer 2
apply(simp)
prefer 2
apply(simp)
apply(auto)
by (metis Cons_eq_append_conv)
lemma v4_proj2:
assumes "\<turnstile> v : r" and "(flat v) = c # s"
shows "flat (projval r c v) = s"
using assms
by (metis list.inject v4_proj)
lemma t: "(c#xs = c#ys) \<Longrightarrow> xs = ys"
by (metis list.sel(3))
lemma t2: "(xs = ys) \<Longrightarrow> (c#xs) = (c#ys)"
by (metis)
fun zeroable where
"zeroable NULL = True"
| "zeroable EMPTY = False"
| "zeroable (CHAR c) = False"
| "zeroable (ALT r1 r2) = (zeroable r1 \<and> zeroable r2)"
| "zeroable (SEQ r1 r2) = (zeroable r1 \<or> zeroable r2)"
lemma "\<not>(nullable r) \<Longrightarrow> \<not>(\<exists>v. \<turnstile> v : r \<and> flat v = [])"
by (metis Prf_flat_L nullable_correctness)
lemma Prf_inj:
assumes "v1 \<succ>(der c r) v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r" (*"flat v1 = flat v2"*)
shows "(injval r c v1) \<succ>r (injval r c v2)"
using assms
apply(induct arbitrary: v1 v2 rule: der.induct)
(* NULL case *)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* EMPTY case *)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* CHAR case *)
apply(case_tac "c = c'")
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(rule ValOrd.intros)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* ALT case *)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(rule ValOrd.intros)
apply(subst v4)
apply(clarify)
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(subst v4)
apply(clarify)
apply(rotate_tac 2)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(rule ValOrd.intros)
apply(clarify)
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(subst v4)
apply(simp)
apply(subst v4)
apply(simp)
apply(simp)
apply(rule ValOrd.intros)
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule ValOrd.intros)
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
(* SEQ case*)
apply(simp)
apply(case_tac "nullable r1")
apply(simp)
defer
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(clarify)
apply(rule ValOrd.intros)
apply(simp)
apply(clarify)
apply(rule ValOrd.intros(2))
apply metis
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
defer
apply(erule ValOrd.cases)
apply(simp_all del: injval.simps)[8]
apply(simp)
apply(clarify)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(rule ValOrd.intros(2))
lemma POSIX_ex: "\<turnstile> v : r \<Longrightarrow> \<exists>v. POSIX v r"
apply(induct r arbitrary: v)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule_tac x="Void" in exI)
apply(simp add: POSIX_def)
apply(auto)[1]
apply (metis Prf.intros(4))
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule_tac x="Char c" in exI)
apply(simp add: POSIX_def)
apply(auto)[1]
apply (metis Prf.intros(5))
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(8))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(drule_tac x="v1" in meta_spec)
apply(drule_tac x="v2" in meta_spec)
apply(auto)[1]
defer
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply (metis POSIX_ALT_I1)
apply (metis POSIX_ALT_I1 POSIX_ALT_I2)
apply(case_tac "nullable r1a")
apply(rule_tac x="Seq (mkeps r1a) va" in exI)
apply(auto simp add: POSIX_def)[1]
apply (metis Prf.intros(1) mkeps_nullable)
apply(simp add: mkeps_flat)
apply(rotate_tac 7)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(case_tac "mkeps r1 = v1a")
apply(simp)
apply (rule ValOrd.intros(1))
apply (metis append_Nil mkeps_flat)
apply (rule ValOrd.intros(2))
apply(drule mkeps_POSIX)
apply(simp add: POSIX_def)
apply metis
apply(simp)
apply(simp)
apply(erule disjE)
apply(simp)
apply(drule_tac x="v2" in spec)
lemma POSIX_ex2: "\<turnstile> v : r \<Longrightarrow> \<exists>v. POSIX v r \<and> \<turnstile> v : r"
apply(induct r arbitrary: v)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule_tac x="Void" in exI)
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply (metis Prf.intros(4))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule_tac x="Char c" in exI)
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(8))
apply (metis Prf.intros(5))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(drule_tac x="v1" in meta_spec)
apply(drule_tac x="v2" in meta_spec)
apply(auto)[1]
apply(simp add: POSIX_def)
apply(auto)[1]
apply(rule ccontr)
apply(simp)
apply(drule_tac x="Seq v va" in spec)
apply(drule mp)
defer
apply (metis Prf.intros(1))
oops
lemma POSIX_ALT_cases:
assumes "\<turnstile> v : (ALT r1 r2)" "POSIX v (ALT r1 r2)"
shows "(\<exists>v1. v = Left v1 \<and> POSIX v1 r1) \<or> (\<exists>v2. v = Right v2 \<and> POSIX v2 r2)"
using assms
apply(erule_tac Prf.cases)
apply(simp_all)
unfolding POSIX_def
apply(auto)
apply (metis POSIX_ALT2 POSIX_def assms(2))
by (metis POSIX_ALT1b assms(2))
lemma POSIX_ALT_cases2:
assumes "POSIX v (ALT r1 r2)" "\<turnstile> v : (ALT r1 r2)"
shows "(\<exists>v1. v = Left v1 \<and> POSIX v1 r1) \<or> (\<exists>v2. v = Right v2 \<and> POSIX v2 r2)"
using assms POSIX_ALT_cases by auto
lemma Prf_flat_empty:
assumes "\<turnstile> v : r" "flat v = []"
shows "nullable r"
using assms
apply(induct)
apply(auto)
done
lemma POSIX_proj:
assumes "POSIX v r" "\<turnstile> v : r" "\<exists>s. flat v = c#s"
shows "POSIX (projval r c v) (der c r)"
using assms
apply(induct r c v arbitrary: rule: projval.induct)
defer
defer
defer
defer
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply(erule_tac [!] exE)
prefer 3
apply(frule POSIX_SEQ1)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(case_tac "flat v1 = []")
apply(subgoal_tac "nullable r1")
apply(simp)
prefer 2
apply(rule_tac v="v1" in Prf_flat_empty)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(frule POSIX_SEQ2)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(drule meta_mp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule ccontr)
apply(subgoal_tac "\<turnstile> val.Right (projval r2 c v2) : (ALT (SEQ (der c r1) r2) (der c r2))")
apply(rotate_tac 11)
apply(frule POSIX_ex)
apply(erule exE)
apply(drule POSIX_ALT_cases2)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(drule v3_proj)
apply(simp)
apply(simp)
apply(drule POSIX_ex)
apply(erule exE)
apply(frule POSIX_ALT_cases2)
apply(simp)
apply(simp)
apply(erule
prefer 2
apply(case_tac "nullable r1")
prefer 2
apply(simp)
apply(rotate_tac 1)
apply(drule meta_mp)
apply(rule POSIX_SEQ1)
apply(assumption)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rotate_tac 7)
apply(drule meta_mp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rotate_tac 7)
apply(drule meta_mp)
apply (metis Cons_eq_append_conv)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: POSIX_def)
apply(simp)
apply(simp)
apply(simp_all)[5]
apply(simp add: POSIX_def)
lemma POSIX_proj:
assumes "POSIX v r" "\<turnstile> v : r" "\<exists>s. flat v = c#s"
shows "POSIX (projval r c v) (der c r)"
using assms
apply(induct r arbitrary: c v rule: rexp.induct)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply(erule_tac [!] exE)
prefer 3
apply(frule POSIX_SEQ1)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(case_tac "flat v1 = []")
apply(subgoal_tac "nullable r1")
apply(simp)
prefer 2
apply(rule_tac v="v1" in Prf_flat_empty)
apply(erule Prf.cases)
apply(simp_all)[5]
lemma POSIX_proj:
assumes "POSIX v r" "\<turnstile> v : r" "\<exists>s. flat v = c#s"
shows "POSIX (projval r c v) (der c r)"
using assms
apply(induct r c v arbitrary: rule: projval.induct)
defer
defer
defer
defer
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply(erule_tac [!] exE)
prefer 3
apply(frule POSIX_SEQ1)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(case_tac "flat v1 = []")
apply(subgoal_tac "nullable r1")
apply(simp)
prefer 2
apply(rule_tac v="v1" in Prf_flat_empty)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(rule ccontr)
apply(drule v3_proj)
apply(simp)
apply(simp)
apply(drule POSIX_ex)
apply(erule exE)
apply(frule POSIX_ALT_cases2)
apply(simp)
apply(simp)
apply(erule
prefer 2
apply(case_tac "nullable r1")
prefer 2
apply(simp)
apply(rotate_tac 1)
apply(drule meta_mp)
apply(rule POSIX_SEQ1)
apply(assumption)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rotate_tac 7)
apply(drule meta_mp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rotate_tac 7)
apply(drule meta_mp)
apply (metis Cons_eq_append_conv)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp add: POSIX_def)
apply(simp)
apply(simp)
apply(simp_all)[5]
apply(simp add: POSIX_def)
done
(* NULL case *)
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(7))
apply(rotate_tac 4)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
prefer 2
apply(simp)
apply(frule POSIX_ALT1a)
apply(drule meta_mp)
apply(simp)
apply(drule meta_mp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule POSIX_ALT_I2)
apply(assumption)
apply(auto)[1]
thm v4_proj2
prefer 2
apply(subst (asm) (13) POSIX_def)
apply(drule_tac x="projval v2" in spec)
apply(auto)[1]
apply(drule mp)
apply(rule conjI)
apply(simp)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
prefer 2
apply(clarify)
apply(subst (asm) (2) POSIX_def)
apply (metis ValOrd.intros(5))
apply(clarify)
apply(simp)
apply(rotate_tac 3)
apply(drule_tac c="c" in t2)
apply(subst (asm) v4_proj)
apply(simp)
apply(simp)
thm contrapos_np contrapos_nn
apply(erule contrapos_np)
apply(rule ValOrd.intros)
apply(subst v4_proj2)
apply(simp)
apply(simp)
apply(subgoal_tac "\<not>(length (flat v1) < length (flat (projval r2a c v2a)))")
prefer 2
apply(erule contrapos_nn)
apply (metis nat_less_le v4_proj2)
apply(simp)
apply(blast)
thm contrapos_nn
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(rule ValOrd.intros)
apply(drule meta_mp)
apply(auto)[1]
apply (metis POSIX_ALT2 POSIX_def flat.simps(3))
apply metis
apply(clarify)
apply(rule ValOrd.intros)
apply(simp)
apply(simp add: POSIX_def)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(rule ValOrd.intros)
apply(simp)
apply(drule meta_mp)
apply(auto)[1]
apply (metis POSIX_ALT2 POSIX_def flat.simps(3))
apply metis
apply(clarify)
apply(rule ValOrd.intros)
apply(simp)
done
(* EMPTY case *)
apply(simp add: POSIX_def)
apply(auto)[1]
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(drule_tac c="c" in t2)
apply(subst (asm) v4_proj)
apply(auto)[2]
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* CHAR case *)
apply(case_tac "c = c'")
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(rule ValOrd.intros)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* ALT case *)
unfolding POSIX_def
apply(auto)
thm v4
lemma Prf_inj:
assumes "v1 \<succ>(der c r) v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r" "flat v1 = flat v2"
shows "(injval r c v1) \<succ>r (injval r c v2)"
using assms
apply(induct arbitrary: v1 v2 rule: der.induct)
(* NULL case *)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* EMPTY case *)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* CHAR case *)
apply(case_tac "c = c'")
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(rule ValOrd.intros)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
(* ALT case *)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(rule ValOrd.intros)
apply(subst v4)
apply(clarify)
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(subst v4)
apply(clarify)
apply(rotate_tac 2)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(rule ValOrd.intros)
apply(clarify)
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule ValOrd.intros)
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
(* SEQ case*)
apply(simp)
apply(case_tac "nullable r1")
defer
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(rule ValOrd.intros)
apply(simp)
apply(simp)
apply(rule ValOrd.intros(2))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
defer
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all del: injval.simps)[8]
apply(simp)
apply(clarify)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(rule ValOrd.intros(2))
done
txt {*
done
(* nullable case - unfinished *)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all del: injval.simps)[8]
apply(simp)
apply(clarify)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(simp)
apply(rule ValOrd.intros(2))
oops
*}
oops
lemma POSIX_der:
assumes "POSIX v (der c r)" "\<turnstile> v : der c r"
shows "POSIX (injval r c v) r"
using assms
unfolding POSIX_def
apply(auto)
thm v4
apply(subst (asm) v4)
apply(assumption)
apply(drule_tac x="projval r c v'" in spec)
apply(auto)
apply(rule v3_proj)
apply(simp)
apply(rule_tac x="flat v" in exI)
apply(simp)
apply(rule_tac c="c" in t)
apply(simp)
apply(subst v4_proj)
apply(simp)
apply(rule_tac x="flat v" in exI)
apply(simp)
apply(simp)
apply(simp add: Cons_eq_append_conv)
apply(auto)[1]
text {*
Injection followed by projection is the identity.
*}
lemma proj_inj_id:
assumes "\<turnstile> v : der c r"
shows "projval r c (injval r c v) = v"
using assms
apply(induct r arbitrary: c v rule: rexp.induct)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(case_tac "c = char")
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
defer
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(simp)
apply(case_tac "nullable rexp1")
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply (metis list.distinct(1) v4)
apply(auto)[1]
apply (metis mkeps_flat)
apply(auto)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)[1]
apply(simp add: v4)
done
lemma "L r \<noteq> {} \<Longrightarrow> \<exists>v. POSIX3 v r"
apply(induct r)
apply(simp)
apply(simp add: POSIX3_def)
apply(rule_tac x="Void" in exI)
apply(auto)[1]
apply (metis Prf.intros(4))
apply (metis POSIX3_def flat.simps(1) mkeps.simps(1) mkeps_POSIX3 nullable.simps(2) order_refl)
apply(simp add: POSIX3_def)
apply(rule_tac x="Char char" in exI)
apply(auto)[1]
apply (metis Prf.intros(5))
apply(erule Prf.cases)
apply(simp_all)[5]
apply (metis ValOrd.intros(8))
apply(simp add: Sequ_def)
apply(auto)[1]
apply(drule meta_mp)
apply(auto)[2]
apply(drule meta_mp)
apply(auto)[2]
apply(rule_tac x="Seq v va" in exI)
apply(simp (no_asm) add: POSIX3_def)
apply(auto)[1]
apply (metis POSIX3_def Prf.intros(1))
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
apply(case_tac "v \<succ>r1a v1")
apply(rule ValOrd.intros(2))
apply(simp)
apply(case_tac "v = v1")
apply(rule ValOrd.intros(1))
apply(simp)
apply(simp)
apply (metis ValOrd_refl)
apply(simp add: POSIX3_def)
oops
lemma "\<exists>v. POSIX v r"
apply(induct r)
apply(rule exI)
apply(simp add: POSIX_def)
apply (metis (full_types) Prf_flat_L der.simps(1) der.simps(2) der.simps(3) flat.simps(1) nullable.simps(1) nullable_correctness proj_inj_id projval.simps(1) v3 v4)
apply(rule_tac x = "Void" in exI)
apply(simp add: POSIX_def)
apply (metis POSIX_def flat.simps(1) mkeps.simps(1) mkeps_POSIX nullable.simps(2))
apply(rule_tac x = "Char char" in exI)
apply(simp add: POSIX_def)
apply(auto) [1]
apply(erule Prf.cases)
apply(simp_all) [5]
apply (metis ValOrd.intros(8))
defer
apply(auto)
apply (metis POSIX_ALT_I1)
(* maybe it is too early to instantiate this existential quantifier *)
(* potentially this is the wrong POSIX value *)
apply(case_tac "r1 = NULL")
apply(simp add: POSIX_def)
apply(auto)[1]
apply (metis L.simps(1) L.simps(4) Prf_flat_L mkeps_flat nullable.simps(1) nullable.simps(2) nullable_correctness seq_null(2))
apply(case_tac "r1 = EMPTY")
apply(rule_tac x = "Seq Void va" in exI )
apply(simp (no_asm) add: POSIX_def)
apply(auto)
apply(erule Prf.cases)
apply(simp_all)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)
apply(rule ValOrd.intros(2))
apply(rule ValOrd.intros)
apply(case_tac "\<exists>c. r1 = CHAR c")
apply(auto)
apply(rule_tac x = "Seq (Char c) va" in exI )
apply(simp (no_asm) add: POSIX_def)
apply(auto)
apply(erule Prf.cases)
apply(simp_all)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)
apply(auto)[1]
apply(rule ValOrd.intros(2))
apply(rule ValOrd.intros)
apply(case_tac "\<exists>r1a r1b. r1 = ALT r1a r1b")
apply(auto)
oops (* not sure if this can be proved by induction *)
text {*
HERE: Crucial lemma that does not go through in the sequence case.
*}
lemma v5:
assumes "\<turnstile> v : der c r" "POSIX v (der c r)"
shows "POSIX (injval r c v) r"
using assms
apply(induct arbitrary: v rule: der.induct)
(* NULL case *)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
(* EMPTY case *)
apply(simp)
apply(erule Prf.cases)
apply(simp_all)[5]
(* CHAR case *)
apply(simp)
apply(case_tac "c = c'")
apply(auto simp add: POSIX_def)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule ValOrd.intros)
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
(* base cases done *)
(* ALT case *)
apply(erule Prf.cases)
apply(simp_all)[5]
using POSIX_ALT POSIX_ALT_I1 apply blast
apply(clarify)
apply(simp)
apply(rule POSIX_ALT_I2)
apply(drule POSIX_ALT1a)
apply metis
apply(auto)[1]
apply(subst v4)
apply(assumption)
apply(simp)
apply(drule POSIX_ALT1a)
apply(rotate_tac 1)
apply(drule_tac x="v2" in meta_spec)
apply(simp)
apply(rotate_tac 4)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(rule ValOrd.intros)
apply(simp)
apply(subst (asm) v4)
apply(assumption)
apply(clarify)
thm POSIX_ALT1a POSIX_ALT1b POSIX_ALT_I2
apply(subst (asm) v4)
apply(auto simp add: POSIX_def)[1]
apply(subgoal_tac "POSIX v2 (der c r2)")
prefer 2
apply(auto simp add: POSIX_def)[1]
apply (metis POSIX_ALT1a POSIX_def flat.simps(4))
apply(frule POSIX_ALT1a)
apply(drule POSIX_ALT1b)
apply(rule POSIX_ALT_I2)
apply(rotate_tac 1)
apply(drule_tac x="v2" in meta_spec)
apply(simp)
apply(subgoal_tac "\<turnstile> Right (injval r2 c v2) : (ALT r1 r2)")
prefer 2
apply (metis Prf.intros(3) v3)
apply auto[1]
apply(subst v4)
apply(auto)[2]
apply(subst (asm) (4) POSIX_def)
apply(subst (asm) v4)
apply(drule_tac x="v2" in meta_spec)
apply(simp)
apply(auto)[2]
thm POSIX_ALT_I2
apply(rule POSIX_ALT_I2)
apply(rule ccontr)
apply(auto simp add: POSIX_def)[1]
apply(rule allI)
apply(rule impI)
apply(erule conjE)
thm POSIX_ALT_I2
apply(frule POSIX_ALT1a)
apply(drule POSIX_ALT1b)
apply(rule POSIX_ALT_I2)
apply auto[1]
apply(subst v4)
apply(auto)[2]
apply(rotate_tac 1)
apply(drule_tac x="v2" in meta_spec)
apply(simp)
apply(subst (asm) (4) POSIX_def)
apply(subst (asm) v4)
apply(auto)[2]
(* stuck in the ALT case *)