I’m actually not sure it’s a regular grammar. Consider this program:
f(n) := n+f(n-1)
Which gives the tree
n+(n-1)+((n-1)-1)+...
The path from any 1 to the root contains a bunch of minuses, then at least as many pluses. That’s not regular.
So it’s probably some other kind of grammar, and I don’t know if it has decidable equivalence.
I’m actually not sure it’s a regular grammar. Consider this program:
Which gives the tree
The path from any 1 to the root contains a bunch of minuses, then at least as many pluses. That’s not regular.
So it’s probably some other kind of grammar, and I don’t know if it has decidable equivalence.