4
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.