Accession Number:

AD0668087

Title:

Derivation-Bounded Languages

Descriptive Note:

Technical Report

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CA SANTA MONICA United States

Personal Author(s):

Report Date:

1968-01-08

Pagination or Media Count:

43.0

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.

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE