# Is the ambiguity of a regular tree grammar decidable?

Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.e. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost derivations?

Is there a proof available about the decidability, or a cite to a paper which proposes such an algorithm?

• What do you mean by "regular tree grammar"? – vonbrand Feb 13 '13 at 16:44
• @vonbrand, this – Karolis Juodelė Feb 13 '13 at 16:48
• A cursory look makes this expressible by a LISP-like language (use () to enclose each tree), so the corresponding context free language is LR(0). My answer would be that the flattened grammar is LR(0) exactly when the tree grammar is unambiguous. But I might be overlooking something... – vonbrand Feb 13 '13 at 17:15
• @vonbrand nice idea. what exactly do you mean by enclosing each tree with brackets? Each root node of a right hand side of each production? Each node which is not a leave? – mruether Feb 13 '13 at 19:03

Start by considering regular string grammars. We can determine whether one such grammar $G$ is ambiguous by constructing the intersection of the grammar with itself, with a direct product construction. The nonterminals are pairs $(A,B)$ of nonterminals from the original string grammar $G$. The new grammar of course also derives the original language $L(G)$, but the new grammar has a nonterminal $(A,B)$ with $A\neq B$ in a succesful derivation, iff $G$ is ambiguous. It is decidable whether any given nonterminal occurs in a succesful derivation, so ambiguity is decidable for regular grammars.
• The grammar $S \to aS \mid aaS \mid a$ is ambiguous, yet I doubt you'll find the pair you are looking for in the product. I think the basic idea can work; you need to find disagreeing pairs of productions, though. – Raphael Feb 14 '13 at 6:43