Δ-clearing restarting automata and CFL

Peter Černo and František Mráz

Abstract. ∆-clearing restarting automata represent a new restricted model of restarting automata which, based on a limited context, can either delete a substring of the current content of its tape or replace a substring by a special auxiliary symbol ∆, which cannot be overwritten anymore, but it can be deleted later. The main result of this paper consists in proving that besides their limited operations, ∆-clearing restarting automata recognize all context-free languages.

Comments are closed.