<p><em>I just wrote this in <a href="https://cstheory.stackexchange.com/a/52184/2367">an answer to the OP's other question on this topic</a>, but for reasons of self-containedness, let me just reproduce the relevant part again:</em></p>
<p>This is an open question, which is explicitly stated in the paper</p>
<p><em>Adams, Jared; Freden, Eric; Mishna, Marni</em>, <a href="http://dx.doi.org/10.1051/ita/2013041" rel="nofollow noreferrer"><strong>From indexed grammars to generating functions</strong></a>, RAIRO, Theor. Inform. Appl. 47, No. 4, 325-350 (2013). <a href="https://zbmath.org/?q=an:1286.68331" rel="nofollow noreferrer">ZBL1286.68331</a>.</p>
<p>They also provide some examples which they conjecture to be inherently ambiguous indexed languages:</p>
<blockquote>
<p>Consider Crestin’s language of palindrome pairs defined by
<span class="math-container">$L_{Crestin} =  \{vw : v, w \in (a|b)^* , v = v^R w = w^R\}$</span>. It is a
“worst case” example of an inherently ambiguous context-free language
(see [8] and its references). We conjecture that <span class="math-container">$L_{Crestin}$</span> remains
inherently ambiguous as an indexed language.</p>
</blockquote>

CC BY-SA 4.0
2022-11-21T21:00:19.970Z
2022-11-21T21:00:19.970Z
Hermann Gruber
<p>Indexed languages are defined as being produced by indexed grammar.</p>
<p>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?</p>

<fl.formal-languages><automata-theory><grammars><ambiguity>
Is there any context-free language that is inherently ambiguous as an indexed language
WangAtChicago
# Is there any context-free language that is inherently ambiguous as an indexed language

(Asked by: username_0 on 2022-09-21)

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?

**Tags:** fl.formal-languages, automata-theory, grammars, ambiguity

---

## 1 answers

### Answer by username_1 on 2022-11-21. Score: 4

*I just wrote this in [an answer to the OP's other question on this topic](https://cstheory.stackexchange.com/a/52184/2367), 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**](http://dx.doi.org/10.1051/ita/2013041), RAIRO, Theor. Inform. Appl. 47, No. 4, 325-350 (2013). [ZBL1286.68331](https://zbmath.org/?q=an:1286.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.


---

