Checking automata and one-way stack languages

摘要

A checking automaton is equivalent to a one-way nonerasing stack automaton which, one it enters its stack, never again writes on its stack. The checking automaton languages (cal) form a full AFL closed under substitution. If L⊆a* is an infinite cal, then L contains an infinite regular set. Consequently, there are one-way non-erasing stack languages (such as {an2|n≥1}) which are not cal.Let ℒ be the family of one-way stack languages and let ℒ be a subAFL of ℒ. ℒ is closed under substitution into ℒ1 if and only if ℒ1 is contained in the family of context-free languages. ℒ is closed under substitution by ℒ1 if and only if ℒ1 is a family of cal. Hence, the one-way stack languages are not closed under substitution. The one-way nested stack languages properly include the stack languages.The family of quasi-real-time one-way stack languages is not closed under substitution by cal. Thus the quasi-real-time one-way stack languages are not a full AFL but are a proper subAFL of the one-way stack languages.Let ℒN be the family of one-way nonerasing stack languages, and let ℒ1 be a subAFL. Then ℒN is closed under substitution into ℒ1 if and only if ℒ1 is a family of regular sets. Hence ℒN is a proper subfamily of ℒ.