%  Linguistics 484 -- Example: PDA_R Prolog
%
%  Push-Down Automata: Rewriting Rules as Transitions.
%
%  The predicates comprising this program cause the Prolog interpreter
%  to emulate the operations of a Push-Down Automaton that accepts the
%  sentences generated by a Chomsky Normal Form context-free grammar.
%
%  In this program, the transitions of the Push-Down Automaton are
%  specified in terms of the rewriting rules of the grammar.  All the
%  rules of a Chomsky Normal Form grammar have either one or the other
%  of the following two forms:
%
%     B --> b, where 'B' is a nonterminal symbol and 'b' is a word; or,
%     B --> C D, where 'B', 'C', and 'D' are nonterminals.
%
%  These rules are included in the program by means of the clauses of
%  rule/2 and rule/3 predicates, with the B --> b rules being specified
%  by clauses of the form
%
%    rule('B', 'b').
%
%  and the B --> C D rules being specified by clauses of the form
%
%    rule('B', 'C', 'D').
%
%  The program then, in effect, "translates" these rules into the
%  transitions that the automaton must execute in order to accept input
%  strings generated by the grammar.  The B --> b rules are translated
%  into initial finite-state transitions of the form
%
%    <'#', '$', 'b', '#', 'B'>
%
%  or into read/push transitions of the form
%
%    <'Zi', 'Qi', 'b', 'Qi', 'B'>
%
%  where '#' represents the empty strore symbol, '$' is the label
%  of the starting state of the machine, 'Zi' is the topmost symbol
%  of the machine in the state 'Qi'.
%
%  The B --> C D rules are translated into lambda/pop transitions
%  of the form
%
%    <'C', 'D', '\', 'Zj', 'B'>
%
%  where '\' stands for the null string, usually denoted by the
%  Greek letter lambda, and 'Zj' is the topmost symbol in the store
%  with the machine in the state labelled 'B'.


%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/3.
%     Thus, an input string is presented for processing by typing a query
%     such as the following:
%
%          s([some, dogs, like, the cat]).
%
%     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/3 goal.  The
%     push-down store, represented by the first argument of control/3,
%     contains only the empty store symbol '#'.
%
      s(Tape) :- control(['#'], '$', Tape).


%control/3    control(Stack, State, Tape) : 
%
%        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.

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

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

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

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

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


%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).