Accession Number : AD0672970

Title :   CHECKING AUTOMATA AND ONE-WAY STACK LANGUAGES,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s) : Greibach,Sheila

Report Date : 01 APR 1968

Pagination or Media Count : 36

Abstract : A checking automaton is equivalent to a one-way nonerasing stack automaton which, once it enters its stack, never again writes on its stack. The checking automaton languages (cal) form a full AFL (Abstract Family of Languages) closed under substitution. If L is contained in a* is an infinite cal, then L contains an infinite regular set. Consequently, there are one-way nonerasing stack languages which are not cal. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, COMPUTATIONAL LINGUISTICS), THEOREMS, CONTEXT FREE GRAMMARS, SEQUENCES(MATHEMATICS), SET THEORY, AUTOMATA, SYNTAX

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE