%  Linguistics 484 -- Example: FSA_R PROLOG
%
%  Finite-State Automata (FSA):
%
%  This example consists of Prolog assertions that cause the Listener
%  to emulate the operations of an FSA that has been adapted to
%  produce output showing the reduction of strings of input tokens.
%  For example, if the following query is typed:
%
%      s([dogs, like, them]).
%
%  the following reduction will be displayed:
%
%         [s,dogs,like,them]
%      => [vpp,like,them]
%      => [np,them]
%      => [h]


%s/1          s(L) : L is a list of tokens accepted by the finite-state
%                    automaton.
%

   s(Data_list) :- nl, write('   '),
                   write([s | Data_list]), nl,
                   control(s, Data_list).

%
%control/2    control(S, L) : L is a list of tokens, and S is the
%                            label of the current state of the automaton.
%
%

   control(h, []).

   control(From, [Token | Rest]) :- move(From, Token, To),
                                    write('=> '),
                                    write([To | Rest]), nl,
                                    control(To, Rest).


%
%move/3       move(X, T, Y) : There exists a transition from state X to
%                           state Y, given the token T.
%
%

   move(s,   she,   vps).
   move(s,   he,    vps).
   move(s,   it,    vps).           move(s,   they,  vpp).
   move(s,   dog,   vps).           move(s,   dogs,  vpp).
   move(s,   cat,   vps).           move(s,   cats,  vpp).

   move(vps, likes, np ).           move(vpp, like,  np ).
   move(vps, plays, np ).           move(vpp, play,  np ).

   move(vps, plays, h  ).           move(vpp, play,  h  ).
   move(vps, runs,  h  ).           move(vpp, run,   h  ).

   move(np,  her,   h  ).
   move(np,  him,   h  ).
   move(np,  it,    h  ).           move(np,  them,  h  ).
   move(np,  dog,   h  ).           move(np,  dogs,  h  ).
   move(np,  cat,   h  ).           move(np,  cats,  h  ).