Absolutely parallel grammars and two-way finite-state transducers

摘要

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.