# zbMATH — the first resource for mathematics

Automatic evaluation of context-free grammars (system description). (English) Zbl 1416.68089
Dowek, Gilles (ed.), Rewriting and typed lambda calculi. Joint international conference, RTA-TLCA 2014, held as part of the Vienna summer of logic, VSL 2014, Vienna, Austria, July 14–17, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8560, 139-148 (2014).
Summary: 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 NP-complete, we design and implement methods based on hashing, SAT, and automata that perform well in practice.
For the entire collection see [Zbl 1291.68017].
##### MSC:
 68Q42 Grammars and rewriting systems 68Q45 Formal languages and automata
##### Keywords:
grammars; equivalence; hashing; SAT; automata
##### Software:
Chaff; HAMPI; PicoSAT; SATIRE
Full Text: