Skip to main content

Questions tagged [tree-grammars]

The tag has no usage guidance.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers

Weak equivalent tree grammar for Context-sensitive word grammar?

Consider arbitrary context-sensitive grammar on strings $G_s$. Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which ...
Andrey Lebedev's user avatar
3 votes
0 answers

Tree Languages are Word Languages on an Infinite Alphabet of Contexts

I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand. In the beginning of Chapter 2, ...
john_leo's user avatar
  • 1,901
2 votes
0 answers

Unranked trees grammars?

Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{...
Andrey Lebedev's user avatar
1 vote
0 answers

Extending minimal top-down tree automata

I'm trying to find an algorithm to update minimal top-down tree automata/hypergraphs. Regular tree grammars can be seen as definitions for recursive data structures: ...
Taren's user avatar
  • 111
0 votes
0 answers

It shows that CF grammar is ambiguous

Let $G$ be the CF grammar that has the production rules: $S \to aS | aSbS | c$. Show that $G$ is ambiguous. I thought of proving it by representing the string $aacbc$ but I don't know if it is correct ...
Luca 's user avatar
  • 63
0 votes
0 answers

How to count number of parse trees for a specific grammar

The task: You are standing in front of a gigantic forest of syntax trees. One tree looks more fascinating than the other. In front of the forest is a sign: "Every tree in this forest arises from ...
kirekhar's user avatar