Thms nfa 1 Sections AutomataTheory Doc

nd_valcom Def NDA(C) q == I(NDA) = 1of(hd(C)) St & (i:(||C||-1). NDA(1of(C[i]),hd(rev(2of(C[i]))),1of(C[(i+1)])) & 2of(C[(i+1)]) = rev(tl(rev(2of(C[i])))) Alph*) & 1of(hd(rev(C))) = q St & 2of(hd(rev(C))) = nil Alph*

Thm* Alph,St:Type, NDA:NDA(Alph;St), C:NComp(Alph;St), q:St. NDA(C) q Prop

NDA_act Def n == 1of(n)

Thm* Alph,States:Type, n:NDA(Alph;States). n StatesAlphStatesProp

nd_automata Def NDA(Alph;States) == (StatesAlphStatesProp)States(States)

Thm* Alph,States:Type{i}. nd_automata{i}(Alph;States) Type{i'}

nd_comp_extend Def C+[a;q] == map(c. < 1of(c),a.2of(c) > ;C) @ [ < q,nil > ]

Thm* Alph,St:Type, C:NComp(Alph;St), a:Alph, q:St. C+[a;q] NComp(Alph;St)

nd_computation Def NComp(Alph;St) == {C:(StAlph* List)| i:(||C||-1). ||2of(C[i])|| > 0 }

Thm* Alph,St:Type. NComp(Alph;St) Type

NDA_init Def I(n) == 1of(2of(n))

Thm* Alph,States:Type, n:NDA(Alph;States). I(n) States

pi1 Def 1of(t) == t.1

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

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

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

map Def map(f;as) == Case of as; nil nil ; a.as' f(a).map(f;as') (recursive)

Thm* A,B:Type, f:(AB), l:A*. map(f;l) B*

reverse Def rev(as) == Case of as; nil nil ; a.as' rev(as') @ [a] (recursive)

Thm* T:Type, as:T*. rev(as) T*

append Def as @ bs == Case of as; nil bs ; a.as' a.(as' @ bs) (recursive)

Thm* T:Type, as,bs:T*. (as @ bs) T*

select Def l[i] == hd(nth_tl(i;l))

Thm* A:Type, l:A*, n:. 0n n < ||l|| l[n] A

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||

gt Def i > j == j < i

Thm* i,j:. i > j Prop

int_seg Def {i..j} == {k:| i k < j }

Thm* m,n:. {m..n} Type

hd Def hd(l) == Case of l; nil "?" ; h.t h

Thm* A:Type, l:A*. ||l||1 hd(l) A

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*

tl Def tl(l) == Case of l; nil nil ; h.t t

Thm* A:Type, l:A*. tl(l) A*

lelt Def i j < k == ij & j < k

le_int Def ij == j < i

Thm* i,j:. ij

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

not Def A == A False

Thm* A:Prop. (A) Prop

About:
!abstractionimpliesfalseallpropmemberifthenelsebfalse
btrueboollessintless_thanandlist_indnil
universelistrecursive_def_noticenatural_numbersubtracttokensetadd
consapplyfunctionspreadproductlambdapairequal