Erasing automata recognize more than context-free languages
František Mráz, Martin Plátek · Czech digital mathematics library · 1995
An erasing automaton is a linear bounded Turing machine which can rewrite any symbol on its tape only to a special symbol (Q).In [1] was formulated a hypothesis that erasing automata cannot recognize all context-free languages (CFL).We show here that the opposite is true.We consider erasing automaton (E-automaton) as a special type of list automaton studied in [10].