Completion Grammars and Completion Automata Revisited

An extension of completion grammars is being introduced such that the model now deals with prefix, infix, postfix and post-infix word order patterns. It is shown that this extension does not affect the weak generative capacity of the system, which was known to be of type 2.

Also the existing notion of a completion automaton is reworked, mainly to have the distinction in word order be reflected by the operations of the automaton rather than by the transition functions of the underlying finite state machine.

In some recent publications (e.g. Steels (1975), Steels and Vermeir (1976), Steels (1976a&b» we have been dealing with a linguistic model known as compZetion grammars. These grammars were designed to cope with a functional viewpoint on language, this means they deal with case structures for language,expressions, instead of phrase structures as do the well-known Chomsky-type grammars.

The model of completion grammars was developed in a context of research on language processing and automatic translation. In particular it reflects the current tendency to build semantics directed systems, rather than syntax directed ones. (See for a more detailed discussion on the distinction between the two Wilks (1975) and Winograd (1973). For the use of completion grammars in the design of semantics directed systems, we refer to Steels (1975;1976a&b).

What will concern us in this paper is an extension of the model, and a study of the formal properties of these extended systems. Also we will introduce a new class of automata. The paper is organized as follows. First we extend the notion of a completion grammar, we give some intuitive explanations for the extension (1.1.), specify the basic definitions (1.2.) and study its weak generative capacity (1.3.). A second section deals with the automata. Again we start with intuitive explanations (2.1.), give the basic definitions and various examples (2.2.) and finally prove the relation between the grammars and the automata (2.3.).