-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathmore_words.v
155 lines (116 loc) · 4.67 KB
/
more_words.v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
(* This program is free software; you can redistribute it and/or *)
(* modify it under the terms of the GNU Lesser General Public License *)
(* as published by the Free Software Foundation; either version 2.1 *)
(* of the License, or (at your option) any later version. *)
(* *)
(* This program is distributed in the hope that it will be useful, *)
(* but WITHOUT ANY WARRANTY; without even the implied warranty of *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *)
(* GNU General Public License for more details. *)
(* *)
(* You should have received a copy of the GNU Lesser General Public *)
(* License along with this program; if not, write to the Free *)
(* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA *)
(* 02110-1301 USA *)
(* Contribution to the Coq Library V6.3 (July 1999) *)
(****************************************************************************)
(* The Calculus of Inductive Constructions *)
(* *)
(* Projet Coq *)
(* *)
(* INRIA ENS-CNRS *)
(* Rocquencourt Lyon *)
(* *)
(* Coq V5.10 *)
(* Nov 25th 1994 *)
(* *)
(****************************************************************************)
(* more_words.v *)
(****************************************************************************)
(* Formal Language Theory *)
(* *)
(* Judicael Courant - Jean-Christophe Filliatre *)
(* *)
(* Developped in V5.8 June-July 1993 *)
(* Ported to V5.10 October 1994 *)
(****************************************************************************)
Require Import Ensf.
Require Import Words.
Hint Unfold eqwordset .
Definition l_inclus (l1 l2 : wordset) : Prop := forall w : Word, l1 w -> l2 w.
Hint Unfold l_inclus.
Lemma refl_l_inclus : forall l1 : wordset, l_inclus l1 l1.
auto.
Qed.
Hint Resolve refl_l_inclus.
Lemma trans_l_inclus :
forall l1 l2 l3 : wordset,
l_inclus l1 l2 -> l_inclus l2 l3 -> l_inclus l1 l3.
auto.
Qed.
Definition l_egal (l1 l2 : wordset) : Prop :=
l_inclus l1 l2 /\ l_inclus l2 l1.
Hint Unfold l_egal.
(*predicat equivalent a eqwordset*)
(*demonstration : *)
Lemma equiv_l_egal_eqwordset :
forall a b : wordset, l_egal a b <-> eqwordset a b.
intros a b.
unfold iff in |- *.
split.
intro Hyp; elim Hyp; auto.
intros Hyp.
split; unfold l_inclus in |- *; intro w; elim (Hyp w); auto.
Qed.
Lemma refl_l_egal : forall l1 : wordset, l_egal l1 l1.
auto.
Qed.
Hint Resolve refl_l_egal.
Section more_about_words.
Variable f : Elt -> Elt.
Let wef := Word_ext f.
(*
Lemma wef_cons : (a:Elt)(u:Word)(wef (cons a u))=(cons (f a) (wef u)).
Proof [a:Elt][u:Word](refl_equal Word (wef (cons a u))).
*)
Lemma wef_append :
forall u v : Word, wef (Append u v) = Append (wef u) (wef v).
intros u v.
elim u.
trivial.
unfold wef in |- *.
intros x w H.
simpl in |- *.
rewrite <- H.
reflexivity.
Qed.
Lemma wef_nil : forall a : Word, wef a = nil -> a = nil.
intro a.
case a.
auto.
unfold wef in |- *; simpl in |- *; intros x w H; discriminate H.
Qed.
Lemma wef_cons :
forall (a b : Word) (e : Elt),
cons e a = wef b ->
exists x : Elt,
ex2 (fun w : Word => cons x w = b) (fun w : Word => f x = e /\ wef w = a).
intros a b e.
unfold wef in |- *.
case b.
simpl in |- *; intro H; discriminate H.
simpl in |- *; intros x w H.
exists x.
exists w.
trivial.
injection H; auto.
Qed.
End more_about_words.
Hint Resolve wef_cons.
Lemma Append_assoc :
forall a b c : Word, Append a (Append b c) = Append (Append a b) c.
intros a b c.
unfold Append in |- *.
elim a; auto.
Qed.
Hint Resolve Append_assoc.