%  Linguistics 484 -- Example: PDA_D Prolog
%
%  Push-Down Automata: Displaying Transitions.
%
%  The predicates comprising this program cause the Prolog interpreter
%  to emulate the operations of a Push-Down Automaton that has been
%  adapted to display the transitions it executes to accept an input
%  string.  Hence, typing the following query:
%
%     s([some, dogs, like, the, cat]).
%
%  causes the following output to be displayed:
%
%     [#,$,some] --> [#,det]
%     [#,det,dogs] --> [det,n]
%     [det,n,\] --> [#,np]
%     [#,np,like] --> [np,v]
%     [np,v,the] --> [v,det]
%     [v,det,cat] --> [det,n]
%     [det,n,\] --> [v,np]
%     [v,np,\] --> [np,vp]
%     [np,vp,\] --> [#,s]
%
%  which represents the transitions in their "rewriting rule"
%  format.  In each of these rule-like lines, the list to the left
%  of the '-->' symbols consists of the symbol at the top of the
%  push-down store, followed by the label of the current state of
%  the machine.  The third entry in the left-hand side list consists
%  of either an input symbol, that is, the word read during a
%  read/push transition, or the symbol '\' which here stands for
%  lambda, the null string, for a null/pop transition.  The right-
%  hand side of the '-->' is a list, the first entry of which is the
%  symbol at the top of the store in the new state, the label for
%  which appear as the second entry of the list.
%
%  The predicates of this program, in effect, translate the rewrting
%  rules of a Chomsky Normal Form context-free grammar into the
%  transitions it must execute in order to accept an input string.
%  The program therefore displays the transitions that result from
%  this "translation" process.


%s/1          s(Tape) : The list of data tokens, Tape, comprises a
%                       sentence if it is accepted by a PDA the control
%                   unit of which is emulated by the predicate control/4.
%
%     Processing of the input string in the list Tape is begun with the
%     machine in its initial state, labelled with the symbol '$', which
%     is specified as the second argument of the control/4 goal.  The
%     push-down store, represented by the first argument of control/4,
%     contains only the empty store symbol '#'.
%
      s(Tape) :- control(['#'], '$', Tape, Moves),
                 nl, list_moves(Moves).


%control/4    control(Stack, State, Tape, Moves) : 
%
%        State is the label of the current state of the automaton,
%        and in this state, Tape is a list of the as yet unread
%        data tokens (words). Stack is a list of the symbols
%        currently in the push-down store.  Moves is a list
%        consisting of the sequence of transitions executed by
%        the machine to accept the string stored in Tape.

%  Empty store condition.
      control(['#'], State, [], []).

%  Final state condition.
      control(Stack, s, [], []).

%  Initial Finite-State Transition:  A --> a (Eg., Det --> some)
      control(['#'], '$', [Token | Tape],
                 [['#', '$', Token], ['#', Next] | Moves]) :-
              rule(Next, Token),
              control(['#'], Next, Tape, Moves).

%  Lambda/Pop Transition:  A --> B C (Eg., S --> NP VP)
      control([Top, Under | Stack], State, Tape,
                 [[Top, State, '\\'], [Under, Next] | Moves]) :-
              rule(Next, Top, State),
              control([Under | Stack], Next, Tape, Moves).

%  Read/Push Transition:  A --> a (Eg., V --> like)
      control([Top | Stack], State, [Token | Tape],
                 [[Top, State, Token], [State, Next] | Moves]) :-
              rule(Next, Token),
              control([State, Top | Stack], Next, Tape, Moves).


%list_moves/1
%
%  Display the sequence of transitions.

   list_moves([]).

   list_moves([From, To | Moves]) :-
             write(From),  write(' --> '), write(To), nl,
             list_moves(Moves).


%rule/2
%
%       rule(Qj, Ti) : Qj is the label of the state to which the PDA moves
%                     in a Read/Push Transition, during which the data
%                    symbol Ti is read, corresponding to the rewriting
%                    rules of the form:   Qj --> Ti .  Such rules are,
%                    in effect, translated into transitions of the form:
%                    <Zi, Qi, Ti, Qi, Qj> .  These rules can also be
%                    translated into Initial Finite-State Transitions of
%                    the form:  <#, $, Ti, #, Qj> , where '$' labels the
%                    initial state of the machine and '#' is the empty
%                    store symbol.

      rule(a,   nice).
      rule(det, the).          rule(det, some).

      rule(n,   dog).          rule(n,   dogs).
      rule(n,   cat).          rule(n,   cats).

      rule(v,   like).         rule(v,   likes).
      rule(v,   chase).        rule(v,   chases).


%rule/3
%
%       rule(Qj, Zi, Qi) : Qj is the label of the state to which the PDA
%                        moves from the state labelled Qi in a Lambda/Pop
%                       Transition, during which the symbol Zi is popped
%                       from its stack, corresponding to the rewriting
%                       rules of the form:    Qj --> Zi Qi .  Such rules
%                       are translated into transitions of the form:
%                       <Zi, Qi, \, Zj, Qj> , where '\' stands for the
%                       null string, usually denoted by lambda.

      rule(np, det,  n).      rule(np,   a,  n).

      rule(vp,   v, np).

      rule(s,   np, vp).