Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Indexed languages are defined as being produced by indexed grammar.
Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language without any indexed grammar which may produce every word or sentence of the language in a unique way? Or in other word, may all context-free language be produced by indexed grammar in a unique way?
I just wrote this in an answer to the OP's other question on this topic, but for reasons of self-containedness, let me just reproduce the relevant part again:
This is an open question, which is explicitly stated in the paper
Adams, Jared; Freden, Eric; Mishna, Marni, From indexed grammars to generating functions, RAIRO, Theor. Inform. Appl. 47, No. 4, 325-350 (2013). ZBL1286.68331.
They also provide some examples which they conjecture to be inherently ambiguous indexed languages:
Consider Crestin’s language of palindrome pairs defined by $L_{Crestin} = \{vw : v, w \in (a|b)^* , v = v^R w = w^R\}$. It is a “worst case” example of an inherently ambiguous context-free language (see [8] and its references). We conjecture that $L_{Crestin}$ remains inherently ambiguous as an indexed language.
