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

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