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?

  • $\begingroup$ What do you mean by "regular tree grammar"? $\endgroup$ – vonbrand Feb 13 '13 at 16:44
  • 1
    $\begingroup$ @vonbrand, this $\endgroup$ – Karolis Juodelė Feb 13 '13 at 16:48
  • $\begingroup$ 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... $\endgroup$ – vonbrand Feb 13 '13 at 17:15
  • $\begingroup$ @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? $\endgroup$ – 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 same is true, mutatis mutandis, for regular tree grammars.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 14 '13 at 6:43
  • $\begingroup$ Thanks @Raphael. Indeed, it is about finding disagreeing pairs of productions, while the letters generated match. However, I was not thinking of grammars, but based my intuition on finite state automata. Because regular tree grammars are somewhat like automata, except the "control" moves to parallel branches. I will rephrase this later. $\endgroup$ – Hendrik Jan Feb 14 '13 at 11:10
  • $\begingroup$ @HendrikJan please keep in mind, that the letters do have an arity, where only nullary letters are used as leaves, all others with a higher arity are inner nodes of a tree. $\endgroup$ – mruether Feb 14 '13 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.