The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
47 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 ...
15
votes
0answers
343 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})$?

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
vote
1answer
177 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. ...
2
votes
2answers
63 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 ...
2
votes
1answer
254 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.g. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost ...