| Ling484 Prolog Examples |
A. C. Brett acbrett@uvic.ca
Department of Linguistics
University of Victoria
Clearihue C139
|
Last updated: 3 January 2005
Automata.
Automata are abstract machines that are normally conceived of
a idealised, but much simplified computers that are devised to
perform particular varieties of problem-solving procedures.
The procedures performed by the automata illustrated here are
employed to determine whether or not given strings of words
constitute sentences.
Two varieties of automata are demonstrated in the examples
identified below.
The first of these is the Finite-State Automaton, which
is the simplest of the automata, and the second is the
Push-Down Automaton, which differs from the
Finite-State machine only in that it is equipped with a memory
device that functions as a push-down store or stack.
The Finite-State Automaton itself has no memory.
These two varieties of machine have been adapted to produce the
Recursive Transition Network and Shift/Reduce Automata
illustrated by the examples cited below.
The automata illustrated here are important because they are
equivalent to two of the grammars in the Chomsky Hierarchy.
The Finite-State Automata are equivalent to the Type 3 (finite
or regular) grammars.
In fact, the Type 3 or regular grammars are identified as "finite
grammars" because of this equivalence.
The equivalence of a Finite-State Automaton to a finite grammar
means that, given a finite grammar G, a Finite-State Automaton can
be devised that recognises just the sentences generated by G.
Push-Down Automata are equivalent to context-free grammars,
meaning that, given a context-free grammar G, a Push-Down
Automaton can be devised that recognises just the sentences
generated by G.
The Recursive Transition Network and Shift/Reduce Automata are
equivalent to Push-Down Automata in that they accept the same languages.
The operations of these machines are demonstrated by the Prolog
predicates in the following examples:
-
Finite-State Automaton.
This example consists of Prolog predicates that cause the
Listener to function as a Finite-State Automaton which operates
as an acceptor of the sentences generated by a finite grammar.
-
Finite-State Recogniser.
This example illustrates the operations of a Finite-State Automaton
that has been adapted to produce output showing the reduction
of the strings it accepts.
-
Finite-State Parser.
The Prolog predicates comprising this example emulate a Finite-State
Automaton adapted to yield phrase markers for the strings it accepts.
-
Push-Down Automaton.
This program consists of predicates that cause the Prolog interpreter
to emulate the operations of a Push-Down Automaton as it accepts the
sentences generated by a Chomsky Normal Form context-free grammar.
-
Push-Down Automata:
Rewriting Rules as Transitions.
This program demonstrates a Push-Down Automaton that has been
adapted to accept the rewriting rules of a Chomsky Normal Form
context-free grammar as specifying the transitions it must
execute in order to accept sentences generated by the grammar.
-
Push-Down Automata:
Displaying Transitions.
The program illustrated here comprises a modification of the
previous example to display the transitions the Push-Down
Automaton executes as it accepts an input string.
-
Push-Down Automata:
Configurations of the Machine.
This program demonstrates the operations of a Push-Down Automaton
that has been adapted to display output consisting of the sequence
of its configurations, together with the contents of its input tape,
during the course of its accepting an input string.
-
Push-Down Automata:
Embedded Clause Processing.
This program demonstrates the operation of a Push-Down Automaton
as it accepts sentences with embedded constituents.
The demonstration sentences included with the program include
Japanese and English sentences adapted from examples cited by
Kuno (1973)
to illustrate the left-branching structure of Japanese sentences,
in contrast to the predominantly right-branching structure
of English sentences.
Yngve (1960)
is generally cited as the first to demonstate the application
of a machine analogous to a push-down automaton in a model
of the processing of left- and right-branching sentences.
He was working with the sentence production process and
concluded that right-branching sentences require less memory
resource to produce than do left-branching sentences.
-
Recursive Transition Network.
This example consists of predicates that cause the Prolog interpreter
to emulate the working of a Recursive Transition Network (RTN)
Acceptor.
Such systems are also called Transition Network Grammars (TNGs).
The RTN, or TNG, developed out of the concept of the transition
network of a finite-state automaton, but is equivalent to a push-down
automaton because the arcs comprising the network of an RTN
represent transcriptions of the rules of a context-free grammar
(Woods (1970)).
Sentences generated by the grammar are accepted by the RTN by
traversing the network comprised of these arcs.
RTNs form the basis of Augmented Transitions Networks (ATNs),
which are now largely of historical interest, both computationally
but also in terms of their application as psychological models of
language processing.
See, for example,
Fodor and Frazier (1980),
Wanner (1980), and
Wanner and Maratsos (1978).
-
Single-State Shift/Reduce Automaton.
The purpose of this example is to introduce the shift and reduce
operations that form the basis of the more elaborate machine
demonstrated in the following example.