A Cycling Cancellation-Automaton for Sentence Well-Formedness

This paper attempts to specify what is the simplest device sufficient to recognize sentence structure, i.

Abstract

This paper attempts to specify what is the simplest device sufficient to recognize sentence structure, i. e. to state for arbitrary sequences of words whether they are well-formed sentences of a natural language. If each word in the sentence is represented by its explicit string-analysis relations, then the sufficient device is one which scans this string-representation of the sentence, cancels every sequence which consists of a symbol followed by its inverse, and repeats the scanning until no more cancellations occur. The device thus requires a memory only one symbol long. In addition, it must retain the uncancelled residue of the sentence after each scan, in order to cycle through it on the next scan; and storage is also needed for the various string-representations which a given sentence can have.