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