Document Type

Technical Report

Publication Date

Summer 8-1-1979

Abstract

It is demonstrated that the degree of ambiguity of a context free language K in the class of EOL systems is not larger than the degree of ambiguity of K in the class of context free grammars. A language K is said to have the negative prefix property if no word K catenated with a nonempty prefix of a word from K+ yields an element of K. It is shown that if an EOL language has the negative prefix property and is EOL-unambiguous then K+ is also EOL-unambiguous. Using those results several conjectures concerning ambiguity of EOL languages are disproved.

Share

COinS