HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the ambiguity of a regular tree grammar decidable?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#9745, answer score: 3

Revisions (0)

No revisions yet.