Accession Number:

AD0672970

Title:

CHECKING AUTOMATA AND ONE-WAY STACK LANGUAGES,

Descriptive Note:

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s):

• Greibach,Sheila

Report Date:

1968-04-01

Pagination or Media Count:

36.0

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