Accession Number : AD0613290

Title :   THE INDEPENDENCE OF INHERENT AMBIGUITY FROM COMPLEMENTEDNESS AMONG CONTEXT FREE LANGUAGES,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s) : Hibbard,T. ; Ullian,J.

Report Date : 10 NOV 1964

Pagination or Media Count : 17

Abstract : A context free language may be called unambiguous if it is not inherently ambiguous. In the absence of evidence to the contrary, the suspicion has arisen that the unambiguous languages might be precisely those languages with context free complements. The two theorems presented lay the suspicion to rest by providing (I) an inherently ambiguous language with context free complement and (II) an unambiguous language without context free complement. This establishes the independence of inherent ambiguity from complementedness among the context free languages. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, THEORY), MATHEMATICAL LOGIC, SET THEORY, ALGEBRA

Distribution Statement : APPROVED FOR PUBLIC RELEASE