/********************************************** % Author: Intisar Bashir % File: npda6.pl (Hwk_9 Exc_3.20) % Representing a NPDA for {a^nbw | |bw|=n} % Alphabet = {a,b} States = {s,f} % Favorable={f} start is state s. ***********************************************/ t((s,a,e),(s,a)). % push a t((s,b,a),(f,e)). % pop a t((f,b,a),(f,e)). % pop a t((f,a,a),(f,e)). % pop a favorable(f). start(s). % check_word(State,Word,Stack). % Accepted if: Word is finished, Stack is empty, Automaton is in favorable state check_word(Q,[],[]):- favorable(Q). % t((s,a,e),(s,a)). %push check_word(Q,[H|T],Stack):- t((Q,H,e),(F,NewTop)), NewStack=[NewTop|Stack], write(Q-H-e-F-NewTop),tab(2),write(stack-NewStack),nl, check_word(F,T,NewStack). % t((f,b,a),(f,e)). % pop check_word(Q,[H|T],[Top|Rest]):- t((Q,H,Top),(F,e)), write(Q-H-Top-F-e),tab(2),write(stack-Rest),nl, check_word(F,T,Rest). % Check if a word is accepted (yes/no). start:- write('PDA accepting a^nbw | |bw| = n'),nl, write('Input your word: '),read(W), start(S),check_word(S,W,[]).