New answers tagged

2 votes

Modify DCFG to enforce length limit

The number of productions needed by a context-free grammar generating $L\cap \Sigma^{\le N}$ in the worst case is $\Theta(N^2)$, as given in Theorem 4 of W. Bucher, H.A. Maurer, K. Culik, D. Wotschke,...
Hermann Gruber's user avatar
0 votes

Does there exist an extension of regular expressions that captures the context free languages?

Yes. A simple example should suffice to show both what and how. Consider the grammar given by $$S → x,\quad S → u S v.$$ This specifies a subset of $\{u,x,v\}^*$ and - more generally - a context-free ...
NinjaDarth's user avatar
0 votes

Modify DCFG to enforce length limit

Here is one algorithm:- Step 1: Convert the grammar to CNF. This should take time O(square of no. Of productions) Idea: The basic idea is to subscript each use of non terminals. For each variable X, ...
harshchy2210's user avatar

Top 50 recent answers are included