Skip to main content
6 votes
Accepted

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
3 votes
Accepted

Modify DCFG to enforce length limit

A partial answer: The number of productions needed by a (not necessarily deterministic) context-free grammar generating $L\cap \Sigma^{\le N}$ in the worst case is $\Theta(N^2)$, as given in Theorem 4 ...
Hermann Gruber's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible