/******************************************** File: pda7.pl Author: Cristina Harko Date: 11/18/2003 Title: A Pushdown Automaton for a^m b^k c^m (Exercise 3.42 a), page 117) ?- start. PushDown accepting a^m b^k c^m Input your word:[a,a,b,c,c]. s-a-e-r-c Stack is: [c] r-a-e-r-c Stack is: [c, c] r-b-e-t-e Stack is: [e, c, c] r-b-e-t-e Stack is: [c, c] t-c-c-f-e Stack is: [c] f-c-c-f-e Stack is: [] Yes ***********************************************/ t((s,$,e),(f,e)). t((s,b,e),(q,e)). t((q,$,e),(f,e)). t((s,a,e),(r,c)). t((r,a,e),(r,c)). t((r,b,e),(t,e)). t((t,b,e),(t,e)). t((t,c,c),(f,e)). t((r,c,c),(f,e)). t((f,c,c),(f,e)). t((f,$,e),(f,e)). start(s). favorable(f). % Word is accepted if: % Word is finished and Stack is empty and Automaton is in favorable state check_word(S,[]):- favorable(S),empty_stack. % If e then push something in the stack check_word(S,[H|T]):- t((S,H,e),(Q,NewTop)),push(NewTop), write(S-H-e-Q-NewTop),print_stack,nl, check_word(Q,T). % look at top of stack, find next step if e then pop check_word(S,[H|T]):- look(Top),t((S,H,Top),(Q,e)),pop, write(S-H-Top-Q-e),print_stack,nl, check_word(Q,T). % Ask for a word see if it is accepted (yes/no). start:- write('PushDown accepting a^m b^k c^m'),nl, write('Input your word:'),read(W), start(S),check_word(S,W). % declare stack as "dynamic" so you can change it :-dynamic(stack/1). % intially the stack is empty. stack([]). % push something in your stack. Remove old stack and put new stack instead push(H):- stack(L),New=[H|L],retract(stack(_)),assert(stack(New)). % pop something out of the stack. Do not care what pop:- stack([_|T]),retract(stack(_)),assert(stack(T)). % check if stack is empty empty_stack:- stack([]). % print the stack print_stack:- stack(L),write(' Stack is: '),write(L). % look at the top of the stack. Do not change stack look(Top):- stack([Top|_]).