Accession Number:

AD0614073

Title:

PRESERVATION OF UNAMBIGUITY AND INHERENT AMBIGUITY IN CONTEXT FREE LANGUAGES.

Descriptive Note:

Technical memo.,

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s):

Report Date:

1965-01-12

Pagination or Media Count:

16.0

Abstract:

Various elementary operations are studied to find whether they preserve unambiguity and inherent ambiguity of languages language means context free language. The following results are established 1 If L is an unambiguous language and S is a generalized sequential machine then a SL is an unambiguous language if S is one-to-one on L, and b S-1L is an unambiguous language. 2 Inherent ambiguity is preserved by every generalized sequential machine which is one-to-one on the set of all words. 3 The product either left or right of a language and a word preserves both unambiguity and inherent ambiguity. 4 Neither unambiguity nor inherent ambiguity is preserved by any of the following languagepreserving operations a one-state complete sequential machine b product by a two-element set c InitL u is not equal to Euv in L for some v d SubwL w is not equal to Euwv in L for some u, v. Author

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE