SYSTEM DEVELOPMENT CORP SANTA MONICA CA SANTA MONICA United States
Pagination or Media Count:
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.