Derivation-Bounded Languages

Abstract

A derivation is a phrase-structure grammar is said to be k-bounded if each word in the derivation contains at most k occurrences of nonterminals. A set L is said to be derivation bounded if there exists a phrase-structure grammar G and a positive inter k such that L is the set of words in the language generated by G which have some k-bounded derivation. The main result is that every derivation-bounded set is a context-free language. Various characterizations of the derivation-bounded languages are then given. For example, the derivation-bounded languages coincide with the standard matching-choice sets discussed by Yntema. They also coincide with the smallest family of sets containing the linear context free languages and closed under arbitrary substitution.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 08, 1968
Accession Number
AD0668087

Entities

People

  • Edwin H. Spanier
  • Seymour Ginsburg

Organizations

  • System Development Corporation

Tags

Communities of Interest

  • Space

DTIC Thesaurus Topics

  • Air Force
  • California
  • Colorado
  • Context Free Grammars
  • Contracts
  • Corporations
  • Data Science
  • Formal Languages
  • Grammars
  • Language
  • New York
  • Phrase Structure Grammars
  • Production
  • Scientific Research
  • Standards
  • United States

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Atmospheric Science/Meteorology
  • Computational Linguistics