Absolutely parallel grammars are defined, and it is shown that the family of languages generated is equal to the family of languages generated by two-way deterministic finite-state transducers (abbreviated 2ft). Furthermore it is shown that this family forms a full AFL closed under substitution. It is shown that the family of languages generated by two-way nondeterministic finite-state transducers is equal to the family of checking automata languages and that it properly contains the family of languages generated by 2ft.
INTRODU CT1ON
Recently there has been an extensive investigation of different types of contextsensitive grammars with the context scattered through the whole word. (See [10], [13], etc.) This paper defines a new class of grammars, called absolutely parallel grammars, belonging to this category. A particular feature of this grammar making it worthwhile is that it describes in simple terms all languages generated by two-way finite-state transducers, which in turn play an important role in the general understanding to two-way deterministic machines [1].
The paper is divided into five sections. In the first two sections, we present definitions of two-way deterministic finite-state transducers and absolutely parallel grammars. In addition, these sections contain some technical lemmas. The equality of the two corresponding families of languages is established in the third section.
In the fourth section, the family of absolutely parallel languages is shown to be a full AFL [4]. * This paper is derived in part from a dissertation [14] submitted in partial fulfillment of the requirements for the Ph.D. degree in mathematics at Case Western Reserve University.