Skip to main content

Questions tagged [tree-grammars]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
33 views

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 ...
1 vote
0 answers
26 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: ...
43 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 ...
0 votes
0 answers
284 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 ...
0 votes
1 answer
51 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 ...
0 votes
1 answer
70 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
26 views

Confused about substitution in grammar in certain cases

To illustrate my confusion let's say I'm given this unambiguous grammar in BNF: ...
1 vote
1 answer
92 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: ...
2 votes
0 answers
175 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{...
5 votes
0 answers
181 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 ...
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 ...
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 ...
2 votes
1 answer
116 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 $\...
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, ...
2 votes
1 answer
112 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 ...
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 ...
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 ...