Assignment 6, first problem.

I am using the rule form for my Prolog-based simulator.
The rationale is that discussed in class.

-------------------------------------------------------------------------------
The given PDA:

% Define the initial state and stack symbols for this pda.

initialStateSymbol(a).
initialStackSymbol(s).

% PDA rules are of the form:
%
% rule(Control_State, Stack_Top, Input, New_Control_State, Stack_Push)
%

rule(a, s, [], a, []).
rule(a, s, 0,  a, [0, s]).
rule(a, 0, 0,  a, [0, 0]).
rule(a, 0, 1,  b, []).
rule(b, 0, 1,  b, []).
rule(b, s, [], b, []).

-------------------------------------------------------------------------------
The one-state PDA equivalent the given one.
The rules in the original PDA that gave rise to these rules are
shown as comments % ... .

% Define the initial state and stack symbols for this pda.

initialStateSymbol(u).
initialStackSymbol(x).

% PDA rules are of the form:
%
% rule(Control_State, Stack_Top, Input, New_Control_State, Stack_Push)
%

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

% rule(a, s, [], a, []).

rule(u, [a, s, a], [], u, []).

% rule(a, s, 0,  a, [0, s]).

rule(u, [a, s, a], 0, u, [[a, 0, a], [a, s, a]]).
rule(u, [a, s, b], 0, u, [[a, 0, a], [a, s, b]]).

rule(u, [a, s, a], 0, u, [[a, 0, b], [b, s, a]]).
rule(u, [a, s, b], 0, u, [[a, 0, b], [b, s, b]]).

% rule(a, 0, 0,  a, [0, 0]).

rule(u, [a, 0, a], 0, u, [[a, 0, a], [a, 0, a]]).
rule(u, [a, 0, b], 0, u, [[a, 0, a], [a, 0, b]]).

rule(u, [a, 0, a], 0, u, [[a, 0, b], [b, 0, a]]).
rule(u, [a, 0, b], 0, u, [[a, 0, b], [b, 0, b]]).

% rule(a, 0, 1,  b, []).

rule(u, [a, 0, b], 1, u, []).

% rule(b, 0, 1,  b, u, []).

rule(u, [b, 0, b], 1, u, []).

% rule(b, s, [], b, []).

rule(u, [b, s, b], [], u, []).

-------------------------------------------------------------------------------
Grammar derived from the 1-state PDA:

The start symbol is x.

The terminals are {0, 1}.

The non-terminals are:
        [a, s, a]
        [a, s, b]
        [a, 0, a]
        [a, 0, b]
        [b, 0, a]
        [b, 0, b]
        [b, s, a]
        [b, s, b]
Each line represents a single non-terminal.

From the 1-state pda, the grammar productions are derived below the
corresponding rules:

rule(u, x, [], u, [[a, s, a]]).
        x -> [a, s, a]

rule(u, x, [], u, [[a, s, b]]).
        x -> [a, s, b]

rule(u, [a, s, a], [], u, []).
        [a, s, a] -> []

rule(u, [a, s, a], 0, u, [[a, 0, a], [a, s, a]]).
        [a, s, a] -> 0 [a, 0, a] [a, s, a]

rule(u, [a, s, b], 0, u, [[a, 0, a], [a, s, b]]).
        [a, s, b] -> 0 [a, 0, a] [a, s, b]

rule(u, [a, s, a], 0, u, [[a, 0, b], [b, s, a]]).
        [a, s, a] -> 0 [a, 0, b] [b, s, a]

rule(u, [a, s, b], 0, u, [[a, 0, b], [b, s, b]]).
        [a, s, b] -> 0 [a, 0, b] [b, s, b]

rule(u, [a, 0, a], 0, u, [[a, 0, a], [a, 0, a]]).
        [a, 0, a] -> 0 [a, 0, a] [a, 0, a]

rule(u, [a, 0, b], 0, u, [[a, 0, a], [a, 0, b]]).
        [a, 0, b] -> 0 [a, 0, a] [a, 0, b]

rule(u, [a, 0, a], 0, u, [[a, 0, b], [b, 0, a]]).
        [a, 0, a] -> 0 [a, 0, b] [b, 0, a]

rule(u, [a, 0, b], 0, u, [[a, 0, b], [b, 0, b]]).
        [a, 0, b] -> 0 [a, 0, b] [b, 0, b]

rule(u, [a, 0, b], 1, u, []).
        [a, 0, b] -> 1

rule(u, [b, 0, b], 1, u, []).
        [b, 0, b] -> 1

rule(u, [b, s, b], [], u, []).
        [b, s, b] -> []

An example of a leftmost derivation is:

x -> [a, s, b]                                  using x -> [a, s, b]
  -> 0 [a, 0, b] [b, s, b]                      using [a, s, b] -> 0 [a, 0, b] [b, s, b]
  -> 0 0 [a, 0, b] [b, 0, b][b, s, b]           using [a, 0, b] -> 0 [a, 0, b] [b, 0, b]
  -> 0 0 0 [a, 0, b] [b, 0, b][b, 0, b][b, s, b] using [a, 0, b] -> 0 [a, 0, b] [b, 0, b]
  -> 0 0 0 1 [b, 0, b][b, 0, b][b, s, b]        using [a, 0, b] -> 1
  -> 0 0 0 1 1 [b, 0, b][b, s, b]               using [b, 0, b] -> 1
  -> 0 0 0 1 1 1 [b, s, b]                      using [b, 0, b] -> 1
  -> 0 0 0 1 1 1                                using [b, s, b] -> []