Программный модуль для работы с контекстно-свободными грамматиками

Аннотация

В статье представлена разработка учебного программного модуля для поддержки начального этапа обучения формальным грамматикам. Разработанный модуль позволяет студенту или преподавателю описывать заданный язык посредством контекстно-свободной грамматики. В процессе выполнения учебного задания по написанию грамматики модуль в интерактивном режиме обеспечивает реакцию на отличия построенной грамматики от эталонной. Основная техническая проблема, которую решали авторы, связана с тем, что не существует алгоритма определения эквивалентности двух контекстно-свободных грамматик. Поэтому модуль должен в реальном времени генерировать достаточно большое число слов языка различной длины, чтобы с большой вероятностью обнаружить отличия предложенной грамматики от эталонной. В работе было проанализировано несколько алгоритмов генерации слов, после чего выбран алгоритм, наиболее соответствующий условиям использования модуля. Разработанный модуль можно использовать для проведения олимпиад по дискретной математике и информатике у школьников и студентов, а также для поддержки самостоятельной работы студентов над темой «Формальные языки и грамматики».