6
$\begingroup$

Consider an ambiguous context-free grammar $G$. Define $A(G)$ the set of ambiguous words, meaning: $$A(G) = \{u\in L(G) \mid u \text{ has at least two derivation trees for }G\}$$ Can we say something about $A(G)$ in the general case? In particular, is $A(G)$ a context-free language?

$\endgroup$
1
  • 1
    $\begingroup$ My hunch is no. Suppose you can divide the productions for $G$ into two subsets, not necessarily disjoint, creating $G_1$ and $G_2$, such that both are unambiguous. This isn't possible in general, but it's sufficient that it is sometimes possible. Now $A(G)$ is (a subset of) $G_1\cap G_2$, which is not necessarily CFG. Lots of handwaving there but perhaps it can be cleaned up into something more formal. $\endgroup$
    – rici
    Commented Nov 9, 2022 at 18:27

1 Answer 1

8
$\begingroup$

The standard example that context-free languages are not closed under intersection can also be used as a counter-example for the language of ambiguous words.

Construct unambiguous grammars for $\{ a^n b^n c^m \mid m,n\ge 1\}$ and $\{ a^m b^n c^n \mid m,n\ge 1\}$. Take the union of these grammars in the common way. The union language is of course context-free, but the ambiguous strings are in the intersection, which is not context-free.

$\endgroup$
5
  • $\begingroup$ Thanks for the answer, it was quite simple :-) Now the follow-up would be: is it at least context-sensitive? $\endgroup$
    – Nathaniel
    Commented Nov 9, 2022 at 19:26
  • $\begingroup$ It also is the example for which no unambiguous grammar exists, if I am not mistaken, so it was a natural point to start. $\endgroup$ Commented Nov 9, 2022 at 19:46
  • $\begingroup$ I am quite convinced the language is context-sensitive. A linear-bounded automaton can try to generate all derivations for a given string. This is obvious, except when $\varepsilon$-productions are allowed in the context-free grammar. But those can most probably be removed without changing ambiguity. (Waves hands.) $\endgroup$ Commented Nov 9, 2022 at 21:00
  • $\begingroup$ How would you remove $ε$-productions from $\{S\rightarrow S \mid \varepsilon\}$ without changing ambiguity? $\endgroup$
    – Nathaniel
    Commented Nov 9, 2022 at 21:05
  • 1
    $\begingroup$ @Nathaniel Sorry, you are right. What I intended to say is that we can deduce where derivations $A \Rightarrow^* \varepsilon$ are unambigous or not. This knowledge can be built in the linear-bounded automaton, and then $\varepsilon$-productions can be removed marking all impacted rules as ambiguous. (Shrugging face.) $\endgroup$ Commented Nov 10, 2022 at 0:39

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.