Def Automata(Alph;States) == (StatesAlphStates)States(States)

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

Def |S| |T| == f:(ST). Surj(S; T; f)

Thm* S,T:Type. |S| |T| Prop

Def Con(A) == s:St. l:Alph*. (Result(A)l) = s

Thm* Alph,St:Type, A:Automata(Alph;St). Con(A) Prop

Def A1 A2 == x,y:Alph*. (Result(A1)x) = (Result(A1)y) S1 (Result(A2)x) = (Result(A2)y) S2

Thm* Alph,S1,S2:Type, A1:Automata(Alph;S1), A2:Automata(Alph;S2). A1 A2 Prop

Def Surj(A; B; f) == b:B. a:A. f(a) = b

Thm* A,B:Type, f:(AB). Surj(A; B; f) Prop

Def Result(DA)l == if null(l) InitialState(DA) else DA((Result(DA)tl(l)),hd(l)) fi (recursive)

Thm* Alph,St:Type, A:Automata(Alph;St), l:Alph*. (Result(A)l) St

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

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

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

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

Def a == 1of(a)

Thm* Alph,States:Type, a:Automata(Alph;States). a StatesAlphStates

Thm* Alph,States:Type, a:Automata(Alph;States). InitialState(a) States

Def null(as) == Case of as; nil true ; a.as' false

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

Thm* null(nil)

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

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