% file:    pdasim.pro
% author:  Robert Keller
% purpose: Prolog program simulating a non-deterministic pushdown automaton.
%          Non-determinism is achieved through back-tracking built into Prolog.
%
% how to:  Run with SWI-prolog on turing, type
%
%          pl -f pdasim.pro
%          test.  
%
%          (including the period)

% These define the initial state and stack symbols for this pda.

initialStateSymbol(initial_state).
initialStackSymbol(s).

% PDA rules are of the form:
%
% rule(Control_State, Stack_Top, Input, New_Control_State, Stack_Push)
%
% A rule that uses no input is shown by giving '' as input 
% (two successive singe quotes with no intervening blank).

% Rules for a PDA accepting: {x in {a, b}* | x not of the form yy}

% Non-deterministically choose to check for odd-length or even-length
% string

rule(initial_state, s, '', check_odd, [s]).
rule(initial_state, s, '', initial_push, [s]).

% All odd-length strings will be accepted.

rule(check_odd, s, a, check_odd2, [s]).
rule(check_odd, s, b, check_odd2, [s]).

rule(check_odd2, s, a, check_odd, [s]).
rule(check_odd2, s, b, check_odd, [s]).

rule(check_odd2, s, '', accept_odd, []).

% Even-length strings are accepted if they have the form
%
% u a v w b x  or  u b v w a x, where 
%
%     |u| = |v| and |w| = |x|. 
%
% The rationale for this was discussed in class.

% initial pushing
% Pushes a marker x for each input symbol read.
% Note that the stack top is on the left.

rule(initial_push, s, a, initial_push, [x, s]).
rule(initial_push, s, b, initial_push, [x, s]).

rule(initial_push, x, a, initial_push, [x, x]).
rule(initial_push, x, b, initial_push, [x, x]).

rule(initial_push, s, a, pop1_remembering_a, [s]).
rule(initial_push, s, b, pop1_remembering_b, [s]).


% At some point, decide to remember the input character,
% without further pushing,
% then start popping the markers, one for each input symbol.

rule(initial_push, s, a, pop1_remembering_a, [s]).
rule(initial_push, s, b, pop1_remembering_b, [s]).

rule(initial_push, x, a, pop1_remembering_a, [x]).
rule(initial_push, x, b, pop1_remembering_b, [x]).


% first popping phase
% Pop symbols, one per input character, until the initial stack
% symbol is encountered, indicating the stack is "virtually empty".

rule(pop1_remembering_a, x, a, pop1_remembering_a, []).
rule(pop1_remembering_a, x, b, pop1_remembering_a, []).

rule(pop1_remembering_b, x, a, pop1_remembering_b, []).
rule(pop1_remembering_b, x, b, pop1_remembering_b, []).


% turn
% The stack is virtually empty, so start the second pushing
% phase, still remembering the original character remembered.

rule(pop1_remembering_a, s, '', push2_remembering_a, [s]).
rule(pop1_remembering_b, s, '', push2_remembering_b, [s]).


% second pushing phase
% Push a marker for each symbol read, until the PDA thinks
% it is time to compare to the original symbol remembered.

rule(push2_remembering_a, s, a, push2_remembering_a, [x, s]).
rule(push2_remembering_a, s, b, push2_remembering_a, [x, s]).

rule(push2_remembering_a, x, a, push2_remembering_a, [x, x]).
rule(push2_remembering_a, x, b, push2_remembering_a, [x, x]).

rule(push2_remembering_b, s, a, push2_remembering_b, [x, s]).
rule(push2_remembering_b, s, b, push2_remembering_b, [x, s]).

rule(push2_remembering_b, x, a, push2_remembering_b, [x, x]).
rule(push2_remembering_b, x, b, push2_remembering_b, [x, x]).


% comparing
% Compare the input symbol to the remembered symbol.
% If they are different, enter the final popping phase.
% Otherwise, there is no action, blocking acceptance.

rule(push2_remembering_a, x, b, final_pop, [x]).
rule(push2_remembering_a, s, b, final_pop, [s]).

rule(push2_remembering_b, x, a, final_pop, [x]).
rule(push2_remembering_b, s, a, final_pop, [s]).


% final popping
% Pop the markers off the stack, one per input symbol. If the stack 
% becomes virtually empty when the input is empty, accept.

rule(final_pop, x, a, final_pop, []).
rule(final_pop, x, b, final_pop, []).


% accepting

rule(final_pop, s, '', accept, []).


% Tests, both positive and negative, odd and even.

test(odd1a) :- scan([ 'a' ]).

test(odd1b) :- scan([ 'b' ]).

test(odd3a) :- scan([ 'a', 'b', 'a' ]).

test(odd3b) :- scan([ 'b', 'b', 'b' ]).

test(odd5a) :- scan([ 'a', 'b', 'a', 'b', 'a' ]).

test(odd5b) :- scan([ 'b', 'b', 'b', 'a', 'a' ]).

test(pos2a) :- scan([ 'a', 'b']).

test(pos2b) :- scan([ 'b', 'a']).

test(neg2a) :- \+scan([ 'a', 'a']).

test(neg2b) :- \+scan([ 'b', 'b']).

test(pos4a) :- scan([ 'a', 'b', 'a', 'a']).

test(neg4a) :- \+scan([ 'a', 'b', 'a', 'b']).

test(pos4b) :- scan([ 'b', 'a', 'a', 'a']).

test(pos4c) :- scan([ 'a', 'a', 'a', 'b']).

test(pos4d) :- scan([ 'a', 'a', 'b', 'a']).

test(pos6) :- scan([ 'a', 'b', 'a', 'a', 'a', 'a']).

test(neg6):- \+scan([ 'a', 'a', 'a', 'a', 'a', 'a']).

test(pos8a) :- scan([ 'a', 'a', 'a', 'b', 'a', 'a', 'a', 'a']).

test(neg8a) :- \+scan([ 'a', 'a', 'a', 'b', 'a', 'a', 'a', 'b']).

test(pos8b) :- scan([ 'a', 'a', 'b', 'a', 'a', 'a', 'a', 'a']).

test(neg8b) :- \+scan([ 'a', 'a', 'b', 'a', 'a', 'a', 'b', 'a']).

test(pos8c) :- scan([ 'b', 'a', 'a', 'a', 'a', 'a', 'a', 'a']).

test(neg8c) :- \+scan([ 'b', 'a', 'a', 'a', 'b', 'a', 'a', 'a']).

% Overall test suite

test :- test(_), fail.
test.


% The rest is the machinery for the PDA implementation.
% It is not specific to a particular language.

% A totally artificial limit to prevent left recursion!
% This needs to be made big enough for the occasion.

leftRecursionLimit(40).


% How we want the empty string (epsilon) to show up, 
% since just whitespace may look weird.

emptyString(' <epsilon> ').


% Scan the input and show the results, success or failure

scan(Input) :-
    nl, nl,
    write('Trying:'), showString(Input), nl, nl,
    (scan(Input, Trace)
       -> (showTrace(Trace), write('Success with:'), showString(Input), nl)
       ;  (write(failed), nl)).
    


% Start things off with the start symbol as the top-of-stack symbol

scan(Input, Trace) :- 
    initialStateSymbol(Q),
    initialStackSymbol(S),
    leftRecursionLimit(Limit),

    scan(conf(Input, Q, [S]), Limit, Trace).


% Failure: limit exceeded

scan(_, Limit, _) :- Limit =< 0, fail.


% The three alternative clauses do most of the work.  Either
%     The stack and input are both empty (success),
%     The top of stack letter matches the input (recurse).
%     The top of the stack is the LHS of a rule (recurse).
%     Or none of the above (failure).

% Stack is empty and so is input.

scan(conf([], State, []), _Limit, [[conf([], State, []), empty_stack]]).


% Apply the transition rule using input.

scan(conf(Input, State, Stack), Limit, [[conf(Input, State, Stack), rule(State, StackTop, Letter, NewState, StackPush)] | Trace]) :-
    Limit > 0,

    Input = [Letter | RestInput],
    Stack = [StackTop | RestStack],
    rule(State, StackTop, Letter, NewState, StackPush),

    append(StackPush, RestStack, NewStack),
    Limit1 is Limit - 1,

    scan(conf(RestInput, NewState, NewStack), Limit1, Trace).


% Apply the transition rule without using input.

scan(conf(Input, State, Stack), Limit, [[conf(Input, State, Stack), rule(State, StackTop, '', NewState, StackPush)] | Trace]) :-
    Limit > 0,

    Stack = [StackTop | RestStack],
    rule(State, StackTop, '', NewState, StackPush),

    append(StackPush, RestStack, NewStack),
    Limit1 is Limit - 1,

    scan(conf(Input, NewState, NewStack), Limit1, Trace).


% The 'show' routines are for pretty formatting only.

showTrace([]).

showTrace([Conf | L]) :-
    showConf(Conf),
    nl,
    showTrace(L).


showConf([conf(Input, State, Stack), Rule]) :-
    !,
    write('input: '), showString(Input), nl,
    write('state:  '), write(State), nl,
    write('stack: '), showString(Stack), nl,
    nl,
    write('rule:   '), showRule(Rule), nl.


% Show list of symbols as a string

showString([]) :-
    !,
    emptyString(S),
    write(S).

showString(L) :-
    showString1(L).


% Show string that is not initially empty

showString1([]).

showString1([A | More]) :-
    write(' '), write(A), 
    showString1(More).


showRule(empty_stack) :-
    write('empty stack').

showRule(rule(StackTop, State, Letter, NewState, StackPush)) :-
    write(StackTop), write(', '), write(State), write(', '), write(Letter), 
    write(' -> '), write(NewState), write(', '), showString(StackPush).


/* Test runs

| ?- test.


Trying: a

input:  a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> check_odd,  s

input:  a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  <epsilon> 
state:  check_odd2
stack:  s

rule:   check_odd2, s,  -> accept_odd,  <epsilon> 

input:  <epsilon> 
state:  accept_odd
stack:  <epsilon> 

rule:   empty stack

Success with: a


Trying: b

input:  b
state:  initial_state
stack:  s

rule:   initial_state, s,  -> check_odd,  s

input:  b
state:  check_odd
stack:  s

rule:   check_odd, s, b -> check_odd2,  s

input:  <epsilon> 
state:  check_odd2
stack:  s

rule:   check_odd2, s,  -> accept_odd,  <epsilon> 

input:  <epsilon> 
state:  accept_odd
stack:  <epsilon> 

rule:   empty stack

Success with: b


Trying: a b a

input:  a b a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> check_odd,  s

input:  a b a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  b a
state:  check_odd2
stack:  s

rule:   check_odd2, s, b -> check_odd,  s

input:  a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  <epsilon> 
state:  check_odd2
stack:  s

rule:   check_odd2, s,  -> accept_odd,  <epsilon> 

input:  <epsilon> 
state:  accept_odd
stack:  <epsilon> 

rule:   empty stack

Success with: a b a


Trying: b b b

input:  b b b
state:  initial_state
stack:  s

rule:   initial_state, s,  -> check_odd,  s

input:  b b b
state:  check_odd
stack:  s

rule:   check_odd, s, b -> check_odd2,  s

input:  b b
state:  check_odd2
stack:  s

rule:   check_odd2, s, b -> check_odd,  s

input:  b
state:  check_odd
stack:  s

rule:   check_odd, s, b -> check_odd2,  s

input:  <epsilon> 
state:  check_odd2
stack:  s

rule:   check_odd2, s,  -> accept_odd,  <epsilon> 

input:  <epsilon> 
state:  accept_odd
stack:  <epsilon> 

rule:   empty stack

Success with: b b b


Trying: a b a b a

input:  a b a b a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> check_odd,  s

input:  a b a b a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  b a b a
state:  check_odd2
stack:  s

rule:   check_odd2, s, b -> check_odd,  s

input:  a b a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  b a
state:  check_odd2
stack:  s

rule:   check_odd2, s, b -> check_odd,  s

input:  a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  <epsilon> 
state:  check_odd2
stack:  s

rule:   check_odd2, s,  -> accept_odd,  <epsilon> 

input:  <epsilon> 
state:  accept_odd
stack:  <epsilon> 

rule:   empty stack

Success with: a b a b a


Trying: b b b a a

input:  b b b a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> check_odd,  s

input:  b b b a a
state:  check_odd
stack:  s

rule:   check_odd, s, b -> check_odd2,  s

input:  b b a a
state:  check_odd2
stack:  s

rule:   check_odd2, s, b -> check_odd,  s

input:  b a a
state:  check_odd
stack:  s

rule:   check_odd, s, b -> check_odd2,  s

input:  a a
state:  check_odd2
stack:  s

rule:   check_odd2, s, a -> check_odd,  s

input:  a
state:  check_odd
stack:  s

rule:   check_odd, s, a -> check_odd2,  s

input:  <epsilon> 
state:  check_odd2
stack:  s

rule:   check_odd2, s,  -> accept_odd,  <epsilon> 

input:  <epsilon> 
state:  accept_odd
stack:  <epsilon> 

rule:   empty stack

Success with: b b b a a


Trying: a b

input:  a b
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a b
state:  initial_push
stack:  s

rule:   initial_push, s, a -> pop1_remembering_a,  s

input:  b
state:  pop1_remembering_a
stack:  s

rule:   pop1_remembering_a, s,  -> push2_remembering_a,  s

input:  b
state:  push2_remembering_a
stack:  s

rule:   push2_remembering_a, s, b -> final_pop,  s

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a b


Trying: b a

input:  b a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  b a
state:  initial_push
stack:  s

rule:   initial_push, s, b -> pop1_remembering_b,  s

input:  a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> final_pop,  s

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: b a


Trying: a a

failed


Trying: b b

failed


Trying: a b a a

input:  a b a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a b a a
state:  initial_push
stack:  s

rule:   initial_push, s, a -> initial_push,  x s

input:  b a a
state:  initial_push
stack:  x s

rule:   initial_push, x, b -> pop1_remembering_b,  x

input:  a a
state:  pop1_remembering_b
stack:  x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> final_pop,  s

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a b a a


Trying: a b a b

failed


Trying: b a a a

input:  b a a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  b a a a
state:  initial_push
stack:  s

rule:   initial_push, s, b -> pop1_remembering_b,  s

input:  a a a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a a a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> push2_remembering_b,  x s

input:  a a
state:  push2_remembering_b
stack:  x s

rule:   push2_remembering_b, x, a -> final_pop,  x

input:  a
state:  final_pop
stack:  x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: b a a a


Trying: a a a b

input:  a a a b
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a a a b
state:  initial_push
stack:  s

rule:   initial_push, s, a -> initial_push,  x s

input:  a a b
state:  initial_push
stack:  x s

rule:   initial_push, x, a -> pop1_remembering_a,  x

input:  a b
state:  pop1_remembering_a
stack:  x s

rule:   pop1_remembering_a, x, a -> pop1_remembering_a,  <epsilon> 

input:  b
state:  pop1_remembering_a
stack:  s

rule:   pop1_remembering_a, s,  -> push2_remembering_a,  s

input:  b
state:  push2_remembering_a
stack:  s

rule:   push2_remembering_a, s, b -> final_pop,  s

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a a a b


Trying: a a b a

input:  a a b a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a a b a
state:  initial_push
stack:  s

rule:   initial_push, s, a -> pop1_remembering_a,  s

input:  a b a
state:  pop1_remembering_a
stack:  s

rule:   pop1_remembering_a, s,  -> push2_remembering_a,  s

input:  a b a
state:  push2_remembering_a
stack:  s

rule:   push2_remembering_a, s, a -> push2_remembering_a,  x s

input:  b a
state:  push2_remembering_a
stack:  x s

rule:   push2_remembering_a, x, b -> final_pop,  x

input:  a
state:  final_pop
stack:  x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a a b a


Trying: a b a a a a

input:  a b a a a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a b a a a a
state:  initial_push
stack:  s

rule:   initial_push, s, a -> initial_push,  x s

input:  b a a a a
state:  initial_push
stack:  x s

rule:   initial_push, x, b -> pop1_remembering_b,  x

input:  a a a a
state:  pop1_remembering_b
stack:  x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a a a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a a a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> push2_remembering_b,  x s

input:  a a
state:  push2_remembering_b
stack:  x s

rule:   push2_remembering_b, x, a -> final_pop,  x

input:  a
state:  final_pop
stack:  x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a b a a a a


Trying: a a a a a a

failed


Trying: a a a b a a a a

input:  a a a b a a a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a a a b a a a a
state:  initial_push
stack:  s

rule:   initial_push, s, a -> initial_push,  x s

input:  a a b a a a a
state:  initial_push
stack:  x s

rule:   initial_push, x, a -> initial_push,  x x

input:  a b a a a a
state:  initial_push
stack:  x x s

rule:   initial_push, x, a -> initial_push,  x x

input:  b a a a a
state:  initial_push
stack:  x x x s

rule:   initial_push, x, b -> pop1_remembering_b,  x

input:  a a a a
state:  pop1_remembering_b
stack:  x x x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a a a
state:  pop1_remembering_b
stack:  x x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a a
state:  pop1_remembering_b
stack:  x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> final_pop,  s

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a a a b a a a a


Trying: a a a b a a a b

failed


Trying: a a b a a a a a

input:  a a b a a a a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  a a b a a a a a
state:  initial_push
stack:  s

rule:   initial_push, s, a -> initial_push,  x s

input:  a b a a a a a
state:  initial_push
stack:  x s

rule:   initial_push, x, a -> initial_push,  x x

input:  b a a a a a
state:  initial_push
stack:  x x s

rule:   initial_push, x, b -> pop1_remembering_b,  x

input:  a a a a a
state:  pop1_remembering_b
stack:  x x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a a a a
state:  pop1_remembering_b
stack:  x s

rule:   pop1_remembering_b, x, a -> pop1_remembering_b,  <epsilon> 

input:  a a a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a a a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> push2_remembering_b,  x s

input:  a a
state:  push2_remembering_b
stack:  x s

rule:   push2_remembering_b, x, a -> final_pop,  x

input:  a
state:  final_pop
stack:  x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: a a b a a a a a


Trying: a a b a a a b a

failed


Trying: b a a a a a a a

input:  b a a a a a a a
state:  initial_state
stack:  s

rule:   initial_state, s,  -> initial_push,  s

input:  b a a a a a a a
state:  initial_push
stack:  s

rule:   initial_push, s, b -> pop1_remembering_b,  s

input:  a a a a a a a
state:  pop1_remembering_b
stack:  s

rule:   pop1_remembering_b, s,  -> push2_remembering_b,  s

input:  a a a a a a a
state:  push2_remembering_b
stack:  s

rule:   push2_remembering_b, s, a -> push2_remembering_b,  x s

input:  a a a a a a
state:  push2_remembering_b
stack:  x s

rule:   push2_remembering_b, x, a -> push2_remembering_b,  x x

input:  a a a a a
state:  push2_remembering_b
stack:  x x s

rule:   push2_remembering_b, x, a -> push2_remembering_b,  x x

input:  a a a a
state:  push2_remembering_b
stack:  x x x s

rule:   push2_remembering_b, x, a -> final_pop,  x

input:  a a a
state:  final_pop
stack:  x x x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  a a
state:  final_pop
stack:  x x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  a
state:  final_pop
stack:  x s

rule:   final_pop, x, a -> final_pop,  <epsilon> 

input:  <epsilon> 
state:  final_pop
stack:  s

rule:   final_pop, s,  -> accept,  <epsilon> 

input:  <epsilon> 
state:  accept
stack:  <epsilon> 

rule:   empty stack

Success with: b a a a a a a a


Trying: b a a a b a a a

failed

yes
*/