A Software Module for Working with Context-Free Grammars

Abstract

The article presents the development of an educational software module to support the initial stage of learning formal grammars. The developed module allows the student or teacher to describe a given language through context-free grammar. In the process of completing a grammar assignment, the module provides an interactive response to the differences between the constructed grammar and the reference one. The main technical problem that the authors solved is related to the fact that there is no algorithm for determining the equivalence of two context-free grammars. Therefore, the module must generate in real time a sufficiently large number of words of a language of different lengths in order to detect differences between the proposed grammar and the reference one with a high probability. In the work, several word generation algorithms were analyzed, after which the algorithm most appropriate to the conditions of use of the module was selected. The developed module can be used for conducting Olympiads in discrete mathematics and computer science for schoolchildren and students, as well as to support students’ independent work on the topic "Formal languages and grammars".