From: matitaweb <claudio.sacerdoticoen@unibo.it>
Date: Tue, 6 Mar 2012 13:44:53 +0000 (+0000)
Subject: chapter 9
X-Git-Tag: make_still_working~1902
X-Git-Url: http://matita.cs.unibo.it/gitweb/?p=helm.git;a=commitdiff_plain;h=c1fbb6fd4c98751f685a244905b4684f71399c9a

chapter 9
---

diff --git a/weblib/tutorial/acUbc.gif b/weblib/tutorial/acUbc.gif
index 5812fc8f4..9222a3418 100644
Binary files a/weblib/tutorial/acUbc.gif and b/weblib/tutorial/acUbc.gif differ
diff --git a/weblib/tutorial/chapter9.ma b/weblib/tutorial/chapter9.ma
index c68c8f1a0..fb11216e5 100644
--- a/weblib/tutorial/chapter9.ma
+++ b/weblib/tutorial/chapter9.ma
@@ -158,7 +158,7 @@ Let us discuss a couple of examples.
 bExample/b. 
 Below is the DFA associated with the regular expression (ac+bc)*.
 
-img src="acUbc.gif" alt="some_text"/  
+img src="http://www.cs.unibo.it/~asperti/FIGURES/acUbc.gif" alt="DFA for (ac+bc)"/  
 
 The graphical description of the automaton is the traditional one, with nodes for 
 states and labelled arcs for transitions. Unreachable states are not shown.
@@ -176,16 +176,24 @@ Let us consider a more complex case.
 bExample/b. 
 Starting form the regular expression (a+ϵ)(b*a + b)b, we obtain the following automaton.
 
-img src="automaton.pdf" alt="some_text"/ 
+img src="http://www.cs.unibo.it/~asperti/FIGURES/automaton.gif" alt="DFA for (a+ϵ)(b*a + b)b"/ 
 
 Remarkably, this DFA is minimal, testifying the small number of states produced by our 
-technique (the pair ofstates $6-8$ and $7-9$ differ for the fact that $6$ and $7$ 
-are final, while $8$ and $9$ are not). 
+technique (the pair ofstates 6-8 and 7-9 differ for the fact that 6 and 7 
+are final, while 8 and 9 are not). 
 *) 
 
-(************************ pit state ***************************)
+(*
+h2Move to pit/h2. 
+
+We conclude this chapter with a few properties of the move opertions in relation
+with the pit state. *).
+
 definition pit_pre ≝ λS.λi.〈blank S (|i|), false〉. 
 
+(* The following function compute if a symbol in S occurs in a given
+item i *).
+
 let rec occur (S: DeqSet) (i: re S) on i ≝  
   match i with
   [ z ⇒ [ ]
@@ -195,6 +203,9 @@ let rec occur (S: DeqSet) (i: re S) on i ≝
   | c e1 e2 ⇒ unique_append ? (occur S e1) (occur S e2) 
   | k e ⇒ occur S e].
 
+(* If a symbol a does not occur in i, then move(i,a) gets to the
+pit state. *).
+
 lemma not_occur_to_pit: ∀S,a.∀i:pitem S. memb S a (occur S (|i|)) ≠ true →
   move S a i  = pit_pre S i.
 #S #a #i elim i //
@@ -209,6 +220,8 @@ lemma not_occur_to_pit: ∀S,a.∀i:pitem S. memb S a (occur S (|i|)) ≠ true 
   ]
 qed.
 
+(* We cannot escape form the pit state. *).
+
 lemma move_pit: ∀S,a,i. move S a (\fst (pit_pre S i)) = pit_pre S i.
 #S #a #i elim i //
   [#i1 #i2 #Hind1 #Hind2 >move_cat >Hind1 >Hind2 // 
@@ -221,6 +234,9 @@ lemma moves_pit: ∀S,w,i. moves S w (pit_pre S i) = pit_pre S i.
 #S #w #i elim w // 
 qed. 
  
+(* If any character in w does not occur in i, then moves(i,w) gets
+to the pit state. *).
+
 lemma to_pit: ∀S,w,e. ¬ sublist S w (occur S (|\fst e|)) →
  moves S w e = pit_pre S (\fst e).
 #S #w elim w