CHAINS OF FULL AFLS

Abstract

If a full Abstract Family of Languages (AFL) L is not closed under substitution, then the result of substituting members of L into L, is not substitution closed and hence L generates an infinite hierarchy of full AFLs. If L1 and L2 are two incomparable full AFLs, then the least full AFL containing L1 and L2 is not substitution closed. In particular, the substitution closure of any full AFL properly contained in the context-free languages is itself properly contained in the context-free languages. If any set of languages generates the context-free languages, one of its members must do so. The substitution closure of the one-way stack languages is properly contained in the nested stack languages. For each n, there is a class of full context-free AFLs whose partial ordering under inclusion is isomorphic to the natural partial ordering on n-tuples of positive integers.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 12, 1969
Accession Number
AD0693584

Entities

People

  • Sheila A. Greibach

Organizations

  • System Development Corporation

Tags

Communities of Interest

  • Space

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Automata
  • Classification
  • Commerce
  • Contracts
  • Corporations
  • Data Science
  • Generators
  • Hierarchies
  • Inclusions
  • Language
  • Massachusetts
  • Nomenclature
  • Scientific Research
  • Security
  • Words (Language)

Readers

  • Graph Algorithms and Convex Optimization.
  • International Journalism and Media Studies.
  • Materials Science