Charles Explorer logo
🇬🇧

Δ-Clearing Restarting Automata and CFL

Publication at Faculty of Mathematics and Physics |
2011

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.