% file: pflap.pro % purpose: Prolog Finite Automata and Languages Package (pflap) % author: Robert Keller % Manifest: A summary of the user interface predciates in pflap % A set of tests using PlUnit is provided in the latter part of this file. % Everything works, but I plan to add more to this. % First are some predicates for generating sequences, such as % input sequences to automata. % sequence(Sequence, Labels): % Labels is a set of labels, i.e. an alphabet. % Sequence is a sequence of elements of the alphabet. % Used as a generator, sequence will produce the sequences in order % of increasing length. % Example: sequence(S, [0, 1]), % will succeed with S values [], [0], [1], [0, 0], [0, 1], [1, 0], ... % sequence can also be used to check whether the first argument is a % sequence over the given alphabet. % Example: sequence([0, 1, 1, 0], [0, 1]) succeeds % Example: sequence([0,a,b,0], [0, 1]) fails. % sequence_in_range(Sequence, M, N, Labels) generates sequences % with a length between M and N inclusive. % Example: ?- sequence_in_range(X, 1, 3, [0, 1]). % X = [0] ; % X = [1] ; % X = [0,0] ; % ... % X = [1,1,1] ; % false. % sequence_in_range can also be used to check a sequence: % Example: sequence_in_range([0, 1, 1], 3, 5, [0, 1]) succeeds % sequences_in_range(Set, M, N, Labels) returns the set of sequences % with lengths between M and N inclusive % State Machines (aka Transition Systems) form the core of both % deterministic and non-deterministic finite-state automata. % They need to be accompanied by specified start and end states % to become regular automata. % % In pflap, state machines are simply lists of transitions. % There are two forms of transition: % labeled: A triple (From, Label, To) where From and To are states % spontaneous: A pair (From, To) with no label % % Here are some live examples: % Example state machine (complete and deterministic) state_machine_1([(a, 0, a), (a, 1, b), (b, 0, c), (b, 1, a), (c, 0, b), (c, 1, c)]). % Example of a non-deterministic state machine state_machine_1n([(a, 0, a), (a, 1, b), (b, 0, c), (b, 1, a), (b, 1, b), (c, 0, b), (c, 1, c)]). % Example of an incomplete state machine % (ones in which some states have no successor for some label) state_machine_1i([(a, 0, a), (a, 1, b), (b, 0, c), (c, 0, b), (c, 1, c)]). % Example state machine with spontaneous transitions % Here (a, b) is a spontaneous transition from state a to state b. state_machine_1s([(a, 0, a), (a, b), (b, 1, b)]). sipser_fig1_19([(even, 0, even), (even, 1, odd), (odd, 0, odd), (odd, 1, even)]). % dfa sipser_fig1_20([(even, 0, even), (even, 1, odd), (odd, 0, odd), (odd, 1, even)], even, [odd]). sipser_fig1_22([(q, 0, q0), (q, 1, q), (q0, 0, q00), (q0, 1, q), (q00, 0, q00), (q00, 1, q001), (q001, 0, q001), (q001, 1, q001)], q, [q001]). sipser_fig1_27([(q1, 0, q1), (q1, 1, q1), (q1, 1, q2), (q2, q3), (q2, 0, q3), (q3, 1, q4), (q4, 0, q4), (q4, 1, q4)], [q1], [q4]). sipser_fig1_31([(q1, 0, q1), (q1, 1, q1), (q1, 1, q2), (q2, 0, q3), (q2, 1, q3), (q3, 0, q4), (q3, 1, q4)], [q1], [q4]). sipser_fig1_32([(q000, 0, q000), (q000, 1, q001), (q001, 0, q010), (q001, 1, q011), (q100, 0, q000), (q100, 1, q001), (q010, 0, q100), (q010, 1, q101), (q011, 0, q110), (q011, 1, q111), (q110, 0, q100), (q110, 1, q101), (q101, 0, q010), (q101, 1, q011), (q111, 0, q110), (q111, 1, q111)], q000, [q100, q101, q110, q111]). % labels(Transitions, Labels) extracts the set of labels from the transitions % Example: labels([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)], [0, 1]). % states(Transitions, States) extracts the states from the transitions % Example: states([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)], [a, b]). % is_deterministic(Transitions) determines whether a state machine is % deterministic. % Example: is_deterministic([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) succeeds % Example: is_deterministic([(a, 0, b), (a, 1, a), (b, 0, a), (b, 0, b), (b, 1, b)]) fails % is_complete(Transitions) determines whether a state machine is complete % Example: is_complete([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) succeeds % Example: is_complete([(a, 0, b), (a, 1, a), (b, 1, b)]) fails % has_spontaneous(Transitions) determines whether a state machine % has any spontaneous transitions. % Example: has_spontaneous([(a, 0, b), (b, a), (b, 0, a)]) succeeds % Example: has_spontaneous([(a, 0, b), (b, 0, a)]) fails % reach(Sequence, Start, End, Transitions) returns Sequence as % a sequence of alternating states and labels, from state Start to % state End, as governed by the state machine Transitions. % This provides a complete picture of how a sequence takes the machine % from one to another, by identifying the intermediate states. % Example: % reach([a, 0, b, 1, b, 0, a], a, a, [(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) % reach can be used to generate or check. % If generation in increasing length is desired, it should be preceded % by a use of length(Sequence, _), as in the following example: % ?- length(Sequence, _), % reach(Sequence, a, a, [(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]). % Sequence = [a] ; % Sequence = [a,1,a] ; % Sequence = [a,0,b,0,a] ; % Sequence = [a,1,a,1,a] ; % Sequence = [a,0,b,0,a,1,a] ; % Sequence = [a,0,b,1,b,0,a] ; % Sequence = [a,1,a,0,b,0,a] % label_sequence(Sequence, Start, End, Transitions) means that % Sequence is a sequence of labels corresponding to transitions from % state Start to state End. % Example: % label_sequence([0, 1, 0], a, b, % [(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) % End of Manifest % Begin pflap code :- ensure_loaded(library(pldoc)). :- set_prolog_flag(toplevel_print_options, [quoted(true), portray(true), attributes(portray), max_depth(999), priority(999)]). % sequence(Sequence, Labels) is nondet % Sequence is a list of elements drawn from Labels. % Given Labels, Sequences will be generated in order of increasing length. % Example: sequence(S, [0, 1]), % will succeed with S values [], [0], [1], [0, 0], [0, 1], [1, 0], ... sequence(X, Labels) :- length(X, _), fill(X, Labels). % fill(List, Labels) fills a list of variables with elements from Labels. fill([], _Labels). fill([A|X], Labels) :- member(A, Labels), fill(X, Labels). % sequence_in_range(X, M, N, Labels) iff X is a sequence % elements in Labels of length M through N inclusive sequence_in_range(X, M, N, Labels) :- M =< N, length(X, M), fill(X, Labels). sequence_in_range(X, M, N, Labels) :- M < N, M1 is M+1, sequence_in_range(X, M1, N, Labels). % sequences_in_range(Set, M, N, Labels) iff % Set is the set of sequences with elements in Labels % from length M to length N inclusive. sequences_in_range(Set, M, N, Labels) :- bagof(X, sequence_in_range(X, M, N, Labels), Set). % Some utilities for getting information from a state machine % transition(From, Label, To, Transitions) iff there is a labeled % transition from From to To with Label transition(From, Label, To, Transitions) :- member((From, Label, To), Transitions). % label(Label, Transitions) iff Label is a the label on a transition label(Label, Transitions) :- transition(_, Label, _, Transitions). % nonpair is needed because of the way tuples work. % Comma is just a binary operator, so a triple is really % a pair where the second element is a pair. nonpair(Y) :- Y \= (_, _). % spontaneous_transition(From, To, Transitions) iff there is % a spontaneous transition from state From to state To. spontaneous_transition(From, To, Transitions) :- member((From, To), Transitions), nonpair(To). % The reason for nonpair is due to comma being a binary operator. % Without this, (a, 0, b) would be recognized as spontaneous, % as it unifies with (a, (0, b)). % This solution could produce anomalies, however, if some states are % encoded as pairs (p, q). If such encodings are entertained, it % would be better to use [p, q] for the pairing aspect, to avoid % false matches. % transitions(From, To, Transitions) if there is either a labeled or % a spontaneous transition from state From to state To. transition(From, To, Transitions) :- transition(From, _, To, Transitions). transition(From, To, Transitions) :- spontaneous_transition(From, To, Transitions). % state(State, Transitions) iff State is either a From state % or a To state in some transition. state(State, Transitions) :- transition(State, _, Transitions). state(State, Transitions) :- transition(_, State, Transitions). % setof1 is like setof, except that it succeeds with [] if Goal fails. setof1(Set, Goal, Ans) :- setof(Set, Goal, Ans) -> true; Ans = []. % For a list of Transitions (From, Label, To), % where From and To are states (nodes) % labels(Transitions, Labels) iff Labels is the set of Labels in the list. % Example: labels([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)], [0, 1]). labels(Transitions, Labels) :- setof1(Label, label(Label, Transitions), Labels). % For a list of Transitions (From, Label, To), % states(Transitions, States) iff States is the set of states From or To % in the list. % Example: states([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)], [a, b]). states(Transitions, States) :- setof1(State, state(State, Transitions), States). % is_deterministic(Transitions) iff no two transitions % in Transitions with the same From and Label have different To's. % succeeds: is_deterministic([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) % fails: is_deterministic([(a, 0, b), (a, 1, a), (b, 0, a), (b, 0, b)]) is_deterministic(Transitions) :- \+ (member((From, Label, To1), Transitions), member((From, Label, To2), Transitions), To1 \== To2). % has_spontaneous(Transitions) iff there is at least one % spontaneous transition in the set. A spontaneous transition is % one of the form (P, Q) where P and Q are states, but there is no % label. has_spontaneous(Transitions) :- spontaneous_transition(_, _, Transitions), !. % is_complete(Transitions) iff for every State and every Label % there is a Transition starting from that State with that Label. % In other words, it is not the case that there is a state From % and a Label with no Transition of the form (From, Label, To). % succeeds: is_complete([(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) % fails: is_complete([(a, 0, b), (a, 1, a), (b, 1, b)]) is_complete(Transitions) :- states(Transitions, States), labels(Transitions, Labels), \+ ((member(From, States), member(Label, Labels)), \+transition(From, Label, _, Transitions)). % reach(Sequence, Start, End, Transitions) iff there is a % state-transition Sequence from Start to End using Transitions from the list. % Transitions is a list of the form (From, Label, To), where From and To are % states and Label is the label on an arc connecting those states. % Sequence is a sequence [S0, L1, S1, S2, L2, ..., Ln, Sn] % where for each i (Si-1, Li, Si) is in Transitions. % Caution: If the state machine has spontaneous transitions, no % label will be included, so the sequence might not be odd-lengh. % Example: % reach([a, 0, b, 1, b, 0, a], a, a, % [(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) reach([State], State, State, _Transitions). reach([Start, Label | More], Start, End, Transitions) :- transition(Start, Label, Intermediate, Transitions), reach(More, Intermediate, End, Transitions). % spontaneous transitions introduce no labels reach([Start | More], Start, End, Transitions) :- spontaneous_transition(Start, Intermediate, Transitions), reach(More, Intermediate, End, Transitions). % label_sequence(Sequence, Start, End, Transitions) iff % Sequence is a sequence of labels corresponding to transitions from % state Start to state End. % Example: % label_sequence([0, 1, 0], a, b, % [(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) % empty sequence goes from any State to itself label_sequence([], State, State, _Transitions). % regular transition from Start, beginning with Label label_sequence([Label | More], Start, End, Transitions) :- transition(Start, Label, State, Transitions), label_sequence(More, State, End, Transitions). % spontaneous transition from Start, does not use a label label_sequence(More, Start, End, Transitions) :- spontaneous_transition(Start, State, Transitions), label_sequence(More, State, End, Transitions). % increasing_label_sequence(Sequence, Start, End, Transitions) is % like label_sequence(Sequence, Start, End, Transitions) with the % addition that sequences are generated in order of increasing length. increasing_label_sequence(Sequence, Start, End, Transitions) :- length(Sequence, _), label_sequence(Sequence, Start, End, Transitions). % generalized_label_sequence(Sequence, Start, End, Transitions) iff % Sequence is a sequence of labels corresponding to transitions from % some state in StartSet to some state in EndSet % generalized_label_sequence([0, 0, 1], [a], [a, b], % [(a, 0, b), (a, 1, a), (b, 0, a), (b, 1, b)]) generalized_label_sequence(Sequence, StartSet, EndSet, Transitions) :- member(Start, StartSet), member(End, EndSet), label_sequence(Sequence, Start, End, Transitions). % increasing_generalized_label_sequence(Sequence, StartSet, EndSet, Transitions) % is like generalized_label_sequence(Sequence, StartSet, EndSet, Transitions) % except that sequences are generated in increasing order. increasing_generalized_label_sequence(Sequence, StartSet, EndSet, Transitions) :- length(Sequence, _), generalized_label_sequence(Sequence, StartSet, EndSet, Transitions). % label_sequence_in_range(Sequence, M, N, StartSet, EndSet, Transitions) iff % Sequence is a sequence of length between M and N inclusive, starting % with a state in StartSet and ending with a state in EndSet. label_sequence_in_range(Sequence, M, N, StartSet, EndSet, Transitions) :- labels(Transitions, Labels), sequences_in_range(Set, M, N, Labels), member(Sequence, Set), generalized_label_sequence(Sequence, StartSet, EndSet, Transitions). % The following utilities may be used in testing and demonstrations. % binary_to_number(Digits, Value) converts a sequence of 0's and 1's % representing a binary numeral, most-significan-digit first, % to a numerical value. binary_to_number(Digits, Value) :- binary_to_number_helper(Digits, 0, Value). % binary_to_number/2 uses binary_to_number/3 with % so that the value is accumulated most-significant-bit first binary_to_number_helper([], Acc, Acc). binary_to_number_helper([Digit | Digits], Acc, Value) :- NewAcc is 2*Acc + Digit, binary_to_number_helper(Digits, NewAcc, Value). % prefix(N, L, M) is true when M is the length N prefix of L. % N must be instantiated before calling. % If N is more than the length of L, M is defined to be L. prefix(0, _L, []). prefix(N1, L, M) :- N1 > 0, ( L = [A|X] -> N is N1 - 1, prefix(N, X, Y), M = [A | Y] ; M = [] ). % firstN(N, Goal, Template , Result) iff Result is a list of up to the % first N solutions of Goal, where a solution is represented % as an instantiation of Template, which shares variables with Goal. % If there are fewer than N solutions all solutions are returned. % If there are more, only N are returned. % If there are no solutions, [] is returned. % Note: The solution is a bit hacky. It uses cut and call. firstN(N, Goal, Template, Result) :- firstN(N, Goal, Template, [], Result). firstN(Count, Goal, Template, Acc, Result) :- copy_term((Goal, Template), (GoalCopy, TemplateCopy)), call((Count > 0, GoalCopy, \+member(TemplateCopy, Acc))), !, Count1 is Count - 1, firstN(Count1, Goal, Template, [TemplateCopy | Acc], Result). firstN(_, _, _, Acc, Result) :- reverse(Acc, Result). groupby(Transitions, From, Result) :- setof1((Label, To), member((From, Label, To), Transitions), Result). groupbyFrom(Transitions, From, Result) :- setof1((From, Label, To), transition(From, Label, To, Transitions), Result1), setof1((From, To), spontaneous_transition(From, To, Transitions), Result2), union(Result1, Result2, Result). % In show_dfa(Predicate), Predicate should be the name of a % 3-ary predicate of the form pred(Transitions, Initial, Final) % where Initial is a single state, and Final is a set of final states. show_dfa(Predicate, NumberOfSequences) :- call(Predicate, Transitions, Initial, Final), write('DFA '), write(Predicate), write(':'), nl, tabulate(Transitions, [Initial], Final), write('examples of strings accepted by '), write(Predicate), write(': '), nl, firstN(NumberOfSequences, increasing_generalized_label_sequence(X, [Initial], Final, Transitions), X, Result), write_by_line(Result), nl. show_nfa(Predicate, NumberOfSequences) :- call(Predicate, Transitions, Initial, Final), write('NFA '), write(Predicate), write(':'), nl, states(Transitions, States), setof1((From, TriplesOrPairs), (member(From, States), groupbyFrom(Transitions, From, TriplesOrPairs)), List), write('Transitions: '), nl, write_list_of_triples(List, Initial, Final), write('examples of strings accepted by '), write(Predicate), write(': '), nl, firstN(NumberOfSequences, increasing_generalized_label_sequence(X, Initial, Final, Transitions), X, Result), write_by_line(Result), nl. write_list_of_triples([], _Initial, _Final). write_list_of_triples([(From, TriplesOrPairs) | Lists], Initial, Final) :- write(From), write(': '), write(TriplesOrPairs), (member(From, Initial) -> write(' Initial') ; true), (member(From, Final) -> write(' Final') ; true), nl, write_list_of_triples(Lists, Initial, Final). % Show elements of a list on separate lines write_by_line([]). write_by_line([First | Rest]) :- write(First), nl, write_by_line(Rest). % tabulate state machine tabulate(Transitions) :- tabulate(Transitions, []). tabulate(Transitions, Initial) :- tabulate(Transitions, Initial, []). tabulate(Transitions, Initial, Final) :- states(Transitions, States), labels(Transitions, Labels), setof1((From, Pairs), (member(From, States), groupby(Transitions, From, Pairs)), Result), append(States, Labels, Both), get_max_length(Both, 0, Length), show_header(Length, Labels), show_table(Result, Labels, Length, Initial, Final), show_horizontal_line(Labels, Length). % support code for tabulate % shows the table body (exclusive of header) show_table([], _Labels, _Length, _Initial, _Final). show_table([(From, Pairs) | More], Labels, Length, Initial, Final) :- show_row(From, Pairs, Labels, Length, Initial, Final), show_table(More, Labels, Length, Initial, Final). % shows a row of the table show_row(From, Pairs, Labels, Length, Initial, Final) :- pad(From, Length, Padded), write(Padded), write(' | '), show_entries(Pairs, Labels, Length), write('| '), (member(From, Initial) -> write('Initial ') ; true), (member(From, Final) -> write('Final') ; true), nl. % shows entries of row, after row header show_entries(_Pairs, [], _Length). show_entries([(Label, State) | Pairs], [Label | Labels], Length) :- !, pad(State, Length, PaddedState), write(PaddedState), write(' '), show_entries(Pairs, Labels, Length). show_entries(Pairs, [_Label | Labels], Length) :- !, write_pad(Length, ' '), write(' '), show_entries(Pairs, Labels, Length). % get the maximium string length of a list of atoms get_max_length([], Length, Length). get_max_length([Label | Labels], Acc, Length) :- term_to_atom(Label, Atom), atom_chars(Atom, Chars), length(Chars, L), (L > Acc -> NewAcc = L ; NewAcc = Acc), get_max_length(Labels, NewAcc, Length). % pad an atom to a given length, which should be >= the length of the atom pad(Label, Length, PaddedLabel) :- term_to_atom(Label, Atom), atom_to_chars(Atom, Chars), char_code(' ', CharCode), pad2(Chars, Length, CharCode, PaddedChars), atom_chars(PaddedLabel, PaddedChars). % helper for pad pad2([], Length, CharCode, PaddedChars) :- length(PaddedChars, Length), fill(PaddedChars, [CharCode]). pad2([Char | Chars], Length, CharCode, [Char | PaddedChars]) :- Length > 0, Length1 is Length - 1, pad2(Chars, Length1, CharCode, PaddedChars). % Show the header of the table show_header(Length, Labels) :- write_pad(Length, ' '), write(' '), show_header_entries(Labels, Length), nl, show_horizontal_line(Labels, Length). % show an entry of the header show_header_entries([], _Length). show_header_entries([Label | Labels], Length) :- pad(Label, Length, Padded), write(Padded), write(' '), show_header_entries(Labels, Length). % show a horizontal line, e.g. after the header and at the bottom show_horizontal_line(Labels, Length) :- write_pad(Length, ' '), write(' '), show_horizontal_line2(Labels, Length), write('-'), nl. % helper for show_horizontal_line show_horizontal_line2([], _Length). show_horizontal_line2([_Label | Labels], Length) :- write_pad(Length, '-'), write('-'), show_horizontal_line2(Labels, Length). % write N copies of a char write_pad(0, _Char). write_pad(N, Char) :- N > 0, write(Char), N1 is N - 1, write_pad(N1, Char). % pflap tests: % For details on unit test protocols, please see: % http://www.swi-prolog.org/pldoc/package/plunit.html :- begin_tests(pflap). test(sequence) :- firstN(10, sequence(X, [0, 1]), X, Result), Result = [[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0, 1, 0]]. test(sequences_in_range) :- sequences_in_range(Set, 0, 3, [0, 1]), Set == [[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]. test(is_deterministic) :- state_machine_1(Transitions), is_deterministic(Transitions). test(is_deterministic, [fail]) :- state_machine_1n(Transitions), is_deterministic(Transitions). test(is_complete) :- state_machine_1(Transitions), is_complete(Transitions). test(is_complete, [fail]) :- state_machine_1i(Transitions), is_complete(Transitions). test(has_spontaneous) :- state_machine_1s(Transitions), has_spontaneous(Transitions). test(has_spontaneous, [fail]) :- state_machine_1(Transitions), has_spontaneous(Transitions). test(reach, [all(X == [[a,0,a,1,b,0,c], [a,1,b,0,c,1,c]])]) :- state_machine_1(Transitions), length(X, 7), reach(X, a, c, Transitions). test(label_sequence_1, [all(X == [[0,0,0,0],[0,0,1,1],[0,1,1,0],[1,0,0,1],[1,1,0,0],[1,1,1,1]])]) :- state_machine_1(Transitions), length(X, 4), label_sequence(X, a, a, Transitions). test(label_sequence_2, [set(X == [[0,0,0,0],[0,0,0,1],[0,0,1,1],[0,1,1,1],[1,1,1,1]])]) :- state_machine_1s(Transitions), length(X, 4), label_sequence(X, a, b, Transitions). test(generalized_label_sequence, [set(X == [[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,0,1],[0,1,1,1], [1,0,0,0],[1,0,1,0],[1,1,0,1],[1,0,1,1],[1,1,1,0]])]) :- state_machine_1(Transitions), length(X, 4), generalized_label_sequence(X, [a], [b, c], Transitions). test(label_sequence_in_range, [all(X == [[0,0],[1,1],[0,0,0],[0,1,1],[1,1,0],[0,0,0,0], [0,0,1,1],[0,1,1,0],[1,0,0,1],[1,1,0,0],[1,1,1,1]])]) :- state_machine_1(Transitions), label_sequence_in_range(X, 2, 4, [a], [a], Transitions). test(increasing_label_sequence_1) :- state_machine_1(Transitions), firstN(8, increasing_label_sequence(X, a, a, Transitions), X, Result), Result = [[],[0],[0,0],[1,1],[0,0,0],[0,1,1],[1,1,0],[0,0,0,0]]. % above, length(X, _) ensures generation in order of increasing length. test(increasing_label_sequence_2) :- state_machine_1s(Transitions), firstN(8, increasing_label_sequence(X, a, b, Transitions), X, Result), Result = [[],[0],[1],[0,0],[0,1],[1,1],[0,0,0],[0,0,1]]. % above, length(X, _) ensures generation in order of increasing length. test(sipser_fig1_19) :- sipser_fig1_19(Transitions), firstN(8, increasing_label_sequence(X, even, odd, Transitions), X, Result), Result = [[1],[0,1],[1,0],[0,0,1],[0,1,0],[1,0,0],[1,1,1],[0,0,0,1]]. test(sipser_fig1_22) :- sipser_fig1_22(Transitions, Start, End), firstN(5, increasing_generalized_label_sequence(X, [Start], End, Transitions), X, Result), Result = [[0,0,1],[0,0,0,1],[0,0,1,0],[0,0,1,1],[1,0,0,1]]. test(sipser_fig1_27) :- sipser_fig1_27(Transitions, Start, End), firstN(8, increasing_generalized_label_sequence(X, Start, End, Transitions), X, Result), Result = [[1,1],[0,1,1],[1,1,1],[1,0,1],[1,1,0],[0,0,1,1],[0,1,1,1],[0,1,0,1]]. test(sipser_fig1_31) :- sipser_fig1_31(Transitions, Initial, Final), firstN(7, increasing_generalized_label_sequence(X, Initial, Final, Transitions), X, Result), Result = [[1,0,0],[1,0,1],[1,1,0],[1,1,1],[0,1,0,0],[0,1,0,1],[0,1,1,0]]. :- end_tests(pflap). :- run_tests. % User examples :-show_dfa(sipser_fig1_20, 10). :-show_dfa(sipser_fig1_22, 10). :-show_nfa(sipser_fig1_27, 10). :-show_nfa(sipser_fig1_31, 16). :-show_dfa(sipser_fig1_32, 16). /* Sample Output from the above examples: DFA sipser_fig1_20: 0 1 ----------- even | even odd | Initial odd | odd even | Final ----------- examples of strings accepted by sipser_fig1_20: [1] [0,1] [1,0] [0,0,1] [0,1,0] [1,0,0] [1,1,1] [0,0,0,1] [0,0,1,0] [0,1,0,0] DFA sipser_fig1_22: 0 1 ----------- q | q0 q | Initial q0 | q00 q | q00 | q00 q001 | q001 | q001 q001 | Final ----------- examples of strings accepted by sipser_fig1_22: [0,0,1] [0,0,0,1] [0,0,1,0] [0,0,1,1] [1,0,0,1] [0,0,0,0,1] [0,0,0,1,0] [0,0,0,1,1] [0,0,1,0,0] [0,0,1,0,1] NFA sipser_fig1_27: Transitions: q1: [ (q1,0,q1), (q1,1,q1), (q1,1,q2)] Initial q2: [ (q2,0,q3), (q2,q3)] q3: [ (q3,1,q4)] q4: [ (q4,0,q4), (q4,1,q4)] Final examples of strings accepted by sipser_fig1_27: [1,1] [0,1,1] [1,1,1] [1,0,1] [1,1,0] [0,0,1,1] [0,1,1,1] [0,1,0,1] [0,1,1,0] [1,0,1,1] NFA sipser_fig1_31: Transitions: q1: [ (q1,0,q1), (q1,1,q1), (q1,1,q2)] Initial q2: [ (q2,0,q3), (q2,1,q3)] q3: [ (q3,0,q4), (q3,1,q4)] q4: [] Final examples of strings accepted by sipser_fig1_31: [1,0,0] [1,0,1] [1,1,0] [1,1,1] [0,1,0,0] [0,1,0,1] [0,1,1,0] [0,1,1,1] [1,1,0,0] [1,1,0,1] [1,1,1,0] [1,1,1,1] [0,0,1,0,0] [0,0,1,0,1] [0,0,1,1,0] [0,0,1,1,1] DFA sipser_fig1_32: 0 1 ----------- q000 | q000 q001 | Initial q001 | q010 q011 | q010 | q100 q101 | q011 | q110 q111 | q100 | q000 q001 | Final q101 | q010 q011 | Final q110 | q100 q101 | Final q111 | q110 q111 | Final ----------- examples of strings accepted by sipser_fig1_32: [1,0,0] [1,0,1] [1,1,0] [1,1,1] [0,1,0,0] [1,1,0,0] [0,1,0,1] [1,1,0,1] [0,1,1,0] [1,1,1,0] [0,1,1,1] [1,1,1,1] [0,0,1,0,0] [0,1,1,0,0] [1,0,1,0,0] [1,1,1,0,0] */