CHECKING AUTOMATA AND ONE-WAY STACK LANGUAGES,

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)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1968
Accession Number
AD0672970

Entities

People

  • Sheila Greibach

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Automata
  • Language

Fields of Study

  • Engineering

Readers

  • Computer Science.
  • Mathematical Modeling and Probability Theory.