4 votes

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018): Given a context-free grammar of size $s$ generating a finite language $L$, it is impossible to ...
Hermann Gruber's user avatar
2 votes

What is the current state of the art in black-box grammar induction?

Note that there is now a replication study (coauthored by Rahul Gopinath) of the 2017 paper Synthesizing Program Input Grammars, see https://publications.cispa.saarland/3607/1/pldi2022glade.pdf Two ...
Martin Berger's user avatar
1 vote

Pumping lemma for CFL intersection

The language $L_t=\{a_1^na_2^n\dots a_t^n:n\ge 0, a_i=a$ for odd $i$ and $a_i=b$ for even $i\}$ is the intersection of two CFL's, even $\cup_t~L_t$ is, and it is hard to imagine what kind of pumping ...
domotorp's user avatar
  • 13.9k
1 vote

Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

It is not known whether CFL is contained in space o(log^2(n)). If CFL were contained in space o(log^2(n)), then NL would also be contained in space o(log^2(n)). The question whether NL is contained in ...
user69092's user avatar

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