% RCS $Id: pflap.pl,v 1.22 2007/02/13 07:50:34 keller Exp keller $ % PFLAP: Prolog Finite Automata and Language Analysis Program % Author: Robert Keller, Harvey Mudd College % Installment 2 (includes DFA, NFA, PDA by empty-stack) % Usage: SWI-Prolog is recommended. On knuth this would be % pl -f pflap.pl pflapTests.pl % Edit in your own examples into pflapTests.pl epsilon([]). % We use the empty-list symbol to denote epsilon % A DFA (Deterministic Finite-State Acceptor) is given by a term % % dfa(Q, A, q0, F, T) where % % Q is the list of states % A is the input alphabet % qo is the start state % F is the list of accepting or "final" states % T is a list of transitions: triples, of the form (pre-state, input-symbol, post-state) % Procedures for a DFA: % % testDFA(DFA, [... strings ...]). % tests the DFA for acceptance on strings in the given list % % showAcceptedInputsDFA(DFA, Steps). % shows all string accepted by DFA in Steps or fewer steps. % % minimizeDFA(DFA, Min) % minimizes states of a DFA, resulting in Min. % % showDFA(DFA) % shows the details of DFA. % An NFA (Nondeterministic Finite-State Acceptor) is given by a term % % nfa(Q, A, S, F, T) where % % Q is the list of states % A is the input alphabet % S is set of initial states % F is the list of accepting or "final" states % T is a list of transitions: triples, of the form (pre-state, input-symbol, post-state) % Procedures for an NFA: % % testNFA(NFA, [... strings ...]). % tests the NFA for acceptance on strings in the given list. % % showAcceptedInputsNFA(NFA, Steps). % shows all strings accepted by NFA in Steps or fewer steps. % % showNFA(NFA) % shows the details of NFA. % A PDA ((non-deterministic) Pushdown Acceptor) is given by a term % % pda(Q, Z, s0, A, q0, F, T) where % % Q is the list of control states % Z is the stack alphabet % S is the initial stack symbol % A is the input alphabet % q0 is the initial control state % F is the list of accepting or "final" states % T is a list of transitions: 5-tuples, of the form % (pop, pre-state, input-symbol, push, post-state) % where pop is a symbol in the stack alphabet that is popped off when this transition occurs % pre-state is the control state enabling this transition % input-symbol is either in the input alphabet or is epsilon (here represented as []) % push is a sequence of symbols that are pushed when this transition occurs % post-state is the control state following this transition % Procedures for PDA: % % testPDAES(PDA, [... strings ...]). % Tests PDA on strings in the given list, with acceptance by empty-stack (ES). % % showAcceptedInputsPDAES(PDA, Steps). % Shows all strings accepted by PDA by empty-stack in Steps or fewer steps. % % showPDA(PDA) % shows the details of PDA. % Test DFA on specific input sequences. testDFA(DFA, InputStrings) :- showDFA(DFA), tryAllDFA(DFA, InputStrings). tryAllDFA(DFA, InputStrings) :- DFA = dfa(_States, _Alphabet, Initial, Final, Transitions), member(InputString, InputStrings), nl, write('Input string: '), write(InputString), atom_chars(InputString, CharSequence), numify(CharSequence, InputSequence), simDFA(Transitions, Initial, StateSequence, InputSequence, Last), ( member(Last, Final) -> true ; write(' not') ), write(' accepted by'), nl, write('state sequence '), write(StateSequence), write('.'), nl, nl, fail. tryAllDFA(_DFA, _InputStrings). % Show the sequences accepted by a DFA up to a specified maximum length % The sequences will be shown in order of increasing length. showAcceptedInputsDFA(DFA, MaxSteps) :- showDFA(DFA), nl, write('Sequences accepted to length '), write(MaxSteps), write(':'), nl, acceptsInNoMoreThanDFA(DFA, MaxSteps, Sequences), sortByLength(Sequences, SortedSequences), writeSet(SortedSequences). showAcceptedInputsDFA(_, _). % acceptsInNoMoreThanDFA(DFA, MaxSteps, Sequences) means % determine the sequences accepted by DFA in no more than MaxSteps steps. % mode acceptsInNoMoreThanDFA(+DFA, +MaxSteps, -Sequences) acceptsInNoMoreThanDFA(DFA, MaxSteps, Sequences) :- acceptsInNoMoreThanDFA(DFA, 0, MaxSteps, [], Sequences). % Auxiliary function for acceptsInNoMoreThan. It is called with % Steps increasing, up to a maximum of MaxSteps. % An accumulated list is given, and the sequences are added to % the accumulator with each successive call. acceptsInNoMoreThanDFA(DFA, Steps, MaxSteps, Accum, Sequences) :- Steps =< MaxSteps, acceptsInExactlyDFA(DFA, Steps, Sequences1), union(Sequences1, Accum, NewAccum), NextSteps is Steps + 1, acceptsInNoMoreThanDFA(DFA, NextSteps, MaxSteps, NewAccum, Sequences). acceptsInNoMoreThanDFA(_DFA, Steps, MaxSteps, Sequences, Sequences) :- Steps > MaxSteps. % acceptsInExactlyDFA(DFA, Steps, Set) means % Set is the set of input sequences accepted by DFA in exactly Steps steps. % mode acceptsInExactlyDFA(+DFA, +Steps, -Set) acceptsInExactlyDFA(DFA, Steps, Set) :- setof1(InputSequence, dfaAccepts(DFA, Steps, InputSequence), Set). % dfaAccepts(DFA, Steps, InputSequence) means dfaAccepts(DFA, Steps, InputSequence) :- dfaAccepts(DFA, Steps, _StateSequence, InputSequence). % dfaAccepts(DFA, Steps, StateSequence, InputSequence) means % DFA accepts InputSequence in Steps with StateSequence % mode dfaAccepts(+DFA, +Steps, -StateSequence, -InputSequence) dfaAccepts(DFA, Steps, StateSequence, InputSequence) :- dfaFinalStates(DFA, Final), dfaReaches(DFA, Steps, StateSequence, InputSequence, Last), member(Last, Final). % DFA reaches Last state in Steps steps % Steps must be instantiated. InputSequence is the input sequence % and StateSequence is the state sequence. dfaReaches(DFA, Steps, StateSequence, InputSequence, Last) :- dfaInitialState(DFA, Initial), dfaTransitions(DFA, Transitions), simDFA( Steps, Transitions, Initial, StateSequence, InputSequence, Last). % simDFA(Steps, Transitions, Initial, StateSequence, InputSequence, Last) % simulates DFA for a Steps steps. InputSequence is the % resulting input sequence and StateSequence is the state sequence. % Last is the last state, for convenience. % The base case: no steps simDFA(0, _Transitions, Q1, [Q1], [], Q1). % The inductive case: 1 or more steps simDFA(Steps, Transitions, Q1, [Q1 | StateSequence], [A | InputSequence], Last) :- Steps > 0, member((Q1, A, Q2), Transitions), RemainingSteps is Steps-1, simDFA(RemainingSteps, Transitions, Q2, StateSequence, InputSequence, Last). % simDFA(Transitions, Initial, StateSequence, InputSequence, Last) % simulates DFA on a given InputSequence. % StateSequence is the resulting state sequence. % Last is the last state, for convenience. % The base case: empty sequence simDFA(_Transitions, Q1, [Q1], [], Q1). % The inductive case: 1 or more steps simDFA(Transitions, Q1, [Q1 | StateSequence], [A | InputSequence], Last) :- member((Q1, A, Q2), Transitions), simDFA(Transitions, Q2, StateSequence, InputSequence, Last). % Minimize a DFA minimizeDFA(dfa(Q, A, S, F, T), dfa(FinalPartition, A, Initial, Final, NewTrans)) :- subtract(Q, F, N), % N = Q - F (set difference) partitionSequence([F, N], T, A, FinalPartition), % assumes T is complete makeTransitions(FinalPartition, T, A, FinalPartition, NewTrans), findSubset(FinalPartition, S, Initial), containFinal(FinalPartition, F, Final). containFinal([], _, []). containFinal([Subset | Subsets], F, [Subset | More]) :- Subset = [State | _], member(State, F), !, containFinal(Subsets, F, More). containFinal([_ | Subsets], F, More) :- containFinal(Subsets, F, More). makeTransitions([], _T, _A, _P, []). makeTransitions([Subset | Subsets], Trans, A, Partition, NewTrans) :- makeTransitions1(A, Subset, Trans, Partition, Trans1), makeTransitions(Subsets, Trans, A, Partition, Trans2), append(Trans1, Trans2, NewTrans). makeTransitions1([], _Subset, _Trans, _Partition, []). makeTransitions1([Letter | Letters], Subset, Trans, Partition, [(Subset, Letter, Target) | NewTrans]) :- Subset = [State | _], member((State, Letter, NextState), Trans), findSubset(Partition, NextState, Target), makeTransitions1(Letters, Subset, Trans, Partition, NewTrans). findSubset([Set | _Sets], State, Set) :- member(State, Set), !. findSubset([_Set | Sets], State, Set) :- findSubset(Sets, State, Set). partitionSequence(Partition, T, A, FinalPartition) :- repartition(Partition, T, A, Partition, NewPartition), ( equivPartitions(Partition, NewPartition) -> FinalPartition = Partition ; partitionSequence(NewPartition, T, A, FinalPartition) ). equivPartitions(P1, P2) :- sort(P1, P1s), sort(P2, P2s), P1s = P2s. repartition([], _T, _A, _OldPartition, []). repartition([Subset | Subsets], T, A, OldPartition, NewPartition) :- reverse(Subset, SubsetRev), repartition1(SubsetRev, T, A, OldPartition, [], Increment), repartition(Subsets, T, A, OldPartition, NewSubsets), append(Increment, NewSubsets, NewPartition). repartition1([], _T, _A, _OldPartition, Subsets, Subsets). repartition1([State | States], T, A, OldPartition, Subsets, NewSubsets) :- addToSubset(Subsets, T, A, OldPartition, State, Subsets1), repartition1(States, T, A, OldPartition, Subsets1, NewSubsets). addToSubset([], _T, _A, _OldPartition, State, [[State]]). addToSubset([Subset | Subsets], T, A, OldPartition, State, [[State | Subset] | Subsets]) :- alike(State, T, A, OldPartition, Subset), !. addToSubset([Subset | Subsets], T, A, OldPartition, State, [Subset | NewSubsets]) :- addToSubset(Subsets, T, A, OldPartition, State, NewSubsets). alike(State, T, A, OldPartition, [State2 | _Others]) :- allAlike(A, T, OldPartition, State, State2), !. allAlike([], _T, _OldPartition, _State, _State2). allAlike([Letter | Letters], Trans, OldPartition, State, State2) :- member((State, Letter, NextState), Trans), member((State2, Letter, NextState2), Trans), equivalent(OldPartition, NextState, NextState2), allAlike(Letters, Trans, OldPartition, State, State2). equivalent(Subsets, State, State2) :- locate(Subsets, State, Subset), member(State2, Subset). locate([Subset | _Subsets], State, Subset) :- member(State, Subset), !. locate([_Subset | Subsets], State, Subset) :- locate(Subsets, State, Subset). % Test NFA on specific input sequences. testNFA(NFA, InputStrings) :- showNFA(NFA), member(InputString, InputStrings), atom_chars(InputString, CharSequence), numify(CharSequence, InputSequence), tryallNFA(NFA, InputString, InputSequence), fail. testNFA(_NFA, _InputStrings). % Fail-loop to try all possible state sequences for given input tryallNFA(NFA, InputString, InputSequence) :- NFA = nfa(_States, _Alphabet, InitialSet, Final, Transitions), member(Initial, InitialSet), simNFA(Transitions, Initial, StateSequence, InputSequence, Last), member(Last, Final), !, write('Input string '), write(InputString), write(' accepted by'), nl, write('state sequence '), write(StateSequence), write('.'), nl, nl. tryallNFA(_NFA, InputString, _InputSequence) :- write('Input string '), write(InputString), write(' not accepted (no accepting sequence).'), nl, nl. % Show the sequences accepted by a NFA up to a specified maximum % nubmer of steps, where epsilon transitions count as a step. % The sequences will be shown in order of increasing length. showAcceptedInputsNFA(NFA, MaxSteps) :- showNFA(NFA), nl, write('Sequences accepted in up to '), write(MaxSteps), write(' steps:'), nl, acceptsInNoMoreThanNFA(NFA, MaxSteps, Sequences), sortByLength(Sequences, SortedSequences), writeSet(SortedSequences). showAcceptedInputsNFA(_, _). % acceptsInNoMoreThanNFA(NFA, MaxSteps, Sequences) means % determine the sequences accepted by NFA in no more than MaxSteps steps. % mode acceptsInNoMoreThanNFA(+NFA, +MaxSteps, -Sequences) acceptsInNoMoreThanNFA(NFA, MaxSteps, Sequences) :- acceptsInNoMoreThanNFA(NFA, 0, MaxSteps, [], Sequences). % Auxiliary function for acceptsInNoMoreThan. It is called with % Steps increasing, up to a maximum of MaxSteps. % An accumulated list is given, and the sequences are added to % the accumulator with each successive call. acceptsInNoMoreThanNFA(NFA, Steps, MaxSteps, Accum, Sequences) :- Steps =< MaxSteps, acceptsInExactly(NFA, Steps, Sequences1), union(Sequences1, Accum, NewAccum), NextSteps is Steps + 1, acceptsInNoMoreThanNFA(NFA, NextSteps, MaxSteps, NewAccum, Sequences). acceptsInNoMoreThanNFA(_NFA, Steps, MaxSteps, Sequences, Sequences) :- Steps > MaxSteps. % acceptsInExactly(NFA, Steps, Set) means % Set is the set of input sequences accepted by NFA in exactly Steps steps. % mode acceptsInExactly(+NFA, +Steps, -Set) acceptsInExactly(NFA, Steps, Set) :- setof1(InputSequence, nfaAccepts(NFA, Steps, InputSequence), Set). % nfaAccepts(NFA, Steps, InputSequence) means nfaAccepts(NFA, Steps, InputSequence) :- nfaAccepts(NFA, Steps, _StateSequence, InputSequence). % nfaAccepts(NFA, Steps, StateSequence, InputSequence) means % NFA accepts InputSequence in Steps with StateSequence % mode nfaAccepts(+NFA, +Steps, *StateSequence, *InputSequence) nfaAccepts(NFA, Steps, StateSequence, InputSequence) :- nfaFinalStates(NFA, Final), nfaReaches(NFA, Steps, StateSequence, InputSequence, Last), member(Last, Final). % NFA reaches Last state in Steps steps % Steps must be instantiated. InputSequence is the input sequence % and StateSequence is the state sequence. nfaReaches(NFA, Steps, StateSequence, InputSequence, Last) :- nfaInitialStates(NFA, InitialSet), nfaTransitions(NFA, Transitions), member(Initial, InitialSet), simNFA( Steps, Transitions, Initial, StateSequence, InputSequence, Last). % simNFA(Steps, Transitions, Initial, StateSequence, InputSequence, Last) % simulates NFA for a Steps steps. InputSequence is the % resulting input sequence and StateSequence is the state sequence. % Last is the last state, for convenience. % The base case: empty sequence simNFA(0, _Transitions, Q1, [Q1], [], Q1). simNFA(Steps, Transitions, Q1, [Q1 | StateSequence], [], Last) :- Steps > 0, epsilon(E), member((Q1, E, Q2), Transitions), RemainingSteps is Steps-1, simNFA(RemainingSteps, Transitions, Q2, StateSequence, [], Last). % The inductive case: 1 or more steps simNFA(Steps, Transitions, Q1, [Q1 | StateSequence], [A | InputSequence], Last) :- Steps > 0, member((Q1, A, Q2), Transitions), \+epsilon(A), RemainingSteps is Steps-1, simNFA(RemainingSteps, Transitions, Q2, StateSequence, InputSequence, Last). simNFA(Steps, Transitions, Q1, [Q1 | StateSequence], InputSequence, Last) :- Steps > 0, member((Q1, A, Q2), Transitions), epsilon(A), RemainingSteps is Steps-1, simNFA(RemainingSteps, Transitions, Q2, StateSequence, InputSequence, Last). % simNFA(Transitions, Initial, StateSequence, InputSequence, Last) % simulates NFA on a given InputSequence. % StateSequence is the resulting state sequence. % Last is the last state, for convenience. % The base case: empty sequence simNFA(_Transitions, Q1, [Q1], [], Q1). % epsilon transitions from start state simNFA(Transitions, Q1, [Q1], [], Q2) :- epsilon(E), member((Q1, E, Q2), Transitions). % The inductive case: 1 or more steps % non-epsilon transitions simNFA(Transitions, Q1, [Q1 | StateSequence], [A | InputSequence], Last) :- member((Q1, A, Q2), Transitions), \+epsilon(A), simNFA(Transitions, Q2, StateSequence, InputSequence, Last). % epsilon transitions simNFA(Transitions, Q1, [Q1 | StateSequence], InputSequence, Last) :- member((Q1, E, Q2), Transitions), epsilon(E), simNFA(Transitions, Q2, StateSequence, InputSequence, Last). % Display a DFA. showDFA(dfa(States, Alphabet, Initial, Final, Transitions)) :- write('DFA: '), nl, write('States = '), write(States), nl, write('Alphabet = '), write(Alphabet), nl, write('Initial = '), write(Initial), nl, write('Final = '), write(Final), nl, write('Transitions:'), nl, showTransitions(Transitions). % Display an NFA. showNFA(nfa(States, Alphabet, InitialSet, Final, Transitions)) :- write('NFA: '), nl, write('States = '), write(States), nl, write('Alphabet = '), write(Alphabet), nl, write('Initial State Set= '), write(InitialSet), nl, write('Final = '), write(Final), nl, write('Transitions:'), nl, showTransitions(Transitions). % Display the transitions of a DFA or NFA showTransitions([]). showTransitions([(Q1, A, Q2) | Transitions]) :- write((Q1, A, Q2)), nl, showTransitions(Transitions). % Component-extraction functions % Initial is initial state of DFA dfaInitialState(dfa(_States, _Alphabet, Initial, _Final, _Transitions), Initial). % Final is set of accepting states of DFA dfaFinalStates(dfa(_States, _Alphabet, _Initial, Final, _Transitions), Final). % Transitions is set of transitions of DFA dfaTransitions(dfa(_States, _Alphabet, _Initial, _Final, Transitions), Transitions). % Initial is initial state of NFA nfaInitialStates(nfa(_States, _Alphabet, InitialSet, _Final, _Transitions), InitialSet). % Final is set of accepting states of NFA nfaFinalStates(nfa(_States, _Alphabet, _InitialSet, Final, _Transitions), Final). % Transitions is set of transitions of NFA nfaTransitions(nfa(_States, _Alphabet, _InitialSet, _Final, Transitions), Transitions). % Test PDA on specific input sequences, with empty-stack acceptance. testPDAES(PDA, InputStrings) :- showPDA(PDA), member(InputString, InputStrings), atom_chars(InputString, CharSequence), numify(CharSequence, InputSequence), tryallPDA(PDA, InputString, InputSequence), fail. testPDAES(_PDA, _InputSequences). % Fail-loop to try all possible state sequences for given input % pdaes accepts by empty stack, so no final states are given tryallPDA(PDA, InputString, InputSequence) :- PDA = pda(_States, _StackAlphabet, InitialStack, _Alphabet, InitialState, _AcceptStates, Transitions), simPDA(Transitions, ([InitialStack], InitialState), StateSequence, InputSequence, ([], _FinalState)), !, write('Input string '), write(InputString), nl, write(' accepted by'), nl, write('state sequence '), write(StateSequence), write('.'), nl, nl. tryallPDA(_PDA, InputString, _InputSequence) :- write('Input string '), write(InputString), nl, write(' not accepted.'), nl, nl. % simPDA(Transitions, Initial, StateSequence, InputSequence, Last) % simulates PDA on a given InputSequence. % StateSequence is the resulting state sequence. % Last is the last state, for convenience. % The base case: empty sequence simPDA(_Transitions, (Stack, State), [(Stack, State)], [], (Stack, State)). % The inductive case: 1 or more steps % non-epsilon transitions simPDA(Transitions, ([Top | Stack], State), [([Top | Stack], State)| StateSequence], [A | InputSequence], Last) :- member((Top, State, A, Push, NewState), Transitions), \+epsilon(A), append(Push, Stack, NewStack), simPDA(Transitions, (NewStack, NewState), StateSequence, InputSequence, Last). % epsilon simPDA(Transitions, ([Top | Stack], State), [([Top | Stack], State) | StateSequence], InputSequence, Last) :- epsilon(E), member((Top, State, E, Push, NewState), Transitions), append(Push, Stack, NewStack), simPDA(Transitions, (NewStack, NewState), StateSequence, InputSequence, Last). % simPDA(Steps, Transitions, Initial, StateSequence, InputSequence, Last) % simulates for a number of steps, determining the input sequence % StateSequence is the resulting state sequence. % Last is the last state, for convenience. % The base case: empty sequence simPDA(0, _Transitions, (Stack, State), [(Stack, State)], [], (Stack, State)). % The inductive case: 1 or more steps % non-epsilon transitions simPDA(Steps, Transitions, ([Top | Stack], State), [([Top | Stack], State)| StateSequence], [A | InputSequence], Last) :- Steps > 0, member((Top, State, A, Push, NewState), Transitions), \+epsilon(A), append(Push, Stack, NewStack), Steps1 is Steps - 1, simPDA(Steps1, Transitions, (NewStack, NewState), StateSequence, InputSequence, Last). % epsilon transition simPDA(Steps, Transitions, ([Top | Stack], State), [([Top | Stack], State) | StateSequence], InputSequence, Last) :- Steps > 0, epsilon(E), member((Top, State, E, Push, NewState), Transitions), append(Push, Stack, NewStack), Steps1 is Steps - 1, simPDA(Steps1, Transitions, (NewStack, NewState), StateSequence, InputSequence, Last). % Display a PDA. showPDA(pda(States, StackAlphabet, InitialStack, Alphabet, InitialState, AcceptStates, Transitions)) :- write('PDA: '), nl, write('States = '), write(States), nl, write('StackAlphabet = '), write(StackAlphabet), nl, write('Initial Stack = '), write(InitialStack), nl, write('Alphabet = '), write(Alphabet), nl, write('Initial State = '), write(InitialState), nl, write('Accept States = '), write(AcceptStates), nl, write('Transitions:'), nl, showPDAtransitions(Transitions). % Display the transitions of a PDA. showPDAtransitions([]). showPDAtransitions([(Top, Q1, A, Push, Q2) | Transitions]) :- write((Top, Q1, A, Push, Q2)), nl, showPDAtransitions(Transitions). % Show the sequences accepted by a PDA using empty-stack up to a specified maximum % nubmer of steps, where epsilon transitions count as a step. % The sequences will be shown in order of increasing length. showAcceptedInputsPDAES(PDA, MaxSteps) :- showPDA(PDA), nl, write('Sequences accepted in up to '), write(MaxSteps), write(' steps:'), nl, acceptsInNoMoreThanPDAES(PDA, MaxSteps, Sequences), sortByLength(Sequences, SortedSequences), writeSet(SortedSequences). showAcceptedInputsPDAES(_, _). % acceptsInNoMoreThanPDAES(PDA, MaxSteps, Sequences) means % determine the sequences accepted by PDA in no more than MaxSteps steps. % using empty-stack acceptance % mode acceptsInNoMoreThanPDAES(+PDA, +MaxSteps, -Sequences) acceptsInNoMoreThanPDAES(PDA, MaxSteps, Sequences) :- acceptsInNoMoreThanPDAES(PDA, 0, MaxSteps, [], Sequences). % Auxiliary function for acceptsInNoMoreThan. It is called with % Steps increasing, up to a maximum of MaxSteps. % An accumulated list is given, and the sequences are added to % the accumulator with each successive call. acceptsInNoMoreThanPDAES(PDA, Steps, MaxSteps, Accum, Sequences) :- Steps =< MaxSteps, acceptsInExactlyPDAES(PDA, Steps, Sequences1), union(Sequences1, Accum, NewAccum), NextSteps is Steps + 1, acceptsInNoMoreThanPDAES(PDA, NextSteps, MaxSteps, NewAccum, Sequences). acceptsInNoMoreThanPDAES(_PDA, Steps, MaxSteps, Sequences, Sequences) :- Steps > MaxSteps. % acceptsInExactlyPDAES(PDA, Steps, Set) means % Set is the set of input sequences accepted by PDAES in exactly Steps steps. % mode acceptsInExactlyES(+PDA, +Steps, -Set) acceptsInExactlyPDAES(PDA, Steps, Set) :- setof1(InputSequence, pdaAcceptsES(PDA, Steps, InputSequence), Set). % pdaAcceptsES(PDA, Steps, InputSequence) means that PDA accepts % a specific input sequence by empty stack in the indicated number of steps. pdaAcceptsES(PDA, Steps, InputSequence) :- pdaAcceptsES(PDA, Steps, _StateSequence, InputSequence). % pdaAcceptsES(PDA, Steps, StateSequence, InputSequence) means % PDAES accepts InputSequence in Steps with StateSequence % by empty stack % mode pdaAcceptsES(+PDA, +Steps, *StateSequence, *InputSequence) pdaAcceptsES(PDA, Steps, StateSequence, InputSequence) :- pdaReaches(PDA, Steps, StateSequence, InputSequence, ([], _FinalState)). % PDA reaches Last (Stack, State) combination in Steps steps % Steps must be instantiated. InputSequence is the input sequence % and StateSequence is the state sequence. pdaReaches(PDA, Steps, StateSequence, InputSequence, Last) :- pdaInitialState(PDA, Initial), pdaTransitions(PDA, Transitions), simPDA( Steps, Transitions, Initial, StateSequence, InputSequence, Last). % Initial is initial state of PDA pdaInitialState(pda(_States, _StackAlphabet, InitialStack, _Alphabet, InitialState, _AcceptStates, _Transitions), ([InitialStack], InitialState)). % Transitions is set of transitions of a PDA pdaTransitions(pda(_States, _StackAlphabet, _InitialStack, _Alphabet, _InitialState, _AcceptStates, Transitions), Transitions). % % Utility predicates % % Utility for computing setof elements satisfying a given predicate. % Returns [] if there is no such element, unlike setof, which just % fails in that case. setof1(Element, Pred, Set) :- setof(Element, Pred, Set) -> true ; Set = []. % Set is the union of Set1 and Set2. % mode union(+Set1, +Set2, -Set) union(Set1, Set2, Set) :- setof1(X, (member(X, Set1); member(X, Set2)), Set). % Return the second items of a list of pairs mapSecond([], []). mapSecond([(_Length, Item) | Pairs], [Item | Items]) :- mapSecond(Pairs, Items). % Sort a list of lists by increasing length sortByLength(In, Out) :- setof1((Length, Item), (member(Item, In), length(Item, Length)), Out1), mapSecond(Out1, Out). % Write a list line-by-line. writeSet([]) :- nl. writeSet([A | X]) :- writeSequence(A), nl, writeSet(X). writeSequence([]). writeSequence([A | X]) :- write(A), writeSequence(X). % The purpose of numify is to convert any numeric digit atoms in a sequence to numbers. % It is more convenient to use number digits in the transition tables. % However, when a string is converted using atom_chars, atoms rather than digits % will result. These are then converted using numify so that matching takes place % when doing member on tables. numify([], []). numify([A | As], [N | Ns]) :- numify1(A, N), numify(As, Ns). numify1('0', 0) :- !. numify1('1', 1) :- !. numify1('2', 2) :- !. numify1('3', 3) :- !. numify1('4', 4) :- !. numify1('5', 5) :- !. numify1('6', 6) :- !. numify1('7', 7) :- !. numify1('8', 8) :- !. numify1('9', 9) :- !. numify1(X, X).