--- a/progs/scala/re.scala Thu Jan 29 11:23:05 2015 +0000
+++ b/progs/scala/re.scala Thu Feb 26 12:42:22 2015 +0000
@@ -43,6 +43,27 @@
def $ (r: Rexp) = RECD(s, r)
}
+def pretty(r: Rexp) : String = r match {
+ case NULL => "0"
+ case EMPTY => "e"
+ case CHAR(c) => c.toString
+ case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")"
+ case SEQ(r1, r2) => pretty(r1) ++ pretty(r2)
+ case STAR(r) => "(" ++ pretty(r) ++ ")*"
+ case RECD(x, r) => "(" ++ x ++ " : " ++ pretty(r) ++ ")"
+}
+
+def vpretty(v: Val) : String = v match {
+ case Void => "()"
+ case Chr(c) => c.toString
+ case Left(v) => "Left(" ++ vpretty(v) ++ ")"
+ case Right(v) => "Right(" ++ vpretty(v) ++ ")"
+ case Sequ(v1, v2) => vpretty(v1) ++ " ~ " ++ vpretty(v2)
+ case Stars(vs) => vs.flatMap(vpretty).mkString("[", ",", "]")
+ case Rec(x, v) => "(" ++ x ++ ":" ++ vpretty(v) ++ ")"
+}
+
+
// size of a regular expressions - for testing purposes
def size(r: Rexp) : Int = r match {
case NULL => 1
@@ -59,7 +80,8 @@
case NULL => Set()
case EMPTY => Set(Void)
case CHAR(c) => Set(Chr(c))
- case ALT(r1, r2) => values(r1) ++ values(r2)
+ case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++
+ (for (v2 <- values(r2)) yield Right(v2))
case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2)
case STAR(r) => Set(Void) ++ values(r) // to do more would cause the set to be infinite
case RECD(_, r) => values(r)
@@ -271,6 +293,29 @@
println(values(r2).mkString("\n"))
println(values(r2).toList.map(flatten).mkString("\n"))
+//Some experiments
+//================
+
+val f0 = ("ab" | "b" | "cb")
+val f1 = der('a', f0)
+val f2 = der('b', f1)
+val g2 = mkeps(f2)
+val g1 = inj(f1, 'b', g2)
+val g0 = inj(f0, 'a', g1)
+
+lex((("" | "a") ~ ("ab" | "b")), "ab".toList)
+lex((("" | "a") ~ ("b" | "ab")), "ab".toList)
+lex((("" | "a") ~ ("c" | "ab")), "ab".toList)
+
+val reg0 = ("" | "a") ~ ("ab" | "b")
+val reg1 = der('a', reg0)
+val reg2 = der('b', reg1)
+println(List(reg0, reg1, reg2).map(pretty).mkString("\n"))
+println(lexing(reg0, "ab"))
+
+val val0 = values(reg0)
+val val1 = values(reg1)
+val val2 = values(reg2)
// Two Simple Tests
--- a/thys/#Re1.thy# Thu Jan 29 11:23:05 2015 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,897 +0,0 @@
-
-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)"
-
-value "L(CHAR c)"
-value "L(SEQ(CHAR c)(CHAR b))"
-
-
-section {* Values *}
-
-datatype val =
- Void
-| Char char
-| Seq val val
-| Right val
-| Left val
-
-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"
-
-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)"
-
-value "flat(Seq(Char c)(Char b))"
-value "flat(Right(Void))"
-
-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)"
-
-value "flats(Seq(Char c)(Char b))"
-
-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 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
- "\<lbrakk>v1 = v1'; v2 \<succ>r2 v2'\<rbrakk> \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1' v2')"
-| "v1 \<succ>r1 v1' \<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
-
-lemma ValOrd_flats:
- assumes "v1 \<succ>r v2"
- shows "hd (flats v2) = hd (flats v1)"
-using assms
-apply(induct)
-apply(auto)
-oops
-
-
-section {* Posix definition *}
-
-definition POSIX :: "val \<Rightarrow> rexp \<Rightarrow> bool"
-where
- "POSIX v r \<equiv> (\<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_SEQ:
- assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2"
- shows "POSIX v1 r1 \<and> POSIX v2 r2"
-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)
-defer
-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)
-apply(clarify)
-oops (*not true*)
-
-lemma POSIX_SEQ_I:
- assumes "POSIX v1 r1" "POSIX v2 r2"
- shows "POSIX (Seq v1 v2) (SEQ r1 r2)"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(rule ValOrd.intros)
-oops (* maybe also not true *)
-
-lemma POSIX3_SEQ_I:
- assumes "POSIX3 v1 r1" "POSIX3 v2 r2"
- shows "POSIX3 (Seq v1 v2) (SEQ r1 r2)"
-using assms
-unfolding POSIX3_def
-apply(auto)
-apply (metis Prf.intros(1))
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(case_tac "v1 = v1a")
-apply(auto)
-apply (metis ValOrd.intros(1))
-apply (rule ValOrd.intros(2))
-oops
-
-lemma POSIX_ALT2:
- assumes "POSIX (Left v1) (ALT r1 r2)"
- shows "POSIX v1 r1"
-using assms
-unfolding POSIX_def
-apply(auto)
-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 POSIX2_ALT:
- assumes "POSIX2 (Left v1) (ALT r1 r2)"
- shows "POSIX2 v1 r1"
-using assms
-unfolding POSIX2_def
-apply(auto)
-oops
-
-lemma POSIX_ALT:
- assumes "POSIX (Left v1) (ALT r1 r2)"
- shows "POSIX v1 r1"
-using assms
-unfolding POSIX_def
-apply(auto)
-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 POSIX2_ALT:
- assumes "POSIX2 (Left v1) (ALT r1 r2)"
- shows "POSIX2 v1 r1"
-using assms
-apply(simp add: POSIX2_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(drule_tac x="Left v'" in spec)
-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(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 POSIX2_ALT1a:
- assumes "POSIX2 (Right v2) (ALT r1 r2)"
- shows "POSIX2 v2 r2"
-using assms
-unfolding POSIX2_def
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(drule_tac x="Right v'" in spec)
-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(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply(auto)
-apply(rule ValOrd.intros)
-by simp
-
-lemma POSIX2_ALT_I1:
- assumes "POSIX2 v1 r1"
- shows "POSIX2 (Left v1) (ALT r1 r2)"
-using assms
-unfolding POSIX2_def
-apply(auto)
-apply(rule Prf.intros)
-apply(simp)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply(auto)
-apply(rule ValOrd.intros)
-oops
-
-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(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply metis
-done
-
-
-
-
-
-section {* The Matcher *}
-
-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
-
-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 mkeps_POSIX2:
- assumes "nullable r"
- shows "POSIX2 (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX2_def)
-oops
-
-lemma mkeps_POSIX3:
- assumes "nullable r"
- shows "POSIX3 (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply (metis Prf.intros(4))
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros)
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply(simp add: POSIX3_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 (metis ValOrd.intros(2) add_leE gen_length_code(1) gen_length_def mkeps_flat)
-apply(auto)
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(2))
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(6))
-apply(auto)[1]
-apply (metis ValOrd.intros(3))
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(2))
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(6))
-apply (metis ValOrd.intros(3))
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(3))
-apply(rotate_tac 5)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis Prf_flat_L drop_0 drop_all list.size(3) mkeps_flat nullable_correctness)
-by (metis ValOrd.intros(5))
-
-
-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(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(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(2) mkeps_flat)
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(6))
-apply (simp add: ValOrd.intros(3))
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(6))
-apply (simp add: ValOrd.intros(3))
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (metis Prf_flat_L mkeps_flat nullable_correctness)
-by (simp add: ValOrd.intros(5))
-
-
-lemma mkeps_POSIX2:
- assumes "nullable r"
- shows "POSIX2 (mkeps r) r"
-using assms
-apply(induct r)
-apply(simp)
-apply(simp)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros)
-apply(simp)
-apply(simp)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(simp add: mkeps_nullable)
-apply(simp add: mkeps_nullable)
-apply(auto)[1]
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros(2))
-apply(simp)
-apply(simp only: nullable.simps)
-apply(erule disjE)
-apply(simp)
-thm POSIX2_ALT1a
-apply(rule POSIX2_ALT)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(simp add: mkeps_nullable)
-oops
-
-
-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
-
-text {*
- The string behin 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
-
-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)
-
-
-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)
-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(auto simp add: POSIX_def)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-using ValOrd.simps apply blast
-apply(auto)
-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(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 *)
--- a/thys/Re1.thy Thu Jan 29 11:23:05 2015 +0000
+++ b/thys/Re1.thy Thu Feb 26 12:42:22 2015 +0000
@@ -1,4 +1,4 @@
-
+
theory Re1
imports "Main"
begin
@@ -42,9 +42,28 @@
| "L (SEQ r1 r2) = (L r1) ;; (L r2)"
| "L (ALT r1 r2) = (L r1) \<union> (L r2)"
+<<<<<<< local
+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)"
+=======
value "L(CHAR c)"
value "L(SEQ(CHAR c)(CHAR b))"
+>>>>>>> other
+<<<<<<< local
+lemma nullable_correctness:
+ shows "nullable r \<longleftrightarrow> [] \<in> (L r)"
+apply (induct r)
+apply(auto simp add: Sequ_def)
+done
+=======
+>>>>>>> other
section {* Values *}
@@ -55,6 +74,33 @@
| 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 head :: "val \<Rightarrow> string"
+where
+ "head(Void) = []"
+| "head(Char c) = [c]"
+| "head(Left v) = head(v)"
+| "head(Right v) = head(v)"
+| "head(Seq v1 v2) = head v1"
+
+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)
@@ -65,19 +111,39 @@
| "\<turnstile> Void : EMPTY"
| "\<turnstile> Char c : CHAR c"
-section {* The string behind a value *}
-
-fun flat :: "val \<Rightarrow> string"
+fun mkeps :: "rexp \<Rightarrow> val"
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)"
+ "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
+
+<<<<<<< local
+=======
value "flat(Seq(Char c)(Char b))"
value "flat(Right(Void))"
+>>>>>>> other
+<<<<<<< local
+
+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.
+*}
+=======
fun flats :: "val \<Rightarrow> string list"
where
"flats(Void) = [[]]"
@@ -85,6 +151,7 @@
| "flats(Left v) = flats(v)"
| "flats(Right v) = flats(v)"
| "flats(Seq v1 v2) = (flats v1) @ (flats v2)"
+>>>>>>> other
value "flats(Seq(Char c)(Char b))"
@@ -116,8 +183,8 @@
inductive ValOrd :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ \<succ>_ _" [100, 100, 100] 100)
where
- "\<lbrakk>v1 = v1'; v2 \<succ>r2 v2'\<rbrakk> \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1' v2')"
-| "v1 \<succ>r1 v1' \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1' v2')"
+ "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')"
@@ -136,38 +203,32 @@
apply(auto intro: ValOrd.intros)
done
-lemma ValOrd_flats:
- assumes "v1 \<succ>r v2"
- shows "hd (flats v2) = hd (flats v1)"
-using assms
-apply(induct)
-apply(auto)
-oops
-
-
section {* Posix definition *}
definition POSIX :: "val \<Rightarrow> rexp \<Rightarrow> bool"
where
- "POSIX v r \<equiv> (\<forall>v'. (\<turnstile> v' : r \<and> flat v = flat v') \<longrightarrow> v \<succ>r v')"
+ "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_SEQ:
+lemma POSIX_SEQ1:
assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2"
- shows "POSIX v1 r1 \<and> POSIX v2 r2"
+ shows "POSIX v1 r1"
using assms
unfolding POSIX_def
apply(auto)
@@ -180,7 +241,14 @@
apply(erule ValOrd.cases)
apply(simp_all)
apply(clarify)
-defer
+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)
@@ -189,38 +257,7 @@
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)
-apply(clarify)
-oops (*not true*)
-
-lemma POSIX_SEQ_I:
- assumes "POSIX v1 r1" "POSIX v2 r2"
- shows "POSIX (Seq v1 v2) (SEQ r1 r2)"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(rule ValOrd.intros)
-oops (* maybe also not true *)
-
-lemma POSIX3_SEQ_I:
- assumes "POSIX3 v1 r1" "POSIX3 v2 r2"
- shows "POSIX3 (Seq v1 v2) (SEQ r1 r2)"
-using assms
-unfolding POSIX3_def
-apply(auto)
-apply (metis Prf.intros(1))
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(case_tac "v1 = v1a")
-apply(auto)
-apply (metis ValOrd.intros(1))
-apply (rule ValOrd.intros(2))
-oops
+done
lemma POSIX_ALT2:
assumes "POSIX (Left v1) (ALT r1 r2)"
@@ -228,6 +265,8 @@
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)
@@ -237,52 +276,14 @@
apply(simp_all)
done
-lemma POSIX2_ALT:
- assumes "POSIX2 (Left v1) (ALT r1 r2)"
- shows "POSIX2 v1 r1"
-using assms
-unfolding POSIX2_def
-apply(auto)
-oops
-
-lemma POSIX_ALT:
- assumes "POSIX (Left v1) (ALT r1 r2)"
- shows "POSIX v1 r1"
-using assms
-unfolding POSIX_def
-apply(auto)
-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 POSIX2_ALT:
- assumes "POSIX2 (Left v1) (ALT r1 r2)"
- shows "POSIX2 v1 r1"
-using assms
-apply(simp add: POSIX2_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(drule_tac x="Left v'" in spec)
-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)
@@ -292,23 +293,6 @@
apply(simp_all)
done
-lemma POSIX2_ALT1a:
- assumes "POSIX2 (Right v2) (ALT r1 r2)"
- shows "POSIX2 v2 r2"
-using assms
-unfolding POSIX2_def
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(drule_tac x="Right v'" in spec)
-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')"
@@ -324,7 +308,8 @@
using assms
unfolding POSIX_def
apply(auto)
-apply(rotate_tac 3)
+apply (metis Prf.intros(2))
+apply(rotate_tac 2)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(auto)
@@ -333,22 +318,6 @@
apply(rule ValOrd.intros)
by simp
-lemma POSIX2_ALT_I1:
- assumes "POSIX2 v1 r1"
- shows "POSIX2 (Left v1) (ALT r1 r2)"
-using assms
-unfolding POSIX2_def
-apply(auto)
-apply(rule Prf.intros)
-apply(simp)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply(auto)
-apply(rule ValOrd.intros)
-oops
lemma POSIX_ALT_I2:
assumes "POSIX v2 r2" "\<forall>v'. \<turnstile> v' : r1 \<longrightarrow> length (flat v2) > length (flat v')"
@@ -356,6 +325,7 @@
using assms
unfolding POSIX_def
apply(auto)
+apply (metis Prf.intros)
apply(rotate_tac 3)
apply(erule Prf.cases)
apply(simp_all)[5]
@@ -364,108 +334,6 @@
apply metis
done
-
-
-section {* The Matcher *}
-
-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
-
-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 mkeps_POSIX2:
- assumes "nullable r"
- shows "POSIX2 (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX2_def)
-oops
-
-lemma mkeps_POSIX3:
- assumes "nullable r"
- shows "POSIX3 (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply (metis Prf.intros(4))
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros)
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply(simp add: POSIX3_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 (metis ValOrd.intros(2) add_leE gen_length_code(1) gen_length_def mkeps_flat)
-apply(auto)
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(2))
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(6))
-apply(auto)[1]
-apply (metis ValOrd.intros(3))
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(2))
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(6))
-apply (metis ValOrd.intros(3))
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(3))
-apply(rotate_tac 5)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis Prf_flat_L drop_0 drop_all list.size(3) mkeps_flat nullable_correctness)
-by (metis ValOrd.intros(5))
-
-
lemma mkeps_POSIX:
assumes "nullable r"
shows "POSIX (mkeps r) r"
@@ -474,77 +342,42 @@
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(simp)
apply(auto)[1]
apply(simp add: POSIX_def)
apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(2) mkeps_flat)
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(6))
-apply (simp add: ValOrd.intros(3))
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(6))
-apply (simp add: ValOrd.intros(3))
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (metis Prf_flat_L mkeps_flat nullable_correctness)
-by (simp add: ValOrd.intros(5))
-
-
-lemma mkeps_POSIX2:
- assumes "nullable r"
- shows "POSIX2 (mkeps r) r"
-using assms
-apply(induct r)
-apply(simp)
-apply(simp)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros)
-apply(simp)
-apply(simp)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(simp add: mkeps_nullable)
-apply(simp add: mkeps_nullable)
-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(rule ValOrd.intros(2))
+apply (simp add: mkeps_flat)
+apply(case_tac "mkeps r1a = v1")
apply(simp)
-apply(simp only: nullable.simps)
+apply (metis ValOrd.intros(1))
+apply (rule ValOrd.intros(2))
+apply metis
+apply(simp)
+apply(simp)
apply(erule disjE)
apply(simp)
-thm POSIX2_ALT1a
-apply(rule POSIX2_ALT)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(simp add: mkeps_nullable)
-oops
+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 *}
@@ -578,6 +411,7 @@
| "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"
@@ -729,175 +563,35 @@
using assms
by (metis list.inject v4_proj)
-lemma t: "(c#xs = c#ys) \<Longrightarrow> xs = ys"
-by (metis list.sel(3))
-
-lemma Prf_proj:
- assumes "v1 \<succ>r v2" "\<turnstile> v1 : r" "\<turnstile> v2 : r" "\<exists>s. (flat v1) = c # s" "\<exists>s. (flat v2) = c # s"
- shows "(projval r c v1) \<succ>(der c r) (projval r c v2)"
-using assms
-apply(induct arbitrary: v1 v2 rule: der.induct)
-apply(simp)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(case_tac "c = c'")
-apply(simp)
-apply (metis ValOrd.intros(7))
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(simp)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(erule Prf.cases)
-apply(simp_all)[5]
+lemma injval_inj: "inj_on (injval r c) {v. \<turnstile> v : der c r}"
+apply(induct c r rule: der.induct)
+unfolding inj_on_def
+apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
-apply(clarify)
-apply(rule ValOrd.intros)
-apply(subst v4_proj2)
-apply(simp)
-apply(simp)
-apply(subst v4_proj2)
-apply(simp)
-apply(simp)
-apply(simp)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
-apply(clarify)
-apply(rule ValOrd.intros)
-apply(subst v4_proj2)
-apply(simp)
-apply(simp)
-apply(subst v4_proj2)
-apply(simp)
-apply(simp)
-apply(simp)
-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 metis
-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 metis
-apply(clarify)
-apply(simp)
-apply(auto)
-defer
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
apply(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
-apply(clarify)
-apply(simp)
-apply (metis Prf_flat_L nullable_correctness)
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(auto)[1]
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
-apply(clarify)
-apply (metis Prf_flat_L nullable_correctness)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply (metis Prf_flat_L nullable_correctness)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply (metis Prf_flat_L nullable_correctness)
-apply(erule Prf.cases)
-apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
-apply(clarify)
-apply(rule ValOrd.intros(2))
-apply (metis append_Cons list.inject neq_Nil_conv)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(auto)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(auto)[1]
-apply(rule ValOrd.intros)
-apply metis
-apply(clarify)
-apply(rule ValOrd.intros)
-
-apply(rule ValOrd.intros)
-apply(simp)
-apply(simp)
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)
-defer
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(simp add: append_eq_Cons_conv)
-apply(clarify)
-apply(rule ValOrd.intros)
-apply(simp)
-apply(subst v4_proj2)
-apply(simp)
-apply(simp)
-apply(subst v4_proj2)
-apply(simp)
-apply(simp)
-
-apply(simp)
-
-apply (metis Prf_flat_L nullable_correctness)
-
-
-
-
-apply(rule ValOrd.intros(2))
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(clarify)
apply(erule Prf.cases)
apply(simp_all)[5]
apply(erule Prf.cases)
@@ -906,18 +600,144 @@
apply(erule Prf.cases)
apply(simp_all)[5]
apply(clarify)
+apply (metis list.distinct(1) mkeps_flat v4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rotate_tac 6)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis list.distinct(1) mkeps_flat v4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+done
+
+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 proj_inj_id:
+ assumes "\<turnstile> v : der c r"
+ shows "projval r c (injval r c v) = v"
+using assms
+apply(induct c r 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(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 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
+ assumes "\<turnstile> v : der c r" "flat v \<noteq> []"
+ shows "injval r c v \<succ>r mkeps r"
+using assms
+apply(induct c r arbitrary: v rule: der.induct)
+apply(simp_all)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(case_tac "c = c'")
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply (metis ValOrd.intros(6))
+apply(clarify)
+apply (metis ValOrd.intros(4) drop_0 drop_all le_add2 list.distinct(1) list.size(3) mkeps_flat monoid_add_class.add.right_neutral nat_less_le v4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(simp)
+defer
+apply(rule ValOrd.intros)
+apply metis
+apply(case_tac "nullable r1")
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+defer
+apply(clarify)
+apply(rule ValOrd.intros)
+apply metis
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+defer
+apply(subst mkeps_flat)
+oops
+*)
lemma Prf_inj:
- assumes "v1 \<succ>(der c r) v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r"
+ 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)
@@ -926,6 +746,7 @@
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
+(* ALT case *)
apply(simp)
apply(erule ValOrd.cases)
apply(simp_all)[8]
@@ -942,15 +763,18 @@
apply(simp_all)[5]
apply(simp)
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(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)
@@ -964,6 +788,657 @@
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
+using injval_inj
+apply(simp add: inj_on_def)
+apply metis
+(* SEQ nullable case *)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(rule ValOrd.intros(1))
+apply(simp)
+apply(rule ValOrd.intros(2))
+apply metis
+using injval_inj
+apply(simp add: inj_on_def)
+apply metis
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(simp)
+apply(rule ValOrd.intros(2))
+prefer 2
+apply (metis list.distinct(1) mkeps_flat v4)
+defer
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rotate_tac 6)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(simp)
+apply(rule ValOrd.intros(2))
+prefer 2
+apply (metis list.distinct(1) mkeps_flat v4)
+defer
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(rule ValOrd.intros(1))
+apply(metis)
+apply(drule_tac x="v1" in meta_spec)
+apply(rotate_tac 7)
+apply(drule_tac x="projval r1 c (mkeps r1)" in meta_spec)
+apply(drule meta_mp)
+
+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
@@ -984,10 +1459,39 @@
apply(simp_all)[5]
apply(erule Prf.cases)
apply(simp_all)[5]
+apply(clarify)
+defer
apply(simp)
apply(erule ValOrd.cases)
-apply(simp_all)[8]
+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)
@@ -997,15 +1501,10 @@
apply(simp_all)[5]
apply(clarify)
apply(simp)
-apply(case_tac "injval r1 c v1 = mkeps r1")
-apply(rule ValOrd.intros(1))
-apply(simp)
-apply (metis impossible_Cons le_add2 list.size(3) mkeps_flat monoid_add_class.add.right_neutral v4)
apply(rule ValOrd.intros(2))
-
-apply(rotate_tac 1)
-apply(drule meta_mp)
-apply(rule
+oops
+*}
+oops
lemma POSIX_der:
assumes "POSIX v (der c r)" "\<turnstile> v : der c r"
@@ -1013,10 +1512,10 @@
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(drule mp)
apply(auto)
apply(rule v3_proj)
apply(simp)
--- a/thys/Test.txt Thu Jan 29 11:23:05 2015 +0000
+++ b/thys/Test.txt Thu Feb 26 12:42:22 2015 +0000
@@ -1,1 +1,7 @@
+<<<<<<< local
+test2
+=======
test
+test file
+
+>>>>>>> other
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/thys/Test.txt~ Thu Feb 26 12:42:22 2015 +0000
@@ -0,0 +1,1 @@
+test
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/thys/new test Thu Feb 26 12:42:22 2015 +0000
@@ -0,0 +1,1 @@
+ssh://fahad@talisker.inf.kcl.ac.uk//Users/urbanc/HGREPOS/lexing
Binary file thys/notes.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/thys/notes.tex Thu Feb 26 12:42:22 2015 +0000
@@ -0,0 +1,355 @@
+\documentclass[11pt]{article}
+\usepackage[left]{lineno}
+\usepackage{amsmath}
+
+\begin{document}
+%%\linenumbers
+
+\noindent
+We already proved that
+
+\[
+\text{If}\;nullable(r)\;\text{then}\;POSIX\;(mkeps\; r)\;r
+\]
+
+\noindent
+holds. This is essentially the ``base case'' for the
+correctness proof of the algorithm. For the ``induction
+case'' we need the following main theorem, which we are
+currently after:
+
+\begin{center}
+\begin{tabular}{lll}
+If & (*) & $POSIX\;v\;(der\;c\;r)$ and $\vdash v : der\;c\;r$\\
+then & & $POSIX\;(inj\;r\;c\;v)\;r$
+\end{tabular}
+\end{center}
+
+\noindent
+That means a POSIX value $v$ is still $POSIX$ after injection.
+I am not sure whether this theorem is actually true in this
+full generality. Maybe it requires some restrictions.
+
+If we unfold the $POSIX$ definition in the then-part, we
+arrive at
+
+\[
+\forall v'.\;
+\text{if}\;\vdash v' : r\; \text{and} \;|inj\;r\;c\;v| = |v'|\;
+\text{then}\; |inj\;r\;c\;v| \succ_r v'
+\]
+
+\noindent
+which is what we need to prove assuming the if-part (*) in the
+theorem above. Since this is a universally quantified formula,
+we just need to fix a $v'$. We can then prove the implication
+by assuming
+
+\[
+\text{(a)}\;\;\vdash v' : r\;\; \text{and} \;\;
+\text{(b)}\;\;inj\;r\;c\;v = |v'|
+\]
+
+\noindent
+and our goal is
+
+\[
+(goal)\;\;inj\;r\;c\;v \succ_r v'
+\]
+
+\noindent
+There are already two lemmas proved that can transform
+the assumptions (a) and (b) into
+
+\[
+\text{(a*)}\;\;\vdash proj\;r\;c\;v' : der\;c\;r\;\; \text{and} \;\;
+\text{(b*)}\;\;c\,\#\,|v| = |v'|
+\]
+
+\noindent
+Another lemma shows that
+
+\[
+|v'| = c\,\#\,|proj\;r\;c\;v|
+\]
+
+\noindent
+Using (b*) we can therefore infer
+
+\[
+\text{(b**)}\;\;|v| = |proj\;r\;c\;v|
+\]
+
+\noindent
+The main idea of the proof is now a simple instantiation
+of the assumption $POSIX\;v\;(der\;c\;r)$. If we unfold
+the $POSIX$ definition, we get
+
+\[
+\forall v'.\;
+\text{if}\;\vdash v' : der\;c\;r\; \text{and} \;|v| = |v'|\;
+\text{then}\; v \succ_{der\;c\;r}\; v'
+\]
+
+\noindent
+We can instantiate this $v'$ with $proj\;r\;c\;v'$ and can use
+(a*) and (b**) in order to infer
+
+\[
+v \succ_{der\;c\;r}\; proj\;r\;c\;v'
+\]
+
+\noindent
+The point of the side-lemma below is that we can ``add'' an
+$inj$ to both sides to obtain
+
+\[
+inj\;r\;c\;v \succ_r\; inj\;r\;c\;(proj\;r\;c\;v')
+\]
+
+\noindent Finally there is already a lemma proved that shows
+that an injection and projection is the identity, meaning
+
+\[
+inj\;r\;c\;(proj\;r\;c\;v') = v'
+\]
+
+\noindent
+With this we have shown our goal (pending a proof of the side-lemma
+next).
+
+
+\subsection*{Side-Lemma}
+
+A side-lemma needed for the theorem above which might be true, but can also be false, is as follows:
+
+\begin{center}
+\begin{tabular}{lll}
+If & (1) & $v_1 \succ_{der\;c\;r} v_2$,\\
+ & (2) & $\vdash v_1 : der\;c\;r$, and\\
+ & (3) & $\vdash v_2 : der\;c\;r$ holds,\\
+then & & $inj\;r\;c\;v_1 \succ_r inj\;r\;c\;v_2$ also holds.
+\end{tabular}
+\end{center}
+
+\noindent It essentially states that if one value $v_1$ is
+bigger than $v_2$ then this ordering is preserved under
+injections. This is proved by induction (on the definition of
+$der$\ldots this is very similar to an induction on $r$).
+\bigskip
+
+\noindent
+The case that is still unproved is the sequence case where we
+assume $r = r_1\cdot r_2$ and also $r_1$ being nullable.
+The derivative $der\;c\;r$ is then
+
+\begin{center}
+$der\;c\;r = ((der\;c\;r_1) \cdot r_2) + (der\;c\;r_2)$
+\end{center}
+
+\noindent
+or without the parentheses
+
+\begin{center}
+$der\;c\;r = (der\;c\;r_1) \cdot r_2 + der\;c\;r_2$
+\end{center}
+
+\noindent
+In this case the assumptions are
+
+\begin{center}
+\begin{tabular}{ll}
+(a) & $v_1 \succ_{(der\;c\;r_1) \cdot r_2 + der\;c\;r_2} v_2$\\
+(b) & $\vdash v_1 : (der\;c\;r_1) \cdot r_2 + der\;c\;r_2$\\
+(c) & $\vdash v_2 : (der\;c\;r_1) \cdot r_2 + der\;c\;r_2$\\
+(d) & $nullable(r_1)$
+\end{tabular}
+\end{center}
+
+\noindent
+The induction hypotheses are
+
+\begin{center}
+\begin{tabular}{ll}
+(IH1) & $\forall v_1 v_2.\;v_1 \succ_{der\;c\;r_1} v_2
+\;\wedge\; \vdash v_1 : der\;c\;r_1 \;\wedge\;
+\vdash v_2 : der\;c\;r_1\qquad$\\
+ & $\hfill\longrightarrow
+ inj\;r_1\;c\;v_1 \succ{r_1} \;inj\;r_1\;c\;v_2$\smallskip\\
+(IH2) & $\forall v_1 v_2.\;v_1 \succ_{der\;c\;r_2} v_2
+\;\wedge\; \vdash v_2 : der\;c\;r_2 \;\wedge\;
+\vdash v_2 : der\;c\;r_2\qquad$\\
+ & $\hfill\longrightarrow
+ inj\;r_2\;c\;v_1 \succ{r_2} \;inj\;r_2\;c\;v_2$\\
+\end{tabular}
+\end{center}
+
+\noindent
+The goal is
+
+\[
+(goal)\qquad
+inj\; (r_1 \cdot r_2)\;c\;v_1 \succ_{r_1 \cdot r_2}
+inj\; (r_1 \cdot r_2)\;c\;v_2
+\]
+
+\noindent
+If we analyse how (a) could have arisen (that is make a case
+distinction), then we will find four cases:
+
+\begin{center}
+\begin{tabular}{ll}
+LL & $v_1 = Left(w_1)$, $v_2 = Left(w_2)$\\
+LR & $v_1 = Left(w_1)$, $v_2 = Right(w_2)$\\
+RL & $v_1 = Right(w_1)$, $v_2 = Left(w_2)$\\
+RR & $v_1 = Right(w_1)$, $v_2 = Right(w_2)$\\
+\end{tabular}
+\end{center}
+
+
+\noindent
+We have to establish our goal in all four cases.
+
+
+\subsubsection*{Case LR}
+
+The corresponding rule (instantiated) is:
+
+\begin{center}
+\begin{tabular}{c}
+$len\,|w_1| \geq len\,|w_2|$\\
+\hline
+$Left(w_1) \succ_{(der\;c\;r_1) \cdot r_2 + der\;c\;r_2} Right(w_2)$
+\end{tabular}
+\end{center}
+
+\noindent
+This means we can also assume in this case
+
+\[
+(e)\quad len\,|w_1| \geq len\,|w_2|
+\]
+
+\noindent
+which is the premise of the rule above.
+Instantiating $v_1$ and $v_2$ in the assumptions (b) and (c)
+gives us
+
+\begin{center}
+\begin{tabular}{ll}
+(b*) & $\vdash Left(w_1) : (der\;c\;r_1) \cdot r_2 + der\;c\;r_2$\\
+(c*) & $\vdash Right(w_2) : (der\;c\;r_1) \cdot r_2 + der\;c\;r_2$\\
+\end{tabular}
+\end{center}
+
+\noindent Since these are assumptions, we can further analyse
+how they could have arisen according to the rules of $\vdash
+\_ : \_\,$. This gives us two new assumptions
+
+\begin{center}
+\begin{tabular}{ll}
+(b**) & $\vdash w_1 : (der\;c\;r_1) \cdot r_2$\\
+(c**) & $\vdash w_2 : der\;c\;r_2$\\
+\end{tabular}
+\end{center}
+
+\noindent
+Looking at (b**) we can further analyse how this
+judgement could have arisen. This tells us that $w_1$
+must have been a sequence, say $u_1\cdot u_2$, with
+
+\begin{center}
+\begin{tabular}{ll}
+(b***) & $\vdash u_1 : der\;c\;r_1$\\
+ & $\vdash u_2 : r_2$\\
+\end{tabular}
+\end{center}
+
+\noindent
+Instantiating the goal means we need to prove
+
+\[
+inj\; (r_1 \cdot r_2)\;c\;(Left(u_1\cdot u_2)) \succ_{r_1 \cdot r_2}
+inj\; (r_1 \cdot r_2)\;c\;(Right(w_2))
+\]
+
+\noindent
+We can simplify this according to the rules of $inj$:
+
+\[
+(inj\; r_1\;c\;u_1)\cdot u_2 \succ_{r_1 \cdot r_2}
+(mkeps\;r_1) \cdot (inj\; r_2\;c\;w_2)
+\]
+
+\noindent
+This is what we need to prove. There are only two rules that
+can be used to prove this judgement:
+
+\begin{center}
+\begin{tabular}{cc}
+\begin{tabular}{c}
+$v_1 = v_1'$\qquad $v_2 \succ_{r_2} v_2'$\\
+\hline
+$v_1\cdot v_2 \succ_{r_1\cdot r_2} v_1'\cdot v_2'$
+\end{tabular} &
+\begin{tabular}{c}
+$v_1 \succ_{r_1} v_1'$\\
+\hline
+$v_1\cdot v_2 \succ_{r_1\cdot r_2} v_1'\cdot v_2'$
+\end{tabular}
+\end{tabular}
+\end{center}
+
+\noindent
+Using the left rule would mean we need to show that
+
+\[
+inj\; r_1\;c\;u_1 = mkeps\;r_1
+\]
+
+\noindent
+but this can never be the case.\footnote{Actually Isabelle
+found this out after analysing its argument. ;o)} Lets assume
+it would be true, then also if we flat each side, it must hold
+that
+
+\[
+|inj\; r_1\;c\;u_1| = |mkeps\;r_1|
+\]
+
+\noindent
+But this leads to a contradiction, because the right-hand side
+will be equal to the empty list, or empty string. This is
+because we assumed $nullable(r_1)$ and there is a lemma
+called \texttt{mkeps\_flat} which shows this. On the other
+side we know by assumption (b***) and lemma \texttt{v4} that
+the other side needs to be a string starting with $c$ (since
+we inject $c$ into $u_1$). The empty string can never be equal
+to something starting with $c$\ldots therefore there is a
+contradiction.
+
+That means we can only use the rule on the right-hand side to
+prove our goal. This implies we need to prove
+
+\[
+inj\; r_1\;c\;u_1 \succ_{r_1} mkeps\;r_1
+\]
+
+
+\subsubsection*{Case RL}
+
+The corresponding rule (instantiated) is:
+
+\begin{center}
+\begin{tabular}{c}
+$len\,|w_1| > len\,|w_2|$\\
+\hline
+$Right(w_1) \succ_{(der\;c\;r_1) \cdot r_2 + der\;c\;r_2} Left(w_2)$
+\end{tabular}
+\end{center}
+
+\subsection*{Problems in the paper proof}
+
+I cannot verify
+
+\end{document}