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

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

lemma Prf_flat_L:

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

using assms

apply(induct)

apply(auto simp add: Sequ_def)

done

lemma L_flat_Prf:

  "L(r) = {flat v | v. \<turnstile> v : r}"

apply(induct r)

apply(auto dest: Prf_flat_L simp add: Sequ_def)

apply (metis Prf.intros(4) flat.simps(1))

apply (metis Prf.intros(5) flat.simps(2))

apply (metis Prf.intros(1) flat.simps(5))

apply (metis Prf.intros(2) flat.simps(3))

apply (metis Prf.intros(3) flat.simps(4))

apply(erule Prf.cases)

apply(auto)

done

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

where

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

section {* Ordering of values *}

inductive ValOrd :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ \<succ>_ _" [100, 100, 100] 100)

where

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