## 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)