g_eq |
Def G1 = G2 == L(G1) = L(G2)
Thm* V1,V2,T:Type, G1:Grammar(V1;T), G2:Grammar(V2;T). G1 = G2 Prop |
g_lang |
Def L(G)(l) == [S] l
Thm* V,T:Type, G:Grammar(V;T). L(G) LangOver(V+T) |
derive |
Def (l,m)
== a:((V+T)* List).
l = a[0] (V+T)* & (i:(||a||-1). a[i] a[(i+1)]) & a[(||a||-1)] = m (V+T)*
Thm* V,T:Type, G:Grammar(V;T). (V+T)*(V+T)*Prop |
grammar |
Def Grammar(V;T) == ((V+T List)(V+T)*)*V
Thm* V,T:Type{i}. Grammar(V;T) Type{i'} |
lang_eq |
Def L = M == l:Alph*. L(l) M(l)
Thm* Alph:Type{i}, L,M:LangOver(Alph). L = M Prop{i'} |
iff |
Def P Q == (P Q) & (P Q)
Thm* A,B:Prop. (A B) Prop |
start |
Def S == inl(G.init)
Thm* V,T:Type, G:Grammar(V;T). S V+T |
directly_derive |
Def (l,m)
== l0:(V+T)*, l1:(V+T List), l2,m1:(V+T)*. l = (l0 @ l1 @ l2) & (l1 m1) & m = (l0 @ m1 @ l2)
Thm* V,T:Type, G:Grammar(V;T). (V+T)*(V+T)*Prop |
produce |
Def (l1,l2) == i:||G.prod||. < l1,l2 > = G.prod[i] (V+T List)(V+T)*
Thm* V,T:Type, G:Grammar(V;T). (V+T List)(V+T)*Prop |
list_p |
Def T List == {l:(T*)| ||l|| > 0 }
Thm* T:Type. (T List) Type |
length |
Def ||as|| == Case of as; nil 0 ; a.as' ||as'||+1 (recursive)
Thm* A:Type, l:A*. ||l|| Thm* ||nil|| |
select |
Def l[i] == hd(nth_tl(i;l))
Thm* A:Type, l:A*, n:. 0n n < ||l|| l[n] A |
int_seg |
Def {i..j} == {k:| i k < j }
Thm* m,n:. {m..n} Type |
rev_implies |
Def P Q == Q P
Thm* A,B:Prop. (A B) Prop |
g_init |
Def g.init == 2of(g)
Thm* V,T:Type, g:Grammar(V;T). g.init V |
nth_tl |
Def nth_tl(n;as) == if n0 as else nth_tl(n-1;tl(as)) fi (recursive)
Thm* A:Type, as:A*, i:. nth_tl(i;as) A* |
hd |
Def hd(l) == Case of l; nil "?" ; h.t h
Thm* A:Type, l:A*. ||l||1 hd(l) A |
append |
Def as @ bs == Case of as; nil bs ; a.as' a.(as' @ bs) (recursive)
Thm* T:Type, as,bs:T*. (as @ bs) T* |
lelt | Def i j < k == ij & j < k |
gt |
Def i > j == j < i
Thm* i,j:. i > j Prop |
pi2 |
Def 2of(t) == t.2
Thm* A:Type, B:(AType), p:a:AB(a). 2of(p) B(1of(p)) |
tl |
Def tl(l) == Case of l; nil nil ; h.t t
Thm* A:Type, l:A*. tl(l) A* |
le_int |
Def ij == j < i
Thm* i,j:. ij |
g_prod |
Def g.prod == 1of(g)
Thm* V,T:Type, g:Grammar(V;T). g.prod ((V+T List)(V+T)*)* |
le |
Def AB == B < A
Thm* i,j:. ij Prop |
lt_int |
Def i < j == if i < j true ; false fi
Thm* i,j:. i < j |
bnot |
Def b == if b false else true fi
Thm* b:. b |
pi1 |
Def 1of(t) == t.1
Thm* A:Type, B:(AType), p:a:AB(a). 1of(p) A |
not |
Def A == A False
Thm* A:Prop. (A) Prop |
About: