All Questions
1 question
10
votes
0
answers
274
views
Complexity of a problem over acyclic context-free grammars
Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
- 500