On inherently ambiguous E0L languages (Q796996)

In this paper the interesting topic of ambiguity of E0L languages is considered. It is known that an E0L system is called ambiguous if its language contains a word with (at least) two different derivation trees in G. An E0L language is called inherently E0L-ambiguous if every E0L system that generates it is ambiguous. The authors demonstrate that there exist inherently ambiguous E0L languages. Particularly it is proved that the language \[ \{a^ mb^{2^ n}:1\leq m\leq n\}\cup \{a^{m^ 2}b^{2^ n}:1\leq m\leq n\} \] is an inherently ambiguous E0L language.