(* Finite Automata *) (* a FA over states Q and type S is a start state, a transition relation, and an end state. *) #use "list.apl". #use "option.apl". #open List. #open Option. (* nondeterministic + epsilon FA *) type nfa Q S = (Q,[(Q,opt S,Q)],[Q]). func start (nfa Q S) = Q. start (Q,_,_) = Q. func delta (nfa Q S) = [(Q,opt S,Q)]. delta (_,Delta,_) = Delta. func accepting (nfa Q S) = [Q]. accepting (_,_,F) = F. pred next (nfa Q S) Q S Q. next FA Q S Q' :- mem ((Q,some S,Q'), (delta FA)). next FA Q S Q' :- mem ((Q,none,Q''), (delta FA)), next FA Q'' S Q'. pred next' (nfa Q S) Q [S] Q. next' FA Q [] Q. next' FA Q [S|L] Q'' :- next FA Q S Q', next' FA Q' L Q''. pred trace' (nfa Q S) Q [S] [Q]. trace' FA Q [] []. trace' FA Q [S|L] [Q'|Qs] :- next FA Q S Q', trace' FA Q' L Qs. pred accept (nfa Q S) [S]. accept FA L :- Q = start FA, next' FA Q L Q', mem (Q', (accepting FA)). pred trace (nfa Q S) [S] [Q]. trace FA L Qs :- Q = start FA, trace' FA Q L Qs. q : name_type. cnst fa1 = (nfa q char). fa1 = (a, [(a,some 'a',a), (a,some 'b',b), (b,some 'a',a), (b,some 'b',b)], [b]). ?accept fa1 "ababab". regexp : type. one : regexp. zero : regexp. plus : (regexp,regexp) -> regexp. comp : (regexp,regexp) -> regexp. star : regexp -> regexp. char : char -> regexp. pred equiv regexp (nfa q char). equiv one (a,[],[a]). equiv zero (a,[],[b]). equiv (char(C)) (a,[(a,some C,b)],[b]). equiv (plus(R1,R2)) (a,L'',[b]) :- equiv R1 (a,L,[b]), equiv R2 (a,L',[b]), append (L, L', L''). equiv (comp(R1,R2)) (a,L'',[c]) :- equiv R1 (a,L,[b]), equiv R2 (b,L',[c]), append (L, L', L''). equiv (star(R)) (a,[(a,none,c),(b,none,a)|L],[c]) :- equiv R (a,L,[b]). ?equiv (char 'd') FA. ?equiv (comp (char 'c',char 'd')) FA. ?equiv (plus (char 'c',char 'd')) FA. ?equiv (star (char 'c')) FA. ?equiv (comp(star (plus (char 'a',char 'b')),char 'b')) FA. cnst fa2 = nfa q char. fa2 = FA :- equiv (comp(star (plus (char 'a',char 'b')),char 'b')) FA. ?accept fa2 "b". ?accept fa2 "ababababababa". ?equiv (comp(comp (char 'c',char 'd'),comp (char 'c',char 'd'))) FA.