Knowledge Base

/** * prob1_ii.pl * * Author: * Description: An NFA simulator. Simulates an NFA that has been defined using * the 'start', 'final', and 'trans' predicates. **/ /** * accept(?Input) * * Determine whether an input list of atoms / string is accepted by the NFA. * **/ accept(Input) :- atom_codes(X, Input), atom_chars(X, Y), start(State), once(acceptFrom(State, Y)). /** * acceptFrom(?CurrState, ?String) * * Determine whether a string can be accepted by the NFA when * it is currently in a particular state. * * Note that empty transitions must be handled by a special * clause. **/ acceptFrom(CurrState, []) :- final(CurrState). acceptFrom(CurrState, [CurrSymb|Rest]) :- trans(CurrState, CurrSymb, NextState), acceptFrom(NextState, Rest). /** * start(?State) * * Specify the start state of the NFA. **/ start(state(1)). /** * final(?State) * * Specify the final states of the NFA. **/ final(state(7)). /** * trans(?Source, ?Symbol, ?Destination) * * Specify the transitions that constitute the NFA. * * Note: Empty transitions can be specified by using the special atom 'empty' * as the second argument Symbol. * * e.g. trans(state(1), empty, state(2)). **/ trans(state(1), a, state(2)). trans(state(2), b, state(4)). trans(state(1), b, state(3)). trans(state(3), a, state(4)). trans(state(4), a, state(5)). trans(state(5), b, state(7)). trans(state(4), b, state(6)). trans(state(6), a, state(7)).

Queries

accept("abba"). accept([b,a,a,b]). accept("aaaa"). accept([b,b,b,b]).

Run

Output

Knowledge Base

/** * prob1_iii.pl * * Author: * Description: An NFA simulator. Simulates an NFA that has been defined using * the 'start', 'final', and 'trans' predicates. **/ /** * accept(?Input) * * Determine whether an input string is accepted by the NFA. **/ run :- read(Input), accept(Input). accept(Input) :- atom_codes(X, Input), atom_chars(X, Y), start(State), once(acceptFrom(State, Y)). /** * acceptFrom(?CurrState, ?String) * * Determine whether a string can be accepted by the NFA when * it is currently in a particular state. * * Note that empty transitions must be handled by a special * clause. **/ acceptFrom(CurrState, []) :- final(CurrState). acceptFrom(CurrState, [CurrSymb|Rest]) :- trans(CurrState, CurrSymb, NextState), acceptFrom(NextState, Rest). /** * start(?State) * * Specify the start state of the NFA. **/ start(state(1)). /** * final(?State) * * Specify the final states of the NFA. **/ final(state(4)). /** * trans(?Source, ?Symbol, ?Destination) * * Specify the transitions that constitute the NFA. * * Note: Empty transitions can be specified by using the special atom 'empty' * as the second argument Symbol. * * e.g. trans(state(1), empty, state(2)). **/ trans(state(1), a, state(2)). trans(state(2), b, state(4)). trans(state(1), b, state(3)). trans(state(3), a, state(4)). trans(state(4), a, state(5)). trans(state(5), b, state(4)). trans(state(4), b, state(6)). trans(state(6), a, state(4)).

Queries

accept("abba"). accept("ababab"). accept(""). accept("abbaaa").

Run

Output

Knowledge Base

/** * prob2.pl * * Description: A lexical analyser to determine valid inputs to a calculator. **/ run :- read(Input), accept(Input). accept(Input) :- atom_codes(X, Input), atom_chars(X, Y), start(State), once(acceptFrom(State, Y)). acceptFrom(CurrState, []) :- endWrite(CurrState,empty,state(1)). acceptFrom(CurrState, [CurrSymb|Rest]) :- trans(CurrState, CurrSymb, NextState), endWrite(CurrState, CurrSymb, NextState), acceptFrom(NextState, Rest). /** * start(?State) * * Specify the start state of the NFA. **/ start(state(1)). /** * final(?State,?Print) * * Specifies the final states of the NFA, and what to print. **/ final(state(2), 'NUMBER'). final(state(3), 'NUMBER'). final(state(4), 'OPERATOR'). final(state(5), 'OPERATOR'). final(state(6), 'INVALID'). /** * endWrite(?Symbol,?State) * * If we're in the start state, print out the last state we were in. * Otherwise, print the character. **/ endWrite(state(1),_,state(1)). endWrite(X,_,state(1)) :- final(X, Y), write(' '), write_ln(Y). endWrite(_,X,_) :- write(X). /** * trans(?Source, ?Symbol, ?Destination) * * Specify the transitions that constitute the NFA. * * Note: Empty transitions can be specified by using the special atom 'empty' * as the second argument Symbol. * * e.g. trans(state(1), empty, state(2)). **/ trans(_ , X , state(1)) :- member(X, [' ','\t']). trans(state(1), '0' , state(2)). trans(state(1), X , state(3)) :- member(X, ['1','2','3','4','5','6','7','8','9']). trans(state(3), X , state(3)) :- member(X, ['1','2','3','4','5','6','7','8','9','0']). trans(state(4), X , state(3)) :- member(X, ['1','2','3','4','5','6','7','8','9']). trans(state(1), '-' , state(4)). trans(state(1), X , state(5)) :- member(X, ['+','/','*','=']). trans(_ , _ , state(6)).

Queries

accept(""). accept("0"). accept("01"). accept("-0"). accept("1"). accept("-1"). accept("1 + 3"). accept("-"). accept("+"). accept("++").

Run

Output