Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
3 votes

Generating grammar from a string

You might be interested in Sequitur (given a single string, it compresses it by finding a grammar that generates just that one string) or in grammar induction (given a set of strings, it finds a ...
D.W.'s user avatar
  • 12.1k
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

What is the intution on the TTT algorithm for regular grammar inference?

If you get a counterexample back from the teacher the counterexample is very long. If the suffix analysis is used as described in the paper, the suffix can be very long, this suffix is added in the ...
Coping Forever's user avatar

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