Affiliations: Dipartimento di Informatica, Università degli Studi di Milano, Italy. [email protected]
Correspondence:
[*]
Address for correspondence: Dip. di Informatica, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. Partially supported by MIUR under the project PRIN “Automi e Linguaggi Formali: Aspetti Matematici e Applicativi”, code H41J12000190001.
Abstract: Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. When d ≥ 2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.
