Uniformly erasable AFL

摘要

A full AFL ℒ is uniformly ℱ-erasable if in every AFA defining ℒ (where each automaton signals acceptance by simultaneously entering an accepting state and emptying its storage), the quasi-realtime acceptors also define ℒ. This is equivalent to the property that every set of languages containing {ε} which generates ℒ under full AFL operations also generates ℒ under AFL operations. A full semi-AFL is uniformly ℱ-erasable if it satisfies the same condition with “semi-AFL” in place of “AFL” and with automata signalling acceptance by simply entering an accepting state. A full AFL is uniformly erasable if it is both uniformly ℱ- and uniformly ℒ-erasable.A study is made of the above three concepts of uniform erasability. The family of all context-free languages and several of its subfamilies are shown to be uniformly erasable. The context-free languages being a uniformly erasable full AFL generalizes the well-known result that every context-free language can be recognized by a quasirealtime pushdown acceptor.