FURTHER RESULTS ON RESTARTING AUTOMATA

摘要

Jancar et al (1995) developed the restarting automaton as a formal model for certain syntactical aspects of natural languages. Here it is shown that with respect to its expressive power the use of nonterminal symbols by restarting automata corresponds to the language theoretical operation of intersection with regular languages. Further, we establish another characterization of the class of Church-Rosser languages by showing that it coincides with the class of languages accepted by the det-RRWW-automata, thus extending an earlier result presented at DLT'99. Finally, we show that the Gladkij language L_(G1) is accepted by an RRWW-automaton, which implies that the class GCSL of growing context-sensitive languages is properly contained in the class L(RRWW).