/**************************************************************** % Author: Amanda Ricketson % File: npda5.pl (hw9-1 Problem 3.22) % Implementation of a pushdown automaton in prolog % for L={a^m b^2m | m = 0,1,2,...} Usage: ?- start. PDA for {a^m b^2m, m = 0,1,2,...}: Input your word: aaabbbbbb. s-a-e-s-[a, a] Stack contents: [a, a] s-a-e-s-[a, a] Stack contents: [a, a, a, a] s-a-e-s-[a, a] Stack contents: [a, a, a, a, a, a] s-b-a-f-e Stack contents: [a, a, a, a, a] f-b-a-f-e Stack contents: [a, a, a, a] f-b-a-f-e Stack contents: [a, a, a] f-b-a-f-e Stack contents: [a, a] f-b-a-f-e Stack contents: [a] f-b-a-f-e Stack contents: [] Word Accepted! Continue? (y/n) n. Yes ***************************************************************/ /**************************************************************** % stack predicates ***************************************************************/ :-dynamic(stack/1). stack([]). empty_stack:- stack([]). print_stack:- stack(L), write('Stack contents: '), write(L). push(H):- % works if pushing atom or list stack(L), (atom(H) -> New = [H|L] ; append(H,L,New)), retract(stack(_)), assert(stack(New)). pop:- (empty_stack -> write('Stack is empty.\n')) ; (stack([_|L]), retract(stack(_)), assert(stack(L))). look(Top):- stack([Top|_]). init_stack:- retract(stack(_)), assert(stack([])). % initalize stack to empty /**************************************************************** % pushdown automaton definition: L = {a^m b^2m, m = 0,1,2,... } ***************************************************************/ t((s,a,e),(s,[a,a])). % in start: read a & push aa, stay in s t((s,b,a),(f,e)). % in state s: read b, pop a, move to state f t((f,b,a),(f,e)). % in state s: read b & pop a, stay in state f favorable(f). % state f is favorable start(s). % state s is start /**************************************************************** % pushdown automaton printing predicates ***************************************************************/ print_push:- write('Pushdown Automata: \n'), write('States: '), print_states, write('Alphabet: '), print_alphabet, write('Transitions: '), nl, print_transition, write('Favorable states: '), print_favorable, write('Start State: '), print_start. print_states:- findall(X,t((X,_,_),(_,_)),L),sort(L,R),write(R),nl. print_alphabet:- findall(X,t((_,X,_),(_,_)),L),sort(L,R),write(R),nl. print_transition:- findall([[X,Let,Po],[Y,Pu]], t((X,Let,Po),(Y,Pu)), R), sort(R,R2), forall(member(X,R2),(write(X),nl)). print_favorable:- findall(X,favorable(X),L),write(L),nl. print_start:- start(X),write(X),nl. /**************************************************************** % pushdown automaton checking predicates % check_word(state, word_as_list) ***************************************************************/ check_word(S,[]):- % word is finished & stack empty favorable(S), empty_stack. check_word(S,[H|T]):- % push onto stack t((S,H,e),(Q,NewTop)),not(NewTop=e),push(NewTop), write(S-H-e-Q-NewTop),write(' '),print_stack,nl, check_word(Q,T). check_word(S,[H|T]):- % pop off of stack look(Top),t((S,H,Top),(Q,e)),pop, write(S-H-Top-Q-e),write(' '),print_stack,nl, check_word(Q,T). /**************************************************************** % pushdown automaton execution predicates ***************************************************************/ start:- init_stack, % make sure stack is empty write('PDA for {a^m b^2m, m = 0,1,2,...}: \n\n'),input. input:- write('Input your word: '),read(W), atom_chars(W,L), start(S), ( (check_word(S,L) -> write('Word Accepted!\n')) ; write('Word not accepted.\n') ), (continue,init_stack,input ; true). continue:- write('Continue? (y/n) '),read(R),R=y.