Введение к работе
Актуальность. Изтіестмо огромное значение теории кою'-зкстно-)бод!шх языков для современного развития информатики. На осіє результатов в этой области разработано много практических яложений, которие с основанием модно утверждать, являются од-А из причин для быстрого темпа развития вычислительной тех-ки и программирования.
Имеются разине лодхохг /ри изучении свойства контекстно-' ободных языков и один из їй'/: - это применение теории полугрупп, от аппарат используется и в диссертации для решения конкрет-х задач.
Как известно, алгоритми, работающие за полиномиальное время
ляются одними из лучших ачгоритмов. В 1981 г. Д.. Sierns и
Hunl ,1906 г. A. Weicr и И. $eUU ив
89 г. І!/. Ku.c/t нашли полином.-.лдагае алгоритмы для провор-однозначности конечных автоматов. А.В.Анисимов в 1981 г. казал, что проверка однозначности конечно-автоматных отобраяе-й является следствием задачи о проверке включения контекстно-ободчых языков в групповие языки группы с разрешимой проблемой івенства слов и показал соответствующий алгоритм решающий эту ідачу. Как описан эгот алгоритм не следует, что он полиномиальный. іким образом возникает вопрос о возможности модифицировать сгориттл А.В.Анисшова, так, чтобы он работал за полиномиальное >емя. Одновременно о этим интерес представляют и чисто теоре-іческие разработки, связанные с этой проблемой.
Как доказал [. Ыггсп в 1975 г. формальный язык зляется кусочно-тестируемый тогда и только тогда, когда его штаксический моноид является Ї - тривиальным. Таким образом
_ 4 -
естественно возникает вопрос когда данная полугруппа является % - тривиальной. В этом аспекте в работе рассмотрен клас линейно-упорядоченных периодических полугрупп. Цели и задачи работа.
Исследовать класс линейно-упорядоченных полугрупп в связи с кусочно-тестируемыми язиками. Показать когда произвольная пер дическая полугруппа является линейно-упорядочиваемая и когда линейно-упорядоченная периодическая полугруппа является 7 -виальной.
Получение новых катодов описания контекстно-свободных языка
Модифицировать алгоритм Л.В.Анисимова, так, чтобы он работа за полиномиальное время.
Методы исследования. Гри реыении поставленных задач иена зовался аппарат теории полугрупп, теории графов, теории замкц
TUX ПОЛуКОЛеЦ, ТЄОРИИ Матриц, Теории КОНТеКСТНО-СВОбОДННХ ЯЗЫ1
и теории автоматов.
{іаучная новизна. Получены ряд теоретических разработок и: теории полутрупп, теории графов и теории формальних языков, а так ке описани полиномиальные алгоритмы, проверяющие включение 'регулярних и линейных языков в групповой язык группы с ра: решимой проблемой равенства слов.
Апробация работы. Ооновкые результаты работы докладывали! на международной конференции по теории полугрупп (г.Сегед, Вві грия, август 1987 г.), Двенадцатой научной конференции болгарских аспирантов в СССР с международным участием (Москва, июнь 1990 г.). Четырнадцатой (Солнечный берег, Болгария, апрель 1985 г.) и Двадцатой (Варна, Дружб;', Болгария, апрель 1991 г. весенншекаяфер&яций союза математиков Болгарии.
Публикации По теме диссертации опубликовано девять пэчат-работ.
Структура и объём работы, диссертационная работа состоит введения, трех глав, каждая глава из трех параграфов и списка ературы. Объём работы 115 страниц. Список литература ктает 167 наименований.