% Pflap: Prolog Formal Language and Automata Package % author: Robert Keller % % Purpose: Pflap provides a way to create, simulate, and analyze automata % in textual form, by using the Prolog language. % % So far we have models for: % DFA: Deterministic Finite-State Acceptors % NFA: Non-Deterministic Finite-State Acceptors % TM: Turing Machines % DFA Format: % A DFA is represented as a list of triples of the form: % [StateName, Output, Transitions] % where % StateName is the name of a state % Output is the output value associated with that state, e.g. % 1 for an accepting state % 0 for a non-accepting state % Transitions is a list of pairs of the form: % [InputSymbol, NextState] % % Example: The following assertion shows the representation of a DFA called dfa1: dfa1([ [q0, 1, [[a, q0], [b, q1]]], [q1, 0, [[a, q2], [b, q0]]], [q2, 1, [[a, q0], [b, q2]]]]). % The following predicates can be used to simulate or analyze DFA's: % moveFA(State, Input, NextState, DFA) % is true when there is a move from State to NextState via a % single input symbol Input in DFA. moveFA(State, Input, NextState, DFA) :- member([State, _, Transitions], DFA), member([Input, NextState], Transitions). % moveSequenceDFA(State, Input_Sequence, LasttState, DFA) % is true when there is a sequence of moves from State to LastState % via a sequence of input symbols. moveSequenceDFA(State, [], State, _). moveSequenceDFA(State, [A | X], LastState, DFA) :- moveFA(State, A, NextState, DFA), moveSequenceDFA(NextState, X, LastState, DFA). % accepted(Input_Sequence, DFA) is true when DFA % accepts Input_Sequence. This assumes: % States with output 1 are accepting. % The first state is the start state. accepted(Input_Sequence, DFA) :- firstState(DFA, Start), moveSequenceDFA(Start, Input_Sequence, LastState, DFA), member([LastState, 1, _], DFA). firstState([[Start, _, _] | _], Start). % acceptedLength(Length, DFA, Set) is true when Set is % the set of sequences of length L accepted by the DFA acceptedLength(L, DFA, Set):- setof1(X, (length(X, L), accepted(X, DFA)), Set). % a technicality: setof fails if there is no solution for the Goal. % We can define a predicate setof1 to get around this. setof1(X, Goal, Set) :- setof(X, Goal, Set) -> true; Set = []. % acceptedLengthUpTo(Length, DFA, Set) is true when Set is % the set of sequences of length L or fewer accepted by the DFA % in order of increasing length. acceptedLengthUpTo(0, DFA, Set) :- acceptedLength(0, DFA, Set). acceptedLengthUpTo(L, DFA, Set) :- L > 0, L1 is L - 1, acceptedLengthUpTo(L1, DFA, S), acceptedLength(L, DFA, T), append(S, T, Set). % The above routines will also work with NFA's, provided that they have no % empty-string transitions. nfa1([ [q0, 0, [[a, q1], [a, q2]]], [q1, 0, [[b, q3]]], [q2, 0, [[c, q4]]], [q3, 1, []], [q4, 1, []]]). % We consider adding an empty-transition capability to Pflap emptyReachable(State1,State2,NFA) :- emptyReachables(State1, States, NFA), member(State2, States). emptyReachables(State1, States, NFA) :- emptyReachablesHelper([State1], [State1], States, NFA). % emptyReachablesHelper(Sources, Acc, Result, NFA) emptyReachablesHelper([], Acc, SortedAcc, _) :- sort(Acc, SortedAcc). emptyReachablesHelper([State | States], Acc, Result, NFA) :- setof1(State2, moveFA(State, [], State2, NFA), States2), difference(States2, Acc, New), append(States, New, NewStates), append(Acc, New, NewAcc), emptyReachablesHelper(NewStates, NewAcc, Result, NFA). % difference(A, B, D) means D is the set of elements in A but not B difference(A, B, D) :- setof1(X, (member(X, A), \+member(X, B)), D). % Define move sequence for NFA. Here we include the possibility of % an using empty transitions. % Note that we use the same moveFA as in DFA. moveSequenceNFA(State, [], State2, NFA) :- emptyReachables(State, States, NFA), member(State2, States). moveSequenceNFA(State, X, State2, NFA) :- moveFA(State, A, NextState, NFA), moveSequenceNFA(NextState, Y, State2, NFA), ( A == [] -> X = Y ; X = [A | Y]). nfaAccepted(Input_Sequence, NFA) :- firstState(NFA, Start), moveSequenceNFA(Start, Input_Sequence, LastState, NFA), member([LastState, 1, _], NFA). % Example of an NFA with empty transitions: nfa2([ [q0, 0, [[a, q1], [a, q2]]], [q1, 0, [[[], q3]]], [q2, 0, [[[], q4]]], [q3, 1, []], [q4, 1, [[[], q1]]] ]). % Turing machines (TMs) % TMs are more complex: There is two-way motion and writing on the tape % We represent it as a list of 5-tuples of the form: % % [CurrentState, ReadSymbol, WriteSymbol, Motion, NextState] % % where Motion is either l, r, or n for left, right, or none % % There is no output with each state. Instead, the output is what is % left on the tape when the machine has no further moves. % % The tape symbol b is used to designate a blank. If the machine tries % to move off of either in, this is the symbol that will be inserted. % % The TM halts when no move is possible. % Here is a Turing Machine example: A binary adder % % The tape alphabet is {0, 1, b}, where b is blank, as mentioned above. % % Initially the head is assumed to be positioned at the left end of a sequence % of 0's and 1's representing a number in binary. The head is returned to this % position after adding 1 to the number. add1_binary( [ [start, 0, 0, r, start], % Move right to b, leaving other symbols as is. [start, 1, 1, r, start], [start, b, b, l, adding], % First b to the right encountered, start moving left. [adding, b, 1, n, stop], % Move left to 0 or b, replacing 1's with 0's. [adding, 0, 1, l, finishing], % Upon encountering a 0 or b, a 1 is written, [adding, 1, 0, l, adding], % then the computation finishes up. [finishing, 0, 0, l, finishing], % Move left to b, leaving symbols as is, then stop. [finishing, 1, 1, l, finishing], [finishing, b, b, r, stop] ]). % The following predicates can be used to simulate TM's % The state of a TM is represented as % [Left-part of tape reversed, Current-Control-State, Current-Read-Symbol, Right-part of tape] % moveTM([LeftReversed, Control, Read, Right], [NewLeftReversed, NewControl, NewRead, NewRight]) % is true when there is a move from one state to the next % for right moves: moveTM([ LeftReversed, Control, Read, [FirstRight | RestRight]], [[Write | LeftReversed], NewControl, FirstRight, RestRight], TM) :- member([Control, Read, Write, r, NewControl], TM). % for left moves: moveTM([[FirstLeft | LeftReversed], Control, Read, Right], [ LeftReversed, NewControl, FirstLeft, [Write | Right]], TM) :- member([Control, Read, Write, l, NewControl], TM). % for non moves: moveTM([LeftReversed, Control, Read, Right], [LeftReversed, NewControl, Write, Right], TM) :- member([Control, Read, Write, n, NewControl], TM). % Two more clauses are needed to handle the case where the % TM wants to move beyond the left or right ends of the tape: % for right moves off the right end, introduce one b under the head: moveTM([ LeftReversed, Control, Read, []], [[Write | LeftReversed], NewControl, b, []], TM) :- member([Control, Read, Write, r, NewControl], TM). % for left moves off the left end, introduce one b under the head: moveTM([[], Control, Read, Right], [[], NewControl, b, [Write | Right]], TM) :- member([Control, Read, Write, l, NewControl], TM). % Move sequence for a Turing machine moveSequenceTM(State, FinalState, TM) :- showTMstate(State), nl, (moveTM(State, NextState, TM) -> moveSequenceTM(NextState, FinalState, TM) ; FinalState = State ). % For tracing purposes: % The left part of the tape is reversed to how it would normally read. showTMstate([LeftReversed, Control, Read, Right]) :- reverse(LeftReversed, Left), showBare(Left), write('['), write(Read), write(']'), showBare(Right), write('['), write(Control), write(']'). showBare([]) :- write(' '). showBare([X | L]) :- write(' '), write(X), showBare(L). showBare1([]). showBare1([X | L]) :- write(' '), write(X), showBare1(L). % More TM examples: % bb4 happens to be the winner of Busy-Beaver(4). bb4([ [a, b, 1, r, b], [a, 1, 1, l, b], [b, b, 1, l, a], [b, 1, b, l, c], [c, b, 1, r, h], [c, 1, 1, l, d], [d, b, 1, r, d], [d, 1, b, r, a] ]). % Testing apparatus: % tester(Goal) for simple success or failure, no variable binding expected. tester(Goal) :- tester(Goal, [], []). % tester(Goal, Variable, Expectation) % runs (a copy of) Goal, which contains Variable. % It tests whether the Goal succeeds and, if so, % whether is bound to Expectation tester(Goal, Variable, Expectation) :- copy_term((Goal, Variable), (Goal1, Variable1)), call(Goal1) -> ( (Variable1 == Expectation -> nl, write('+++ test succeeded: '), write(Variable1), write(' == '), success ; nl, write('--- test failed: '), write(Variable1), write(' \== '), failure ), write(Expectation), write(', goal: '), write(Goal1), nl, nl ) ; nl, write('--- test goal failed: '), write(Goal1), nl, nl, failure. % Call success for when a test is successful, failure when it fails. % Call show. at the end to see totals. % Caution: Uses non-declarative aspects of Prolog. :- dynamic successes/1, failures/1. successes(0). failures(0). success :- retract(successes(N)), N1 is N + 1, assert(successes(N1)). failure :- retract(failures(N)), N1 is N + 1, assert(failures(N1)). show :- write('>>> test summary: '), successes(N), write(N), write(' successes, '), failures(M), write(M), write(' failures.'), nl, nl. % Turn off ... annoyance :- set_prolog_flag(toplevel_print_options, [quoted(true), portray(true), attributes(portray), max_depth(0), priority(699)]). % Pflap tests :- tester((dfa1(D), moveFA(q0, a, NextState, D)), NextState, q0). :- tester((dfa1(D), moveFA(q0, b, NextState, D)), NextState, q1). :- tester((dfa1(D), moveFA(q1, a, NextState, D)), NextState, q2). :- tester((dfa1(D), moveFA(q1, b, NextState, D)), NextState, q0). :- tester((dfa1(D), moveFA(q2, a, NextState, D)), NextState, q0). :- tester((dfa1(D), moveFA(q2, b, NextState, D)), NextState, q2). :- tester((dfa1(D), moveSequenceDFA(q0, [a, b, a], LastState, D)), LastState, q2). :- tester((dfa1(D), length(Sequence, 2), moveSequenceDFA(q0, Sequence, q2, D)), Sequence, [b, a]). :- tester((dfa1(D), accepted([b, b, a], D))). :- tester((dfa1(D), acceptedLength(3, D, S)), S, [[a, a, a], [a, b, a], [a, b, b], [b, a, a], [b, a, b], [b, b, a]]). :- tester((dfa1(D), acceptedLengthUpTo(3, D, S)), S, [[], [a], [a, a], [b, a], [b, b], [a, a, a], [a, b, a], [a, b, b], [b, a, a], [b, a, b], [b, b, a]]). :- tester((nfa1(N), acceptedLengthUpTo(3, N, S)), S, [[a, b], [a, c]]). :- tester((nfa2(N), emptyReachables(q1, S, N)), S, [q1, q3]). :- tester((nfa2(N), emptyReachables(q2, S, N)), S, [q1, q2, q3, q4]). :- tester((nfa2(N), nfaAccepted([a], N))). :- tester((nfa2(N), length(X, 1), nfaAccepted(X, N)), X, [a]). :- tester((nfa2(N), setof1(X, (length(X, 1), nfaAccepted(X, N)), S)), S, [[a]]). :- tester((nfa2(N), setof1(X, (length(X, 2), nfaAccepted(X, N)), S)), S, []). :- tester((nfa2(N), setof1(X, (length(X, 0), nfaAccepted(X, N)), S)), S, []). :- tester((add1_binary(TM), moveSequenceTM([[], start, 1, [1, 0, 0, 1, 1]], FinalState, TM)), FinalState, [[b], stop, 1, [1, 0, 1, 0, 0, b]]). :- tester((add1_binary(TM), moveSequenceTM([[], start, 1, [1, 1, 1, 1, 1]], FinalState, TM)), FinalState, [[], stop, 1, [0, 0, 0, 0, 0, 0, b]]). :- tester((bb4(TM), moveSequenceTM([[], a, b, []], FinalState, TM)), FinalState, [[1], h, b, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]). :- show.