--- a/thys/#MyFirst.thy# Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,198 +0,0 @@
-theory MyFirst
-imports Main
-begin
-
-datatype 'a list = Nil | Cons 'a "'a list"
-
-fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where
-"app Nil ys = ys" |
-"app (Cons x xs) ys = Cons x (app xs ys)"
-
-fun rev :: "'a list \<Rightarrow> 'a list" where
-"rev Nil = Nil" |
-"rev (Cons x xs) = app (rev xs) (Cons x Nil)"
-
-value "rev(Cons True (Cons False fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where
-"app Nil ys = ys" |
-"app (Cons x xs) ys = Cons x (app xs ys)"
-
-fun rev :: "'a list \<Rightarrow> 'a list" where
-"rev Nil = Nil" |
-"rev (Cons x xs) = app (rev xs) (Cons x Nil)"Nil))"
-
-value "1 + (2::nat)"
-value "1 + (2::int)"
-value "1 - (2::nat)"
-value "1 - (2::int)"
-
-lemma app_Nil2 [simp]: "app xs Nil = xs"
-apply(induction xs)
-apply(auto)
-done
-
-lemma app_assoc [simp]: "app (app xs ys) zs = app xs (app ys zs)"
-apply(induction xs)
-apply(auto)
-done
-
-lemma rev_app [simp]: "rev(app xs ys) = app (rev ys) (rev xs)"
-apply (induction xs)
-apply (auto)
-done
-
-theorem rev_rev [simp]: "rev(rev xs) = xs"
-apply (induction xs)
-apply (auto)
-done
-
-fun add :: "nat \<Rightarrow> nat \<Rightarrow> nat" where
-"add 0 n = n" |
-"add (Suc m) n = Suc(add m n)"
-
-lemma add_02: "add m 0 = m"
-apply(induction m)
-apply(auto)
-done
-
-value "add 2 3"
-
-
-(**commutative-associative**)
-lemma add_04: "add m (add n k) = add (add m n) k"
-apply(induct m)
-apply(simp_all)
-done
-
-lemma add_zero: "add n 0 = n"
-apply(induct n)
-apply(auto)
-done
-lemma add_zero: "add n 0 = n"
-apply(induct n)
-apply(auto)
-done
-lemma add_Suc: "add m (Suc n) = Suc (add m n)"
-apply(induct m)
-apply(metis add.simps(1))
-apply(auto)
-done
-
-lemma add_comm: "add m n = add n m"
-apply(induct m)
-apply(simp add: add_zero)
-apply(simp add: add_Suc)
-done
-
-lemma add_odd: "add m (add n k) = add k (add m n)"
-apply(subst add_04)
-apply(subst (2) add_comm)
-apply(simp)
-done
-
-
-fun dub :: "nat \<Rightarrow> nat" where
-"dub 0 = 0" |
-"dub m = add m m"
-
-lemma dub_01: "dub 0 = 0"
-apply(induct)
-apply(auto)
-done
-
-lemma dub_02: "dub m = add m m"
-apply(induction m)
-apply(auto)
-done
-
-value "dub 2"
-
-fun trip :: "nat \<Rightarrow> nat" where
-"trip 0 = 0" |
-"trip m = add m (add m m)"
-
-lemma trip_01: "trip 0 = 0"
-apply(induct)
-apply(auto)
-done
-
-lemma trip_02: "trip m = add m (add m m)"
-apply(induction m)
-apply(auto)
-done
-
-value "trip 1"
-value "trip 2"
-
-fun sum :: "nat \<Rightarrow> nat" where
- "sum 0 = 0"
-| "sum (Suc n) = (Suc n) + sum n"
-
-function sum1 :: "nat \<Rightarrow> nat" where
- "sum1 0 = 0"
-| "n \<noteq> 0 \<Longrightarrow> sum1 n = n + sum1 (n - 1)"
-apply(auto)
-done
-
-termination sum1
-by (smt2 "termination" diff_less less_than_iff not_gr0 wf_less_than zero_neq_one)
-
-lemma "sum n = sum1 n"
-apply(induct n)
-apply(auto)
-done
-
-lemma "sum n = (\<Sum>i \<le> n. i)"
-apply(induct n)
-apply(simp_all)
-done
-
-fun mull :: "nat \<Rightarrow> nat \<Rightarrow> nat" where
-"mull 0 0 = 0" |
-"mull m 0 = 0" |
-"mull m 1 = m" |
-(**"mull m (1::nat) = m" | **)
-(**"mull m (suc(0)) = m" | **)
-"mull m n = mull m (n-(1::nat))"
-apply(pat_completeness)
-apply(auto)
-
-done
-
- "mull 0 n = 0"
-| "mull (Suc m) n = add n (mull m n)"
-
-lemma test: "mull m n = m * n"
-sorry
-
-fun poww :: "nat \<Rightarrow> nat \<Rightarrow> nat" where
- "poww 0 n = 1"
-| "poww (Suc m) n = mull n (poww m n)"
-
-
-"mull 0 0 = 0" |
-"mull m 0 = 0" |
-(**"mull m 1 = m" | **)
-(**"mull m (1::nat) = m" | **)
-(**"mull m (suc(0)) = m" | **)
-"mull m n = mull m (n-(1::nat))"
-
-(**Define a function that counts the
-number of occurrences of an element in a list **)
-(**
-fun count :: "'a\<Rightarrow>'a list\<Rightarrow>nat" where
-"count "
-**)
-
-
-(* prove n = n * (n + 1) div 2 *)
-
-
-
-
-
-
-
-
-
-
-
--- a/thys/CountSnoc.thy.orig Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-theory CountSnoc
-imports Main
-begin
-
-datatype 'a myList = Nil | Cons 'a "'a myList"
-
-fun app_list :: "'a myList \<Rightarrow> 'a myList \<Rightarrow> 'a myList" where
-"app_list Nil ys = ys" |
-"app_list (Cons x xs) ys = Cons x (app_list xs ys)"
-
-fun rev_list :: "'a myList \<Rightarrow> 'a myList" where
-"rev_list Nil = Nil" |
-"rev_list (Cons x xs) = app_list (rev_list xs) (Cons x Nil)"
-
-(*
-fun count_list :: "'a \<Rightarrow> 'a myList \<Rightarrow> nat" where
-"count_list x [] = 0" |
-"count_list x (y#xs) = (
- if x = y then Suc(count_list x xs)
- else count_list x xs)"
-*)
-
-fun count_list :: "'a \<Rightarrow> 'a list \<Rightarrow> nat" where
-"count_list x [] = 0" |
-"count_list x (y#xs) = (
- if x = y then Suc(count_list x xs)
- else count_list x xs)"
-
-<<<<<<< local
-value "count_list 1 [1,1,0]"
-value "count_list 1 [2,2,2]"
-value "count_list 2 [2,2,1]"
-=======
-value "count_list (1::nat) [1,1,1]"
-value "count_list (1::nat) [2,2,2]"
-value "count_list (2::nat) [2,2,1]"
->>>>>>> other
-
-
--- a/thys/CountSnoc.thy~ Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,29 +0,0 @@
-theory CountSnoc
-imports Main
-begin
-
-
-datatype 'a myList = Nil | Cons 'a "'a myList"
-
-fun app_list :: "'a myList \<Rightarrow> 'a myList \<Rightarrow> 'a myList" where
-"app_list Nil ys = ys" |
-"app_list (Cons x xs) ys = Cons x (app_list xs ys)"
-
-fun rev_list :: "'a myList \<Rightarrow> 'a myList" where
-"rev_list Nil = Nil" |
-"rev_list (Cons x xs) = app_list (rev_list xs) (Cons x Nil)"
-
-fun count_list :: "'a \<Rightarrow> 'a list \<Rightarrow> nat" where
-"count_list x [] = 0" |
-"count_list x (y#xs) = (
- if x = y then Suc(count_list x xs)
- else count_list x xs)"
-
-value "count_list (1::nat) [1,1,1]"
-value "count_list (1::nat) [2,2,2]"
-value "count_list (2::nat) [2,2,1]"
-
-
-
-
-
--- a/thys/MyFirst.thy~ Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,132 +0,0 @@
-theory MyFirst
-imports Main
-begin
-
-datatype 'a list = Nil | Cons 'a "'a list"
-
-fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where
-"app Nil ys = ys" |
-"app (Cons x xs) ys = Cons x (app xs ys)"
-
-fun rev :: "'a list \<Rightarrow> 'a list" where
-"rev Nil = Nil" |
-"rev (Cons x xs) = app (rev xs) (Cons x Nil)"
-
-value "rev(Cons True (Cons False Nil))"
-
-value "1 + (2::nat)"
-value "1 + (2::int)"
-value "1 - (2::nat)"
-value "1 - (2::int)"
-
-lemma app_Nil2 [simp]: "app xs Nil = xs"
-apply(induction xs)
-apply(auto)
-done
-
-lemma app_assoc [simp]: "app (app xs ys) zs = app xs (app ys zs)"
-apply(induction xs)
-apply(auto)
-done
-
-lemma rev_app [simp]: "rev(app xs ys) = app (rev ys) (rev xs)"
-apply (induction xs)
-apply (auto)
-done
-
-theorem rev_rev [simp]: "rev(rev xs) = xs"
-apply (induction xs)
-apply (auto)
-done
-
-fun add :: "nat \<Rightarrow> nat \<Rightarrow> nat" where
-"add 0 n = n" |
-"add (Suc m) n = Suc(add m n)"
-
-lemma add_02: "add m 0 = m"
-apply(induction m)
-apply(auto)
-done
-
-value "add 2 3"
-
-(**commutative-associative**)
-lemma add_04: "add m (add n k) = add (add m n) k"
-apply(induct m)
-apply(simp_all)
-done
-
-lemma add_zero: "add n 0 = n"
-sorry
-
-lemma add_Suc: "add m (Suc n) = Suc (add m n)"
-sorry
-
-lemma add_comm: "add m n = add n m"
-apply(induct m)
-apply(simp add: add_zero)
-apply(simp add: add_Suc)
-done
-
-fun dub :: "nat \<Rightarrow> nat" where
-"dub 0 = 0" |
-"dub m = add m m"
-
-lemma dub_01: "dub 0 = 0"
-apply(induct)
-apply(auto)
-done
-
-lemma dub_02: "dub m = add m m"
-apply(induction m)
-apply(auto)
-done
-
-value "dub 2"
-
-fun trip :: "nat \<Rightarrow> nat" where
-"trip 0 = 0" |
-"trip m = add m (add m m)"
-
-lemma trip_01: "trip 0 = 0"
-apply(induct)
-apply(auto)
-done
-
-lemma trip_02: "trip m = add m (add m m)"
-apply(induction m)
-apply(auto)
-done
-
-value "trip 1"
-value "trip 2"
-
-fun mull :: "nat \<Rightarrow> nat \<Rightarrow> nat" where
-"mull 0 0 = 0" |
-"mull m 0 = 0" |
-(**"mull m 1 = m" | **)
-(**"mull m (1::nat) = m" | **)
-(**"mull m (suc(0)) = m" | **)
-"mull m n = mull m (n-(1::nat))"
-
-(**Define a function that counts the
-number of occurrences of an element in a list **)
-(**
-fun count :: "'a\<Rightarrow>'a list\<Rightarrow>nat" where
-"count "
-**)
-
-fun sum :: "nat \<Rightarrow> nat" where
-"sum n = 0 + \<dots> + n"
-(* prove n = n * (n + 1) div 2 *)
-
-
-
-
-
-
-
-
-
-
-
--- a/thys/Re1.thy.orig Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,642 +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)"
-
-
-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)"
-
-
-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
-
-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)"
-
-(*
-lemma
- assumes "r = SEQ (ALT EMPTY EMPTY) (ALT EMPTY (CHAR c))"
- shows "(Seq (Left Void) (Right (Char c))) \<succ>r (Seq (Left Void) (Left Void))"
-using assms
-apply(simp)
-apply(rule ValOrd.intros)
-apply(rule ValOrd.intros)
-apply(rule ValOrd.intros)
-apply(rule ValOrd.intros)
-apply(simp)
-done
-*)
-
-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')"
-
-
-(*
-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 (smt Prf.intros(1) ValOrd.simps assms(3) rexp.inject(2) val.distinct(15) val.distinct(17) val.distinct(3) val.distinct(9) val.inject(2))
-apply(drule_tac x="Seq v1 v'" in spec)
-apply(simp)
-by (smt Prf.intros(1) ValOrd.simps rexp.inject(2) val.distinct(15) val.distinct(17) val.distinct(3) val.distinct(9) val.inject(2))
-*)
-
-(*
-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)
-
-apply(auto)
-done
-*)
-
-
-
-
-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)
-
-done
-
-
-lemma POSIX_ALT2:
-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 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 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 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 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 {* 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)
-
-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))
-
-
-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(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(erule Prf.cases)
-apply(simp_all)[5]
-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 "\<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(rule_tac x = "Seq v va" in exI )
-apply(simp (no_asm) add: POSIX_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)
-apply(case_tac "v \<succ>r1a v1")
-apply (metis ValOrd.intros(2))
-apply(simp add: POSIX_def)
-apply(case_tac "flat v = flat v1")
-apply(auto)[1]
-apply(simp only: append_eq_append_conv2)
-apply(auto)
-thm append_eq_append_conv2
-
-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(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(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.rej Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,36 +0,0 @@
---- thys/Re1.thy
-+++ thys/Re1.thy
-@@ -168,6 +168,33 @@
- done
- *)
-
-+
-+
-+
-+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)
-+
-+done
-+
- lemma POSIX_ALT:
- assumes "POSIX (Left v1) (ALT r1 r2)"
- shows "POSIX v1 r1"
--- a/thys/Re1.thy~ Tue Oct 07 18:43:29 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,741 +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)"
-
-
-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)"
-
-
-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
-
-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)"
-
-(*
-lemma
- assumes "r = SEQ (ALT EMPTY EMPTY) (ALT EMPTY (CHAR c))"
- shows "(Seq (Left Void) (Right (Char c))) \<succ>r (Seq (Left Void) (Left Void))"
-using assms
-apply(simp)
-apply(rule ValOrd.intros)
-apply(rule ValOrd.intros)
-apply(rule ValOrd.intros)
-apply(rule ValOrd.intros)
-apply(simp)
-done
-*)
-
-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> flat v \<ge> 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 (smt Prf.intros(1) ValOrd.simps assms(3) rexp.inject(2) val.distinct(15) val.distinct(17) val.distinct(3) val.distinct(9) val.inject(2))
-apply(drule_tac x="Seq v1 v'" in spec)
-apply(simp)
-by (smt Prf.intros(1) ValOrd.simps rexp.inject(2) val.distinct(15) val.distinct(17) val.distinct(3) val.distinct(9) val.inject(2))
-*)
-
-(*
-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)
-
-apply(auto)
-done
-*)
-
-
-
-
-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)
-
-done
-
-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)
-
-
-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(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply metis
-done
-
-
-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 {* 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)
-
-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)
-apply(auto)[1]
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros)
-apply(simp)
-apply(rule ValOrd.intros)
-
-
-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(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(erule Prf.cases)
-apply(simp_all)[5]
-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 "\<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(rule_tac x = "Seq v va" in exI )
-apply(simp (no_asm) add: POSIX_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)
-apply(case_tac "v \<succ>r1a v1")
-apply (metis ValOrd.intros(2))
-apply(simp add: POSIX_def)
-apply(case_tac "flat v = flat v1")
-apply(auto)[1]
-apply(simp only: append_eq_append_conv2)
-apply(auto)
-thm append_eq_append_conv2
-
-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(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(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 *)