Введение к работе
Актуальность темы. Класс регулярных языков занимает центральное положение по отношению к значительной части теории формальных языков. Вопрос о том, порождает ли данная бесконтекстная грамматика регулярный язык, составляет так называемую проблему регулярности для бесконтекстных языков; хорошо известно, что эта проблема алгоритмически неразрешима.
Тем не менее, выделение подклассов бесконтекстных языков с разрешимой проблемой регулярности и нахождение новых ха-рактеризаций для регулярных языков представляют интерес не только для теории формальных языков, но и для ее приложений. Интерес для приложений обусловлен следующим.
Бесконтекстные грамматики широко используются для описания синтаксиса языков программирования, а понятие магазинного автомата лежит в основе многих алгоритмов распознавания и синтаксического анализа языков. Наиболее общие такие алгоритмы подходят для широких классов грамматик, но их существенным недостатком является слишком большой объем анализатора, получаемого по грамматике.
Одна из идей, направленных на уменьшение сложности анализаторов, предполагает разбиение исходной грамматики на части, с тем, чтобы для каждой из полученных частей построить анализатор небольшого объема. Может оказаться, что лежащий в основе анализатора магазинный автомат допускает регулярный язык с неоправданными затратами памяти или времени. В целях повышения эффективности анализа, недостаточно рациональные магазинные автоматы, допускающие регулярные языки, можно заменить эквивалентными конечными.
Цель работы состоит в нахождении алгоритмически проверяемых условий регулярности бесконтекстного языка и создании понятийной среды, которая удобна для отыскания таких условий.
Научная новизна. В терминах теории D-графов определяется подкласс магазинных автоматов, названных автоматами без самовставления. Доказывается, что он характеризует регулярные языки. Принадлежность автомата данному классу распознаваема, что дает нетривиальное достаточное условие регулярности бесконтекстного языка.
Магазинные автоматы без самовставления являются, по-видимому, наиболее общими по своему виду магазинными автоматами из тех, о которых установлено, что они характеризуют регулярные языки.
Важным вспомогательным результатом является алгоритм преобразования так называемого ядра магазинного автомата в бесконтекстную грамматику. Получаемая грамматика наследует свойства исходного автомата. В частности, грамматика не имеет самовставляющихся символов тогда и только тогда, когда автомат является автоматом без самовставления.
Самому понятию ядра в работе дано новое истолкование: определяется некоторый простейший вид вычислений автомата, и ядро трактуется как результат итеративного построения вычислений такого вида.
Теоретическая и практическая ценность. Задача распознавания регулярности в подклассах класса бесконтекстных языков представляет интерес для практики описания и трансляции языков программирования, так как алгоритмы такого распознавания могут служить средством отыскания непозволительно сложных фрагментов языковых описаний.
Свойства приведенного в работе алгоритма построения эквивалентной магазинному автомату грамматики позволяют более широко использовать в теории автоматов те понятия и факты, которые сформулированы в терминах грамматик.
Апробация работы. Результаты диссертационной работы докладывались на Третьей международной конференции по алгебре (Красноярск, 1993), научно-исследовательском семинаре по автоматизации программирования (факультет ВМиК МГУ, март 1998).
Публикации. По теме диссертации имеется 3 публикации, список которых приводится в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, одного вспомогательного и трех основных разделов и списка литературы. Общий объем диссертации — 79 страниц. Библиография включает 53 наименования.