A note on ambiguity of internal contextual grammars

Abstract

In this paper, we continue the study of ambiguity of internal contextual grammars which was investigated in Ilie [On ambiguity in internal contextual languages, in: C. Martin-Vide (Ed.), Second Int. Conf. on Mathematical Linguistics, Tarragona, 1996, John Benjamins, Amsterdam, 1997, pp. 29-45] and Martin-Vide et al. [Attempting to define the ambiguity in internal contextual languages, in: C. Martin-Vide (Ed.), Second Int. Conf. on Mathematical Linguistics, Tarragona, 1996, John Benjamins, Amsterdam, 1997, pp. 59-81]. We solve some open problems formulated in these papers. The main results are: (i) there are inherently 1-ambiguous languages with respect to internal contextual grammars with arbitrary choice which are 0-unambiguous with respect to finite choice, (ii) there are inherently 2-ambiguous languages with respect to internal contextual grammars with arbitrary choice which are 1-unambiguous with respect to regular choice, and (iii) there are inherently 2-ambiguous languages with respect to depth-first internal contextual grammars with arbitrary choice which are 1-unambiguous with respect to finite choice. 2006 Elsevier B.V. All rights reserved.