grammar 1 Sections AutomataTheory Doc

g_lang Def L(G)(l) == [S] l

Thm* V,T:Type, G:Grammar(V;T). L(G) LangOver(V+T)

start Def S == inl(G.init)

Thm* V,T:Type, G:Grammar(V;T). S 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

g_init Def g.init == 2of(g)

Thm* V,T:Type, g:Grammar(V;T). g.init V

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

pi2 Def 2of(t) == t.2

Thm* A:Type, B:(AType), p:a:AB(a). 2of(p) B(1of(p))

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

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:
!abstractionimpliesfalseallpropmemberspread
universefunctionproductifthenelsebfalsebtruebool
lessintless_thanlistunionlist_indnil
andrecursive_def_noticeconstokennatural_numbersubtractset
addapplyexistsequalpairinl