<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="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="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>
<p>A non-contextfree example:</p>
<blockquote>
<p>Recall that a word is primitive if it is not a power of another word.
In the copious literature on the subject it is customary to let <span class="math-container">$Q$</span>
denote the language of primitive words over a two letter alphabet.
[...]</p>
<p><span class="math-container">$L' = \{ w^k : w \in (a|b)^* , k &gt; 1 \}$</span>  defines the complement
of <span class="math-container">$Q$</span> with respect to the free monoid <span class="math-container">$(a|b)^*$</span>.  It is not difficult
to construct an ambiguous balanced grammar for <span class="math-container">$L'$</span> [...]. What about an
unambiguous grammar? Recall from [20] that <span class="math-container">$w_1^n = w_2^m$</span> implies
that each <span class="math-container">$w^i$</span> is a power of a common word <span class="math-container">$v$</span>. Thus to avoid
ambiguity, each building block <span class="math-container">$w$</span> used to construct <span class="math-container">$L'$</span> needs to be
primitive. This means we must not only be able to recreate <span class="math-container">$Q$</span> in
order to generate <span class="math-container">$L$</span> unambiguously, we must be able to encode each
word <span class="math-container">$w \in Q$</span> as a string of index symbols, as per the language of
composites. We refer again to Section 3.1. We find this highly
unlikely and we conjecture that <span class="math-container">$L' = \{ w^k : w \in (a|b)^* , k &gt; 1\}$</span>
is inherently ambiguous as an indexed language.</p>
</blockquote>
<p>For more details and examples, please consult the paper.</p>

CC BY-SA 4.0
2022-11-21T20:56:12.183Z
2022-11-21T20:56:12.183Z
Hermann Gruber
<p>Indexed languages are defined as being produced by an <a href="https://en.wikipedia.org/wiki/Indexed_grammar" rel="nofollow noreferrer">indexed grammar</a>.
My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in a unique way (without ambiguity)?</p>

CC BY-SA 4.0
2022-09-20T21:18:00.867Z
Please ask only one question per post.  I encourage you to make the question interesting for others by providing some background and showing what progress you have made attempting to solve the question on your own.  Please see the section of our [help/on-topic] that begins "Questions should be based on knowledge sharing...".
D.W.
<fl.formal-languages><automata-theory><grammars>
Is there any inherently ambiguous indexed language?
WangAtChicago
# Is there any inherently ambiguous indexed language?

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

Indexed languages are defined as being produced by an [indexed grammar](https://en.wikipedia.org/wiki/Indexed_grammar).
My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in a unique way (without ambiguity)?

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

> **Comments:**
> **username_1**: Please ask only one question per post.  I encourage you to make the question interesting for others by providing some background and showing what progress you have made attempting to solve the question on your own.  Please see the section of our [help/on-topic] that begins "Questions should be based on knowledge sharing...".  

---

## 1 answers

### Answer by username_2 on 2022-11-21. Score: 5

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.

A non-contextfree example:

> Recall that a word is primitive if it is not a power of another word.
> In the copious literature on the subject it is customary to let $Q$
> denote the language of primitive words over a two letter alphabet.
> [...]
>
> $L' = \{ w^k : w \in (a|b)^\* , k > 1 \}$ defines the complement
> of $Q$ with respect to the free monoid $(a|b)^\*$. It is not difficult
> to construct an ambiguous balanced grammar for $L'$ [...]. What about an
> unambiguous grammar? Recall from [20] that $w\_1^n = w\_2^m$ implies
> that each $w^i$ is a power of a common word $v$. Thus to avoid
> ambiguity, each building block $w$ used to construct $L'$ needs to be
> primitive. This means we must not only be able to recreate $Q$ in
> order to generate $L$ unambiguously, we must be able to encode each
> word $w \in Q$ as a string of index symbols, as per the language of
> composites. We refer again to Section 3.1. We find this highly
> unlikely and we conjecture that $L' = \{ w^k : w \in (a|b)^\* , k > 1\}$
> is inherently ambiguous as an indexed language.

For more details and examples, please consult the paper.


---

