Введение к работе
Актуальность. Работа выполнена «на стыке» теории формальных языков и алгебры полугрупп. По мнению автора, в настояее время между этими разделами математики - теорией формальных языков и алгеброй полугрупп - построены ещё не все связи, и представленная диссертация рассматривает вопросы, касающиеся одной из этих недостающих связей.
ЛІножество рассматриваемых в диссертации вопросов полнее отразило бы такое длинное название: «Свойства специальных подмоноидов глобальных надмоноидов свободных моноидов с бесконечным числом образующих, решение некоторых проблем эквивалентности в этих подмоноидах и применение полученных необходимых и достаточных условий в различных задачах, исследующих нетрадиционные способы задания подклассов класса контекстно-свободных языков». Автор видит в таком название проявление связи между теорией формальных языков и алгеброй полугрупп.
Научная новизна. В работе рассматриваются различные примеры применения алгебраических свойств специальных- подмоноидов глобальных надмоноидов свободных моноидов (супермоноидов) к решению проблем эквивалентности в различных подклассах класса КС-языков. Подобных примеров применения свойств сулермоноядов в теории формальных языков автору не известно. Да и сами проблемы равенства в глобальных надмоноидах, рассматриваемые автором, ранее не исследовались.
Кроме того, в связи с двумя следующими фактами:
бесконечности рассматриваемых в работе алфавитов;
применении доказанных утверждений, относящихся к алгебре полугрупп, к некоторым задачам теории контекстно-свободных языков,
- в качестве примера «научной новизны» стоит отметить еле-
дующее обстоятельство. Контекстно-свободные языки определяются над конечным алфавитом, причём для каждого нетерминала имеется конечное множество правил: Однако для исследования многих конкретных КС-языков часто оказывается удобным рассматривать и специальные расширения класса контекстно-свободных языков - например, допускать языки над бесконечным алфавитом, и/или рассматривать грамматики с бесконечным числом правил. * Таким образом, можно считать, что автором исследовано специальное расширение класса КС-языков: определён класс простых скобочных языков, исследована проблема эквивалентности в нём (сводящаяся к одноіі из описанных выше проблем эквивалентности в глобальном надмоноиде свободного моноида с бесконечным числом образующих), а также показана возможность применения полученных результатов в других задачах.
Практическое применение. Диссертация формулирует темы для дальнейших научных работ на стыке теории формальных языков, алгебры полугрупп и информатики; вот некоторые из таких тем:
специальные алгоритмы минимизации конечных автоматов;
применение конечных автоматов для исследования проблем эквивалентности в различных подклассах класса контекстно-свободных языков;
описание образующих элементов специальных подмонои-дов глобальных надмоноидов свободных моноидов (с конечным или бесконечным числом образующих);
формулировка достаточных условий возможности описания языка (или некоторой грамматической структуры)
1 Прп этом, коне^шо, на множества правых частей правил каждого конкретного нетерминала должны быть наложены специальные ограничения, — в противном случае подобная «грамматика* могла бы допускать произвольный язык над рассматриваемым алфавитом.
как последовательности простых скобочных языков;
скобочные и простые скобочные языки без «префиксно-суффиксных» ограничений.
Все эти темы связаны с соответствующими разделами настоящей диссертации.
При проектировании и реализации программных систем, работающих с конечными автоматами, могут быть полезными варианты алгоритмов их эквивалентного преобразования, приведённые в диссертационной работе (см. подробнее ниже, раздел «Содержание работы»).
Кроме того, в системах автоматизации построения трансляторов, а также в автоматизированных системах, предназначенных для работы с естественными языками, могут найти применение результаты главы «Проблемы равенства в классе простых скобочных языков» (также см. раздел «Содержание работы»). Такие работы в настоящее время также ведутся в Ульяновском университете под руководством автора данной диссертации (работы были поддержаны грантом фонда «Университеты России»).
Структура и объём диссертационной работы. Диссертация состоит из введения, двух частей (подразделяющихся на 10 глав), заключения, трёх приложений, предметного указателя и списка литературы, включающего 90 названий. Общий объём диссертации - 240 машинописных страниц.
