Theory Regular-Sets.Relation_Interpretation

section ‹Regular Expressions as Homogeneous Binary Relations›

theory Relation_Interpretation
imports Regular_Exp
begin

primrec rel :: "('a ⇒ ('b * 'b) set) ⇒ 'a rexp ⇒ ('b * 'b) set"
where
  "rel v Zero = {}" |
  "rel v One = Id" |
  "rel v (Atom a) = v a" |
  "rel v (Plus r s) = rel v r ∪ rel v s" |
  "rel v (Times r s) = rel v r O rel v s" |
  "rel v (Star r) = (rel v r)^*"

primrec word_rel :: "('a ⇒ ('b * 'b) set) ⇒ 'a list ⇒ ('b * 'b) set"
where
  "word_rel v [] = Id"
| "word_rel v (a#as) = v a O word_rel v as"

lemma word_rel_append: 
  "word_rel v w O word_rel v w' = word_rel v (w @ w')"
by (rule sym) (induct w, auto)

lemma rel_word_rel: "rel v r = (⋃w∈lang r. word_rel v w)"
proof (induct r)
  case Times thus ?case 
    by (auto simp: rel_def word_rel_append conc_def relcomp_UNION_distrib relcomp_UNION_distrib2)
next
  case (Star r)
  { fix n
    have "(rel v r) ^^ n = (⋃w ∈ lang r ^^ n. word_rel v w)"
    proof (induct n)
      case 0 show ?case by simp
    next
      case (Suc n) thus ?case
        unfolding relpow.simps relpow_commute[symmetric]
        by (auto simp add: Star conc_def word_rel_append
          relcomp_UNION_distrib relcomp_UNION_distrib2)
    qed }

  thus ?case unfolding rel.simps
    by (force simp: rtrancl_power star_def)
qed auto


text ‹Soundness:›

lemma soundness:
 "lang r = lang s ⟹ rel v r = rel v s"
unfolding rel_word_rel by auto

end