5
$\begingroup$

Indexed languages are defined as being produced by an 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)?

$\endgroup$
1
  • $\begingroup$ 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 center that begins "Questions should be based on knowledge sharing...". $\endgroup$
    – D.W.
    Commented Sep 20, 2022 at 21:18

1 Answer 1

5
$\begingroup$

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.

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.

$\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.