patternMinor
Is the ambiguity of a regular tree grammar decidable?
Viewed 0 times
theregularambiguitydecidablegrammartree
Problem
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?
Is there a proof available about the decidability, or a cite to a paper which proposes such an algorithm?
Solution
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.
The same is true, mutatis mutandis, for regular tree grammars.
Context
StackExchange Computer Science Q#9745, answer score: 3
Revisions (0)
No revisions yet.