Questions tagged [tree-grammars]
The tree-grammars tag has no usage guidance.
16
questions
42
votes
0
answers
2k
views
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$? [closed]
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
- 1,861
5
votes
0
answers
180
views
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 ...
- 345
4
votes
1
answer
1k
views
Is the ambiguity of a regular tree grammar decidable?
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 ...
- 96
3
votes
0
answers
56
views
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, ...
- 1,861
2
votes
1
answer
114
views
Deriving from a terminal word in a context free grammar
Just to make it clear.
(since my book doesn't mention anything like this)
Suppose we have a context free grammar $G=(V,T,P,S)$.
where $T=\{a,b\}$ (The other sets doesn't really matter).
Since $\...
- 242
2
votes
2
answers
111
views
I'm lookin for a method to construct a particular grammar?
I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the ...
- 465
2
votes
1
answer
106
views
"Grammar inference" for 2-D images
Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in ...
D.W.♦
- 154k
2
votes
0
answers
174
views
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{...
- 345
1
vote
1
answer
71
views
How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?
I don't get how to intuitively come up with an example for an ambiguous grammar.
Let's take as an example this grammar:
...
- 251
1
vote
1
answer
2k
views
Derive a Context Free Grammar from a language
I am having challenges (in two phases) with creating a CFG.
Derive the CFG for the following language
Show parse trees for the strings cacab and aacabbb obtained from the grammar designed above.
I ...
- 123
1
vote
0
answers
20
views
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:
...
- 111
0
votes
1
answer
48
views
Adding constraints in grammar for Grammatical Evolution
I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p ...
- 103
0
votes
1
answer
25
views
Confused about substitution in grammar in certain cases
To illustrate my confusion let's say I'm given this unambiguous grammar in BNF:
...
- 251
0
votes
0
answers
172
views
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 ...
- 1
0
votes
1
answer
57
views
Ambiguous Grammar demostration exercise
Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows:
$$S \rightarrow aT | bR$$
$$R \rightarrow a | aS | bRR$...
0
votes
1
answer
38
views
Unsure about parse tree of PCFG
I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa.
My solution would look like
...
- 111