# Language of ambiguous words

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?

• 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.
– rici
Commented Nov 9, 2022 at 18:27

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.
• 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.) Commented Nov 9, 2022 at 21:00
• How would you remove $ε$-productions from $\{S\rightarrow S \mid \varepsilon\}$ without changing ambiguity? Commented Nov 9, 2022 at 21:05
• @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.) Commented Nov 10, 2022 at 0:39