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
6 votes

Intersection Non-Emptiness for Two-Way Finite Automata

Unlike one-way models, intersection of 2-way NFAs is "cheap": Given 2-way NFAs $A_1,A_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves ...
Shaull's user avatar
  • 5,646
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