theory ReStar

  imports "Main" 

begin

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)

definition

  Der :: "char \<Rightarrow> string set \<Rightarrow> string set"

where

  "Der c A \<equiv> {s. [c] @ s \<in> A}"

definition 

  Ders :: "string \<Rightarrow> string set \<Rightarrow> string set"

where  

  "Ders s A \<equiv> {s' | s'. s @ s' \<in> A}"

lemma Der_null [simp]:

  shows "Der c {} = {}"

unfolding Der_def

by auto

lemma Der_empty [simp]:

  shows "Der c {[]} = {}"

unfolding Der_def

by auto

lemma Der_char [simp]:

  shows "Der c {[d]} = (if c = d then {[]} else {})"

unfolding Der_def

by auto

lemma Der_union [simp]:

  shows "Der c (A \<union> B) = Der c A \<union> Der c B"

unfolding Der_def

by auto

  shows "Der c (A ;; B) = (Der c A) ;; B \<union> (if [] \<in> A then Der c B else {})"

unfolding Der_def Sequ_def

inductive_set

  Star :: "string set \<Rightarrow> string set" ("_\<star>" [101] 102)

  for A :: "string set"

where

  start[intro]: "[] \<in> A\<star>"

| step[intro]:  "\<lbrakk>s1 \<in> A; s2 \<in> A\<star>\<rbrakk> \<Longrightarrow> s1 @ s2 \<in> A\<star>"

lemma star_cases:

  shows "A\<star> = {[]} \<union> A ;; A\<star>"

unfolding Sequ_def

by (auto) (metis Star.simps)

lemma star_decomp: 

  assumes a: "c # x \<in> A\<star>" 

  shows "\<exists>a b. x = a @ b \<and> c # a \<in> A \<and> b \<in> A\<star>"

using a

by (induct x\<equiv>"c # x" rule: Star.induct) 

   (auto simp add: append_eq_Cons_conv)

lemma Der_star [simp]:

  shows "Der c (A\<star>) = (Der c A) ;; A\<star>"

proof -    

  have "Der c (A\<star>) = Der c ({[]} \<union> A ;; A\<star>)"

    by (simp only: star_cases[symmetric])

  also have "... = Der c (A ;; A\<star>)"

    by (simp only: Der_union Der_empty) (simp)

  also have "... = (Der c A) ;; A\<star> \<union> (if [] \<in> A then Der c (A\<star>) else {})"

    by simp

  also have "... =  (Der c A) ;; A\<star>"

    unfolding Sequ_def Der_def

    by (auto dest: star_decomp)

  finally show "Der c (A\<star>) = (Der c A) ;; A\<star>" .

qed

section {* Regular Expressions *}

datatype rexp =

  NULL

| EMPTY

| CHAR char

| SEQ rexp rexp

| ALT rexp rexp

| STAR 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)"

| "L (STAR r) = (L r)\<star>"

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)"

| "nullable (STAR r) = True"

lemma nullable_correctness:

  shows "nullable r  \<longleftrightarrow> [] \<in> (L r)"

section {* Values *}

datatype val = 

  Void

| Char char

| Seq val val

| Right val

| Left val

| Stars "val list"

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)"

| "flat (Stars []) = []"

| "flat (Stars (v#vs)) = (flat v) @ (flat (Stars vs))" 

 "flat (Stars vs) = concat (map flat vs)"

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"

| "\<turnstile> Stars [] : STAR r"

| "\<lbrakk>\<turnstile> v : r; \<turnstile> Stars vs : STAR r\<rbrakk> \<Longrightarrow> \<turnstile> Stars (v # vs) : STAR r"

lemma not_nullable_flat:

  shows "flat v \<noteq> []"

using assms

lemma Prf_flat_L:

  assumes "\<turnstile> v : r" shows "flat v \<in> L r"

using assms

apply(induct v r rule: Prf.induct)

apply(auto simp add: Sequ_def)

done

lemma Prf_Stars:

  assumes "\<forall>v \<in> set vs. \<turnstile> v : r"

  shows "\<turnstile> Stars vs : STAR r"

using assms

apply(induct vs)

apply (metis Prf.intros(6))

by (metis Prf.intros(7) insert_iff set_simps(2))

lemma Star_string:

  assumes "s \<in> A\<star>"

  shows "\<exists>ss. concat ss = s \<and> (\<forall>s \<in> set ss. s \<in> A)"

using assms

apply(induct rule: Star.induct)

apply(auto)

apply(rule_tac x="[]" in exI)

apply(simp)

apply(rule_tac x="s1#ss" in exI)

apply(simp)

done

lemma Star_val:

  assumes "\<forall>s\<in>set ss. \<exists>v. s = flat v \<and> \<turnstile> v : r"

  shows "\<exists>vs. concat (map flat vs) = concat ss \<and> (\<forall>v\<in>set vs. \<turnstile> v : r)"

using assms

apply(induct ss)

apply(auto)

apply (metis empty_iff list.set(1))

by (metis concat.simps(2) list.simps(9) set_ConsD)

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)

apply(subgoal_tac "\<exists>vs::val list. concat (map flat vs) = x \<and> (\<forall>v \<in> set vs. \<turnstile> v : r)")

apply(auto)[1]

apply(rule_tac x="Stars vs" in exI)

apply(simp)

apply(rule Prf_Stars)

apply(simp)

apply(drule Star_string)

apply(auto)

apply(rule Star_val)

apply(simp)

done

section {* Values Sets *}

definition prefix :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubseteq> _" [100, 100] 100)

where

  "s1 \<sqsubseteq> s2 \<equiv> \<exists>s3. s1 @ s3 = s2"

definition sprefix :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubset> _" [100, 100] 100)

where

  "s1 \<sqsubset> s2 \<equiv> (s1 \<sqsubseteq> s2 \<and> s1 \<noteq> s2)"

lemma length_sprefix:

  "s1 \<sqsubset> s2 \<Longrightarrow> length s1 < length s2"

unfolding sprefix_def prefix_def

by (auto)

definition Prefixes :: "string \<Rightarrow> string set" where

  "Prefixes s \<equiv> {sp. sp \<sqsubseteq> s}"

definition Suffixes :: "string \<Rightarrow> string set" where

  "Suffixes s \<equiv> rev ` (Prefixes (rev s))"

definition SPrefixes :: "string \<Rightarrow> string set" where

  "SPrefixes s \<equiv> {sp. sp \<sqsubset> s}"

definition SSuffixes :: "string \<Rightarrow> string set" where

  "SSuffixes s \<equiv> rev ` (SPrefixes (rev s))"

lemma Suffixes_in: 

  "\<exists>s1. s1 @ s2 = s3 \<Longrightarrow> s2 \<in> Suffixes s3"

unfolding Suffixes_def Prefixes_def prefix_def image_def

apply(auto)

by (metis rev_rev_ident)

lemma SSuffixes_in: 

  "\<exists>s1. s1 \<noteq> [] \<and> s1 @ s2 = s3 \<Longrightarrow> s2 \<in> SSuffixes s3"

unfolding SSuffixes_def Suffixes_def SPrefixes_def Prefixes_def sprefix_def prefix_def image_def

apply(auto)

by (metis append_self_conv rev.simps(1) rev_rev_ident)

lemma Prefixes_Cons:

  "Prefixes (c # s) = {[]} \<union> {c # sp | sp. sp \<in> Prefixes s}"

unfolding Prefixes_def prefix_def

apply(auto simp add: append_eq_Cons_conv) 

done

lemma finite_Prefixes:

  "finite (Prefixes s)"

apply(induct s)

apply(auto simp add: Prefixes_def prefix_def)[1]

apply(simp add: Prefixes_Cons)

done

lemma finite_Suffixes:

  "finite (Suffixes s)"

unfolding Suffixes_def

apply(rule finite_imageI)

apply(rule finite_Prefixes)

done

lemma prefix_Cons:

  "((c # s1) \<sqsubseteq> (c # s2)) = (s1 \<sqsubseteq> s2)"

apply(auto simp add: prefix_def)

done

lemma prefix_append:

  "((s @ s1) \<sqsubseteq> (s @ s2)) = (s1 \<sqsubseteq> s2)"

apply(induct s)

apply(simp)

apply(simp add: prefix_Cons)

done

definition Values :: "rexp \<Rightarrow> string \<Rightarrow> val set" where

  "Values r s \<equiv> {v. \<turnstile> v : r \<and> flat v \<sqsubseteq> s}"

definition rest :: "val \<Rightarrow> string \<Rightarrow> string" where

  "rest v s \<equiv> drop (length (flat v)) s"

lemma rest_Nil:

  "rest v [] = []"

apply(simp add: rest_def)

done

lemma rest_Suffixes:

  "rest v s \<in> Suffixes s"

unfolding rest_def

by (metis Suffixes_in append_take_drop_id)

lemma Values_recs:

  "Values (NULL) s = {}"

  "Values (EMPTY) s = {Void}"

  "Values (CHAR c) s = (if [c] \<sqsubseteq> s then {Char c} else {})" 

  "Values (ALT r1 r2) s = {Left v | v. v \<in> Values r1 s} \<union> {Right v | v. v \<in> Values r2 s}"

  "Values (SEQ r1 r2) s = {Seq v1 v2 | v1 v2. v1 \<in> Values r1 s \<and> v2 \<in> Values r2 (rest v1 s)}"

  "Values (STAR r) s = 

      {Stars []} \<union> {Stars (v # vs) | v vs. v \<in> Values r s \<and> Stars vs \<in> Values (STAR r) (rest v s)}"

unfolding Values_def

apply(auto)

(*NULL*)

apply(erule Prf.cases)

apply(simp_all)[7]

(*EMPTY*)

apply(erule Prf.cases)

apply(simp_all)[7]

apply(rule Prf.intros)

apply (metis append_Nil prefix_def)

(*CHAR*)

apply(erule Prf.cases)

apply(simp_all)[7]

apply(rule Prf.intros)

apply(erule Prf.cases)

apply(simp_all)[7]

(*ALT*)

apply(erule Prf.cases)

apply(simp_all)[7]

apply (metis Prf.intros(2))

apply (metis Prf.intros(3))

(*SEQ*)

apply(erule Prf.cases)

apply(simp_all)[7]

apply (simp add: append_eq_conv_conj prefix_def rest_def)

apply (metis Prf.intros(1))

apply (simp add: append_eq_conv_conj prefix_def rest_def)

(*STAR*)

apply(erule Prf.cases)

apply(simp_all)[7]

apply(rule conjI)

apply(simp add: prefix_def)

apply(auto)[1]

apply(simp add: prefix_def)

apply(auto)[1]

apply (metis append_eq_conv_conj rest_def)

apply (metis Prf.intros(6))

apply (metis append_Nil prefix_def)

apply (metis Prf.intros(7))

by (metis append_eq_conv_conj prefix_append prefix_def rest_def)

lemma finite_image_set2:

  "finite {x. P x} \<Longrightarrow> finite {y. Q y} \<Longrightarrow> finite {(x, y) | x y. P x \<and> Q y}"

  by (rule finite_subset [where B = "\<Union>x \<in> {x. P x}. \<Union>y \<in> {y. Q y}. {(x, y)}"]) auto

section {* Sulzmann functions *}

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))"

| "mkeps(STAR r) = Stars []"

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)"

| "der c (STAR r) = SEQ (der c r) (STAR r)"

fun 

 ders :: "string \<Rightarrow> rexp \<Rightarrow> rexp"

where

  "ders [] r = r"

| "ders (c # s) r = ders s (der c r)"

lemma der_correctness:

  shows "L (der c r) = Der c (L r)"

apply(induct r) 

apply(simp_all add: nullable_correctness)

done

lemma ders_correctness:

  shows "L (ders s r) = Ders s (L r)"

apply(induct s arbitrary: r) 

apply(simp add: Ders_def)

apply(simp)

apply(subst der_correctness)

apply(simp add: Ders_def Der_def)

done

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)"

| "injval (STAR r) c (Seq v (Stars vs)) = Stars ((injval r c v) # vs)" 

fun 

  lex :: "rexp \<Rightarrow> string \<Rightarrow> val option"

where

  "lex r [] = (if nullable r then Some(mkeps r) else None)"

| "lex r (c#s) = (case (lex (der c r) s) of  

                    None \<Rightarrow> None

                  | Some(v) \<Rightarrow> Some(injval r c v))"

fun 

  lex2 :: "rexp \<Rightarrow> string \<Rightarrow> val"

where

  "lex2 r [] = mkeps r"

| "lex2 r (c#s) = injval r c (lex2 (der c r) s)"

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)"

| "projval (STAR r) c (Stars (v # vs)) = Seq (projval r c v) (Stars vs)"

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

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)[7]

apply(simp)

apply(erule Prf.cases)

apply(simp_all)[7]

apply(case_tac "c = c'")

apply(simp)

apply(erule Prf.cases)

apply(simp_all)[7]

apply (metis Prf.intros(5))

apply(simp)