% Example of converting a 2-state PDA to a 1-state pda.
% Robert Keller

% In both cases, PDA rules are of the form:
%
% rule(Control_State, Stack_Top, Input, New_Control_State, Stack_Push)
%
% as used for my Prolog-based simulator.

% Rules for a PDA accepting: {xx^R | x in {a, b}+ }  |  % Rules for a PDA accepting: {xx^R | x in {a, b}+ }
% by empty stack                                     |  % by empty stack using only one control state u.
                                                     |  
% Define the initial state and stack symbols:        |  % Define the initial state and stack symbols:
                                                     |  
initialStateSymbol(q0).                              |  initialStateSymbol(u).
initialStackSymbol(s).                               |  initialStackSymbol(x).
                                                     |  
                                                     |  % Initial epsilon rules to initialize stack:
                                                     |  
                                                     |  rule(u, x, [], u, [[q0, s, q0]]).
                                                     |  rule(u, x, [], u, [[q0, s, q1]]).
                                                     |  
                                                     |  
rule(q0, s, a,  q0, [a, s]).                         |  rule(u, [q0, s, q0], a, u, [[q0, a, q0], [q0, s, q0]]).
                                                     |  rule(u, [q0, s, q1], a, u, [[q0, a, q0], [q0, s, q1]]).
                                                     |  rule(u, [q0, s, q0], a, u, [[q0, a, q1], [q1, s, q0]]).
                                                     |  rule(u, [q0, s, q1], a, u, [[q0, a, q1], [q1, s, q1]]).
                                                     |  
rule(q0, s, b,  q0, [b, s]).                         |  rule(u, [q0, s, q0], b, u, [[q0, b, q0], [q0, s, q0]]).
                                                     |  rule(u, [q0, s, q1], b, u, [[q0, b, q0], [q0, s, q1]]).
                                                     |  rule(u, [q0, s, q0], b, u, [[q0, b, q1], [q1, s, q0]]).
                                                     |  rule(u, [q0, s, q1], b, u, [[q0, b, q1], [q1, s, q1]]).
                                                     |  
rule(q0, a, a,  q0, [a, a]).                         |  rule(u, [q0, a, q0], a, u, [[q0, a, q0], [q0, a, q0]]).
                                                     |  rule(u, [q0, a, q1], a, u, [[q0, a, q0], [q0, a, q1]]).
                                                     |  rule(u, [q0, a, q0], a, u, [[q0, a, q1], [q1, a, q0]]).
                                                     |  rule(u, [q0, a, q1], a, u, [[q0, a, q1], [q1, a, q1]]).
                                                     |  
rule(q0, a, b,  q0, [b, a]).                         |  rule(u, [q0, a, q0], b, u, [[q0, b, q0], [q0, a, q0]]).
                                                     |  rule(u, [q0, a, q1], b, u, [[q0, b, q0], [q0, a, q1]]).
                                                     |  rule(u, [q0, a, q0], b, u, [[q0, b, q1], [q1, a, q0]]).
                                                     |  rule(u, [q0, a, q1], b, u, [[q0, b, q1], [q1, a, q1]]).
                                                     |  
rule(q0, b, a,  q0, [a, b]).                         |  rule(u, [q0, b, q0], a, u, [[q0, a, q0], [q0, b, q0]]).
                                                     |  rule(u, [q0, b, q1], a, u, [[q0, a, q0], [q0, b, q1]]).
                                                     |  rule(u, [q0, b, q0], a, u, [[q0, a, q1], [q1, b, q0]]).
                                                     |  rule(u, [q0, b, q1], a, u, [[q0, a, q1], [q1, b, q1]]).
                                                     |  
rule(q0, b, b,  q0, [b, b]).                         |  rule(u, [q0, b, q0], b, u, [[q0, b, q0], [q0, b, q0]]).
                                                     |  rule(u, [q0, b, q1], b, u, [[q0, b, q0], [q0, b, q1]]).
                                                     |  rule(u, [q0, b, q0], b, u, [[q0, b, q1], [q1, b, q0]]).
                                                     |  rule(u, [q0, b, q1], b, u, [[q0, b, q1], [q1, b, q1]]).
                                                     |  
rule(q0, a, [], q1, [a]).                            |  rule(u, [q0, a, q0], [], u, [[q1, a, q0]]).
                                                     |  rule(u, [q0, a, q1], [], u, [[q1, a, q1]]).
                                                     |  
rule(q0, b, [], q1, [b]).                            |  rule(u, [q0, b, q0], [], u, [[q1, b, q0]]).
                                                     |  rule(u, [q0, b, q1], [], u, [[q1, b, q1]]).
                                                     |  
rule(q1, a,  a, q1, []).                             |  rule(u, [q1, a, q1], a, u, []).
                                                     |  
rule(q1, b,  b, q1, []).                             |  rule(u, [q1, b, q1], b, u, []).
                                                     |  
rule(q1, s,  [], q1, []).                            |  rule(u, [q1, s, q1], [], u, []).