ICS Theory Group

Winter 2017: Theory Seminar
Bren Hall, Room 1300, 1:00pm


January 27, 2017:

Automatic Evaluation of Context-Free Grammars

Nil Mamano

We implement an online judge for context-free grammars. Our system contains a list of problems describing formal languages, and asking for grammars generating them. A submitted proposal grammar receives a verdict of acceptance or rejection depending on whether the judge determines that it is equivalent to the reference solution grammar provided by the problem setter. Since equivalence of context-free grammars is an undecidable problem, we consider a maximum length $\ell$ and only test equivalence of the generated languages up to words of length $\ell$. This length restriction is very often sufficient for the well-meant submissions. Since this restricted problem is still $\mathsf{NP}$-complete, we design and implement methods based on hashing, SAT, and automata that perform well in practice.

(Based on a paper by Carles Creus and Guillem Godoy from the International Conference on Rewriting Techniques and Applications, RTA 2014)