[helm.git] / matita / matita / lib / tutorial / chapter8.ma

(* 
Regular Expressions

We shall apply all the previous machinery to the study of regular languages 
and the constructions of the associated finite automata. *)

include "tutorial/chapter7.ma".

(* The type re of regular expressions over an alphabet $S$ is the smallest 
collection of objects generated by the following constructors: *)

inductive re (S: DeqSet) : Type[0] ≝
   z: re S                (* empty: ∅ *)
 | e: re S                (* epsilon: ϵ *)
 | s: S → re S            (* symbol: a *)
 | c: re S → re S → re S  (* concatenation: e1 · e2 *)
 | o: re S → re S → re S  (* plus: e1 + e2 *)
 | k: re S → re S.        (* kleene's star: e* *)

interpretation "re epsilon" 'epsilon = (e ?).
interpretation "re or" 'plus a b = (o ? a b).
interpretation "re cat" 'middot a b = (c ? a b).
interpretation "re star" 'star a = (k ? a).

notation < "a" non associative with precedence 90 for @{ 'ps $a}.
notation > "` term 90 a" non associative with precedence 90 for @{ 'ps $a}.
interpretation "atom" 'ps a = (s ? a).

notation "`∅" non associative with precedence 90 for @{ 'empty }.
interpretation "empty" 'empty = (z ?).

(* The language sem{e} associated with the regular expression e is inductively 
defined by the following function: *)

let rec in_l (S : DeqSet) (r : re S) on r : word S → Prop ≝ 
match r with
[ z ⇒ ∅
| e ⇒ {ϵ}
| s x ⇒ { (x::[]) }
| c r1 r2 ⇒ (in_l ? r1) · (in_l ? r2)
| o r1 r2 ⇒ (in_l ? r1) ∪ (in_l ? r2)
| k r1 ⇒ (in_l ? r1) ^*].


notation "\sem{term 19 E}" non associative with precedence 75 for @{'in_l $E}.
interpretation "in_l" 'in_l E = (in_l ? E).
interpretation "in_l mem" 'mem w l = (in_l ? l w).

lemma rsem_star : ∀S.∀r: re S. \sem{r^*} = \sem{r}^*.
// qed.


(* 
Pointed Regular expressions

We now introduce pointed regular expressions, that are the main tool we shall 
use for the construction of the automaton. 
A pointed regular expression is just a regular expression internally labelled 
with some additional points. Intuitively, points mark the positions inside the 
regular expression which have been reached after reading some prefix of
the input string, or better the positions where the processing of the remaining 
string has to be started. Each pointed expression for $e$ represents a state of 
the {\em deterministic} automaton associated with $e$; since we obviously have 
only a finite number of possible labellings, the number of states of the automaton 
is finite.

Pointed regular expressions provide the tool for an algebraic revisitation of 
McNaughton and Yamada's algorithm for position automata, making the proof of its 
correctness, that is far from trivial, particularly clear and simple. In particular, 
pointed expressions offer an appealing alternative to Brzozowski's derivatives, 
avoiding their weakest point, namely the fact of being forced to quotient derivatives 
w.r.t. a suitable notion of equivalence in order to get a finite number of states 
(that is not essential for recognizing strings, but is crucial for comparing regular 
expressions). 

Our main data structure is the notion of pointed item, that is meant whose purpose
is to encode a set of positions inside a regular expression. 
The idea of formalizing pointers inside a data type by means of a labelled version 
of the data type itself is probably one of the first, major lessons learned in the 
formalization of the metatheory of programming languages. For our purposes, it is 
enough to mark positions preceding individual characters, so we shall have two kinds 
of characters •a (pp a) and a (ps a) according to the case a is pointed or not. *)

inductive pitem (S: DeqSet) : Type[0] ≝
   pz: pitem S                       (* empty *)
 | pe: pitem S                       (* epsilon *)
 | ps: S → pitem S                   (* symbol *)
 | pp: S → pitem S                   (* pointed sysmbol *)
 | pc: pitem S → pitem S → pitem S   (* concatenation *)
 | po: pitem S → pitem S → pitem S   (* plus *)
 | pk: pitem S → pitem S.            (* kleene's star *)
 
(* A pointed regular expression (pre) is just a pointed item with an additional 
boolean, that must be understood as the possibility to have a trailing point at 
the end of the expression. As we shall see, pointed regular expressions can be 
understood as states of a DFA, and the boolean indicates if
the state is final or not. *)

definition pre ≝ λS.pitem S × bool.

interpretation "pitem star" 'star a = (pk ? a).
interpretation "pitem or" 'plus a b = (po ? a b).
interpretation "pitem cat" 'middot a b = (pc ? a b).
notation < ".a" non associative with precedence 90 for @{ 'pp $a}.
notation > "`. term 90 a" non associative with precedence 90 for @{ 'pp $a}.
interpretation "pitem pp" 'pp a = (pp ? a).
interpretation "pitem ps" 'ps a = (ps ? a).
interpretation "pitem epsilon" 'epsilon = (pe ?).
interpretation "pitem empty" 'empty = (pz ?).

(* The carrier $|i|$ of an item i is the regular expression obtained from i by 
removing all the points. Similarly, the carrier of a pointed regular expression 
is the carrier of its item. *)

let rec forget (S: DeqSet) (l : pitem S) on l: re S ≝
 match l with
  [ pz ⇒ z ? (* `∅ *)
  | pe ⇒ ϵ
  | ps x ⇒ `x
  | pp x ⇒ `x
  | pc E1 E2 ⇒ (forget ? E1) · (forget ? E2)
  | po E1 E2 ⇒ (forget ? E1) + (forget ? E2)
  | pk E ⇒ (forget ? E)^* ].

(* Already in the library
notation "| term 19 C |" with precedence 70 for @{ 'card $C }.
*)
interpretation "forget" 'card a = (forget ? a).

lemma erase_dot : ∀S.∀e1,e2:pitem S. |e1 · e2| = c ? (|e1|) (|e2|).
// qed.

lemma erase_plus : ∀S.∀i1,i2:pitem S.
  |i1 + i2| = |i1| + |i2|.
// qed.

lemma erase_star : ∀S.∀i:pitem S.|i^*| = |i|^*. 
// qed.

(* 
Comparing items and pres

Items and pres are very concrete datatypes: they can be effectively compared, 
and enumerated. In particular, we can define a boolean equality beqitem and a proof
beqitem_true that it refects propositional equality, enriching the set (pitem S)
to a DeqSet. *)

let rec beqitem S (i1,i2: pitem S) on i1 ≝ 
  match i1 with
  [ pz ⇒ match i2 with [ pz ⇒ true | _ ⇒ false]
  | pe ⇒ match i2 with [ pe ⇒ true | _ ⇒ false]
  | ps y1 ⇒ match i2 with [ ps y2 ⇒ y1==y2 | _ ⇒ false]
  | pp y1 ⇒ match i2 with [ pp y2 ⇒ y1==y2 | _ ⇒ false]
  | po i11 i12 ⇒ match i2 with 
    [ po i21 i22 ⇒ beqitem S i11 i21 ∧ beqitem S i12 i22
    | _ ⇒ false]
  | pc i11 i12 ⇒ match i2 with 
    [ pc i21 i22 ⇒ beqitem S i11 i21 ∧ beqitem S i12 i22
    | _ ⇒ false]
  | pk i11 ⇒ match i2 with [ pk i21 ⇒ beqitem S i11 i21 | _ ⇒ false]
  ].

lemma beqitem_true: ∀S,i1,i2. iff (beqitem S i1 i2 = true) (i1 = i2). 
#S #i1 elim i1
  [#i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % // normalize #H destruct
  |#i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % // normalize #H destruct
  |#x #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % normalize #H destruct
    [>(\P H) // | @(\b (refl …))]
  |#x #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % normalize #H destruct
    [>(\P H) // | @(\b (refl …))]
  |#i11 #i12 #Hind1 #Hind2 #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] %
   normalize #H destruct 
    [cases (true_or_false (beqitem S i11 i21)) #H1
      [>(proj1 … (Hind1 i21) H1) >(proj1 … (Hind2 i22)) // >H1 in H; #H @H
      |>H1 in H; normalize #abs @False_ind /2/
      ]
    |>(proj2 … (Hind1 i21) (refl …)) >(proj2 … (Hind2 i22) (refl …)) //
    ]
  |#i11 #i12 #Hind1 #Hind2 #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] %
   normalize #H destruct 
    [cases (true_or_false (beqitem S i11 i21)) #H1
      [>(proj1 … (Hind1 i21) H1) >(proj1 … (Hind2 i22)) // >H1 in H; #H @H
      |>H1 in H; normalize #abs @False_ind /2/
      ]
    |>(proj2 … (Hind1 i21) (refl …)) >(proj2 … (Hind2 i22) (refl …)) //
    ]
  |#i3 #Hind #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i4] %
   normalize #H destruct 
    [>(proj1 … (Hind i4) H) // |>(proj2 … (Hind i4) (refl …)) //]
  ]
qed. 

definition DeqItem ≝ λS.
  mk_DeqSet (pitem S) (beqitem S) (beqitem_true S).

(* We also add a couple of unification hints to allow the type inference system 
to look at (pitem S) as the carrier of a DeqSet, and at beqitem as if it was the 
equality function of a DeqSet. *)

unification hint  0 ≔ S; 
    X ≟ mk_DeqSet (pitem S) (beqitem S) (beqitem_true S)
(* ---------------------------------------- *) ⊢ 
    pitem S ≡ carr X.
    
unification hint  0 ≔ S,i1,i2; 
    X ≟ mk_DeqSet (pitem S) (beqitem S) (beqitem_true S)
(* ---------------------------------------- *) ⊢ 
    beqitem S i1 i2 ≡ eqb X i1 i2.

(* 
Semantics of pointed regular expressions

The intuitive semantic of a point is to mark the position where
we should start reading the regular expression. The language associated
to a pre is the union of the languages associated with its points. *)

let rec in_pl (S : DeqSet) (r : pitem S) on r : word S → Prop ≝ 
match r with
[ pz ⇒ ∅
| pe ⇒ ∅
| ps _ ⇒ ∅
| pp x ⇒ { (x::[]) }
| pc r1 r2 ⇒ (in_pl ? r1) · \sem{forget ? r2} ∪ (in_pl ? r2)
| po r1 r2 ⇒ (in_pl ? r1) ∪ (in_pl ? r2)
| pk r1 ⇒ (in_pl ? r1) · \sem{forget ? r1}^*  ].

interpretation "in_pl" 'in_l E = (in_pl ? E).
interpretation "in_pl mem" 'mem w l = (in_pl ? l w).

definition in_prl ≝ λS : DeqSet.λp:pre S. 
  if (snd ?? p) then \sem{fst ?? p} ∪ {ϵ} else \sem{fst ?? p}.
  
interpretation "in_prl mem" 'mem w l = (in_prl ? l w).
interpretation "in_prl" 'in_l E = (in_prl ? E).

(* The following, trivial lemmas are only meant for rewriting purposes. *)

lemma sem_pre_true : ∀S.∀i:pitem S. 
  \sem{〈i,true〉} = \sem{i} ∪ {ϵ}. 
// qed.

lemma sem_pre_false : ∀S.∀i:pitem S. 
  \sem{〈i,false〉} = \sem{i}. 
// qed.

lemma sem_cat: ∀S.∀i1,i2:pitem S. 
  \sem{i1 · i2} = \sem{i1} · \sem{|i2|} ∪ \sem{i2}.
// qed.

lemma sem_cat_w: ∀S.∀i1,i2:pitem S.∀w.
  \sem{i1 · i2} w = ((\sem{i1} · \sem{|i2|}) w ∨ \sem{i2} w).
// qed.

lemma sem_plus: ∀S.∀i1,i2:pitem S. 
  \sem{i1 + i2} = \sem{i1} ∪ \sem{i2}.
// qed.

lemma sem_plus_w: ∀S.∀i1,i2:pitem S.∀w. 
  \sem{i1 + i2} w = (\sem{i1} w ∨ \sem{i2} w).
// qed.

lemma sem_star : ∀S.∀i:pitem S.
  \sem{i^*} = \sem{i} · \sem{|i|}^*.
// qed.

lemma sem_star_w : ∀S.∀i:pitem S.∀w.
  \sem{i^*} w = (∃w1,w2.w1 @ w2 = w ∧ \sem{i} w1 ∧ \sem{|i|}^* w2).
// qed.

(* Below are a few, simple, semantic properties of items. In particular:
- not_epsilon_item : ∀S:DeqSet.∀i:pitem S. ¬ (\sem{i} ϵ).
- epsilon_pre : ∀S.∀e:pre S. (\sem{i} ϵ) ↔ (\snd e = true).
- minus_eps_item: ∀S.∀i:pitem S. \sem{i} =1 \sem{i}-{[ ]}.
- minus_eps_pre: ∀S.∀e:pre S. \sem{\fst e} =1 \sem{e}-{[ ]}.
The first property is proved by a simple induction on $i$; the other
results are easy corollaries. We need an auxiliary lemma first. *)

lemma append_eq_nil : ∀S.∀w1,w2:word S. w1 @ w2 = ϵ → w1 = ϵ.
#S #w1 #w2 cases w1 // #a #tl normalize #H destruct qed.

lemma not_epsilon_lp : ∀S:DeqSet.∀e:pitem S. ¬ (ϵ ∈ e).
#S #e elim e normalize   
  [1,2,3:/2/
  |#x % #H destruct 
  |#r1 #r2 * #n1 #n2 % * /2/ * #w1 * #w2 * * #H 
   >(append_eq_nil …H…) /2/
  |#r1 #r2 #n1 #n2 % * /2/
  |#r #n % * #w1 * #w2 * * #H >(append_eq_nil …H…) /2/
  ]
qed.

lemma epsilon_to_true : ∀S.∀e:pre S. ϵ ∈ e → snd … e = true.
#S * #i #b cases b // normalize #H @False_ind /2/ 
qed.

lemma true_to_epsilon : ∀S.∀e:pre S. snd … e = true → ϵ ∈ e.
#S * #i #b #btrue normalize in btrue; >btrue %2 // 
qed.

lemma minus_eps_item: ∀S.∀i:pitem S. \sem{i} ≐ \sem{i}-{ϵ}.
#S #i #w % 
  [#H whd % // normalize @(not_to_not … (not_epsilon_lp …i)) //
  |* //
  ]
qed.

lemma minus_eps_pre: ∀S.∀e:pre S. \sem{fst ?? e} ≐ \sem{e}-{ϵ}.
#S * #i * 
  [>sem_pre_true normalize in ⊢ (??%?); #w % 
    [/3/ | * * // #H1 #H2 @False_ind @(absurd …H1 H2)]
  |>sem_pre_false normalize in ⊢ (??%?); #w % [ /3/ | * // ]
  ]
qed.