автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Применение свойств специальных моноидов в теории формальных языков

МЕЛЬНИКОВ Борис Феликсович

специальных моноидов в теории формальных языков

Специальность 05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат 7Ш на соискание учёной степени

РГ8 ОД

Применение свойств

и

физико-

>-математических наук

Ульяновск, 1997

Работа выполнена в Ульяновском государственном университете

Официальные оппоненты: доктор физико-математических доктор физико-математических д октор физико- м атематич еских

наук Р. Л.Смелянский

паук Р. И. Подловченко

наук В. Н. Латышев

Ведущая организация:

Саратовский государственный университет

Защита состоится" " 1997 г. в часов на за-

седании специализированного совета Д.053.05.38 по математике при МГУ им.М.В.Ломоносова по адресу: 199899, Москва, ГСП, В-234, Воробьёвы горы, МГУ, факультет вычислительной математики и кибернетики, ауд.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан " " 1997 г.

Учёный секретарь совета

профессор Н. П. Трифонов

Общая характеристика работы

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

ЛГножество рассматриваемых в диссертации вопросов полнее отразило бы такое длинное название: «Свойства специальных подмоноидов глобальных надмоноидов свободных моноидов с бесконечным числом образующих, решение некоторых проблем эквивалентности в этих подмоноидах и применение полученных необходимых и достаточных условий в различных задачах, исследующих нетрадиционные способы задания подклассов класса контекстно-свободных языков». Автор видит в таком название проявление связи между теорией формальных языков и алгеброй полугрупп.

Научная новизна. В работе рассматриваются различные примеры применения алгебраических свойств специальных- подмоноидов глобальных надмоноидов свободных моноидов (супермоноидов) к решению проблем эквивалентности в различных подклассах класса КС-языков. Подобных примеров применения свойств сулермоноидов в теории формальных языков автору не известно. Да и сами проблемы равенства в глобальных надмоноидах, рассматриваемые автором, ранее не исследовались.

Кроме того, в связи с двумя следующими фактами:

• бесконечности рассматриваемых в работе алфавитов;

• применении доказанных утверждений, относящихся к алгебре полугрупп, к некоторым задачам теории контекстно-свободных языков,

- в качестве примера «научной новизны» стоит отметить еле-

дующее обстоятельство. Контекстно-свободные языки определяются над конечным алфавитом, причём для каждого нетерминала имеется конечное множество правил: Однако для исследования многих конкретных КС-языков часто оказывается удобным рассматривать и специальные расширения класса контекстно-свободных языков - например, допускать языки над бесконечным алфавитом, и/или рассматривать грамматики с бесконечным числом правил. 1 Таким образом, можно считать, что автором исследовано специальное расширение класса КС-языков: определён класс простых скобочных языков, исследована проблема эквивалентности в нём (сводящаяся к одной из описанных выше проблем эквивалентности в глобальном надмоноиде свободного моноида с бесконечным числом образующих), а также показана возможность применения полученных результатов в других задачах.

Практическое применение. Диссертация формулирует темы для дальнейших научных работ на стыке теории формальных языков, алгебры полугрупп и информатики; вот некоторые из таких тем:

• специальные алгоритмы минимизации конечных автоматов;

• применение конечных автоматов для исследования проблем эквивалентности в различных подклассах класса контекстно-свободных языков;

• описание образующих элементов специальных подмонои-дов глобальных надмоноидов свободных моноидов (с конечным или бесконечным числом образующих);

• формулировка достаточных условий возможности описания языка (или некоторой грамматической структуры)

1 Прп этом, конечно, на множества правых частей правил каждого конкретного нетерминала должны быть наложены специальные ограничения, — в противном случае подобная «грамматика* могла бы допускать произвольный язык над рассматриваемым алфавитом.

как последовательности простых скобочных языков;

• скобочные н простые скобочные языки без «префиксно-суффиксных» ограничений.

Все эти темы связаны с соответствующими разделами настоящей диссертации.

При проектировании и реализации программных систем, работающих с конечными автоматами, могут быть полезными варианты алгоритмов их эквивалентного преобразования, приведённые в диссертационной работе (см. подробнее ниже, раздел «Содержание работы»).

Кроме того, в системах автоматизации построения трансляторов, а также в автоматизированных системах, предназначенных для работы с естественными языками, могут найти применение результаты главы «Проблемы равенства в классе простых скобочных языков» (также см. раздел «Содержание работы»). Такие работы в настоящее время также ведутся в Ульяновском университете под руководством автора данной диссертации (работы были поддержаны грантом фонда «Университеты России»).

Структура и объём диссертационной работы. Диссертация состоит из введения, двух частей (подразделяющихся на 10 глав), заключения, трёх приложений, предметного указателя и списка литературы, включающего 90 названий. Общий объём диссертации - 240 машинописных страниц.

Содержание работы

Автор надеется, что практически весь приведённый в диссертации материал удовлетворяет требованиям, схожим со сформулированными А. Саломаа2: постановку каждой из решаемых задач (а иногда - и некоторые доказательства) можно легко объяснить человеку, не являющемуся специалистом ни в теории полугрупп, ни в теории формальных языков (а нередко - и нематематику). Итак, постановка решаемых задач обычно несложна, но в то же время рассматриваемые проблемы ранее в известных автору публикациях не исследовались.

Во введении (глава 1) обсуждаются актуальность темы и научная новизна работы. Приводится краткая характеристика задач, рассматриваемых в диссертации, а также расположение задач по главам. В виде ориентированного графа описываются связи между частями и главами диссертационной работы.

Как было сказано выше, диссертационная работа выполнена «на стыке» теории формальных языков и алгебры полугрупп. К алгебре «ближе» первая часть («Алгебраические свойства глобальных надмоноидов свободных моноидов», главы 2-6), а к теории формальных языков - вторая часть («Применение свойств глобальных надмоноидов в различных задачах теории формальных языков», главы 7-11).

В главе 2 («Простейшие свойства глобальных надмоноидов») рассматриваются наиболеее простые свойства глобальных надмоноидов свободных моноидов. 3 Последние объекты также являются моноидами. Всюду будет допускаться случай, когда исходные свободные моноиды имеют бесконечное число

2 А.Саломаа: Жемчужины теории формальных языков, М., Мир, 1986.

3 Далее иногда будем говорить просто «глобальные надмоноиды».

образующих (атомов). То есть - по терминологии теории формальных языков - будут рассматриваться языки, заданные над произвольным алфавитом - возможно, бесконечным.

В глобальных надмоноидах рассматриваются некоторые специальные проблемы равенства (т. е. задачи поиска необходимых и достаточных условий этих равенств). Среди этих проблем - исследование равенства Ат = Вп. Доказывается, например, что в случае префиксных языков это равенство равносильно наличию у множеств А и В .общего корня, определяемого обычным образом для операции конкатенации. Критерии всех рассматриваемых равенств были использованы автором в различных задачах теории формальных языков - подробнее об этой сказано в главе б, а также во всех главах второй части.

Главу 3 («¿¿-итерации языков») можно рассматривать как одно из возможных развитии кандидатской диссертации автора. 4 В ней для заданного А - конечного или бесконечного языка над конечным или бесконечным алфавитом - исследуются т.н. бесконечные итерации языков (обозначаемые А" ) - множества бесконечных слов специального вида. Приводятся ссылки на работы автора, где показано, что равенство А" = В" равносильно специальным образом определённому отношению эквивалентности языков А* и В* (ниже - отношение оо ). 5 Определяются специальные и/-языки - ш -итерации «обычных» языков. В конечном случае (т. е. в случае конечных итерируемых языков) приводятся г. н. ВТОЬ-снстемы, реализующие эти ш -итерации, а также специальные и -автоматы

4 Б.Ф.Мельников: Метод исследования бесконечных итераций слов. Диссертация ... кандидата физ.-мат. наук. -М., МГУ, ф-т ВМК, 1990.

5 Близкие - с точки зрения автора настоящей работы - вопросы рассматривались в нескольких разных местах монографии Ж.Лаллемава «Полугруппы и комбинаторные приложения» (М., Мир, 1985). Например, в главе 5 указанной монографии были приведены условия совпадения двух яодмоноидов свободного моноида.

- расширение конечных автоматов. Формулируется задача определения критериев равенства двух ш-итераций (равенства А~° = Ви). Приводятся простейшие свойства отношения ос . Более сложные его свойства будут исследованы далее, в главе 4, а применяться эти свойства будут во всей оставшейся части диссертации. Приводится альтернативный алгоритм проверки равенства Аа = Вы в конечном случае, использующий «обычные» конечные автоматы.

В главе 4 («Итерации языков») продолжается исследование языков вида А*. Приводятся свойства бинарного отношения оо , более сложные, чем были рассмотрены в главе 3. Доказывается основная теорема 1 (см. ниже), для формулировки которой в настоящем реферате необходимо строго определить следующие понятия.

Определение. Для произвольного алфавита Д рассмотрим следующее рекуррентное определение множества максимальных префиксных кодов над Д (ниже - тр(Д)).

• Считаем, что Д 6 гпр (Д).

• Для произвольных С 6 тр (Л) и В С. С полагаем

(С\В) и В А € тр (Д).

Определение. Условие префнксности языка А будем обозначать Рг (А), условие суффиксности - Би (Л). Язык рге^ы) - множество всех префиксов слова и (аналогично -для языков).

Если множество И таково, что для некоторого

С € тр (Д)

выполнено включение С С В, то будем писать

п е тр+(Д).

Если для некоторого языка А £ £ выполнено условие

С е тр (&А) ( или £> 6 тр + (ДЛ) ),

то для языков

С' = Ь,а{С) ( соответственно, = /гд(2?) ),

будем писать

С'€тр(А) (соответственно, £)'€тр+(А) ).

Важно отметить, что в случае А = £ (при этом можно считать. что £ = Д 4) недоразумения не возникает: два разных определения, имеющиеся в этом случае для множества языков тр (Д), в действительности равносильны, т.е. определяют одни и те же множества; то же самое - для тр+ (Д).

После введённых определений приведём формулировку основной теоремы 1. Отметим ещё раз, что все рассматриваемые алфавиты и языки над ними могут быть бесконечными.

Основная теорема 1. Пусть для некоторых языков А и В выполнено условие А* оо В*, и при этом язык А является префиксным. Тогда существует префиксный язык О, такой что' А* со £>*, причём А €тр(£>) и В €тр+(£>).6 '

Доказанные в этой теореме критерии равенства двух и>-итерашш многократно используются во второй части диссертации. Кроме того, приводится формулировка аналогичных критериев'для неограниченного «префиксного» случая, а также краткое описание построенного на основе данных критериев алгоритма проверки равенства двух ш-итераций в «конечном» случае.

6 Или в эквивалентной формулировке: для некоторого инверсного мор-фпзма Лр1 , являющегося кодом О ,

Э кЪ1(А), НЪ1(В) €тр + (Дв),

причём € тр(Дв).

Отметим, что условие А 6 тр(1>), более жёсткое, -чем Л Е тр+ (.0), следует из префиксности А.

Глава 5 («Проблемы-коммутирования в глобальных надмо-ноидах») - попытка обобщения несложного утверждения об условиях коммутирования слов на случай языков. До конца рассматриваемая проблема не решена - т.е. в общем случае удобных для использования в других задачах необходимых и достаточных условий этого равенства не получено 7, и ещё не решенные задачи сформулированы в виде гипотез. В главе 5 приведены полученные необходимые условия, а в префиксном случае - необходимые и достаточные, которые далее (глава 9) применены при решении проблемы равенства в подклассе класса простых скобочных языков. Автор надеется, что эти же критерии могут быть применены и в других задачах теории формальных языков.

Итак, в главе 5 рассматривается равенство

А ■ В = В ■ А

на множествах языков (т.е. - в глобальных надмоноидах свободных моноидов). Отметим, что рассматриваемые множества А п В могут содержать е. Доказаны следующие утверждения.

Теорема. Пусть для некоторых языков А и В выполнено условие АВ = В А. Тогда А* оо В*.

В частных случаях получены более сильные утверждения.

Теорема. Если АВ = В А, причём Л и В префиксны, то

(3с е б*, к, I е м0) (А = ск,в = с').

Теорема. Если А = £ = {0,1} и АВ = В А, то

В=иЕ'-

для некоторого Г С N0.

7 Такими «удобными для использования» можно считать, например, необходимые и достаточные условия для равенства А" = В"' (основная теорема 1), а также для равенств, рассматриваемых далее в глазе 9.

При этом в формулировке последнего утверждения множество индексов i С Nq может быть и бесконечным.

В главе 6 («Специальные подмоноиды глобальных надмоно-идов свободных моноидов») приведены формулировки некоторых фактов, доказанных в предыдущих главах (в основном -2 и 5) с точки зрения алгебры полугрупп. Также рассматриваются развития этих фактов.

В первом разделе этой главы рассмотрены некоторые общие свойства глобальных надмоноидов, а также кратко охарактеризованы задачи, возникающие в его подмоноидах.

Далее сформулировано 4 вида ограничений на языки (элементы глобальных надмоноидов): ограниченности, префикс-ности и полноты (нредполноты).

Определение. Если язык L обладает следующим свойством:

(ЗА- G N) (Vu е L) (|и| < к) ,

то он называется ограниченным.

Если язык L обладает следующим свойством:

(Vq- € S>") (Эи eL) (и £ pref (а)) ,

то он называется полным. 8

Если язык L обладает следующим свойством:

(v«6Sa) ((L Л pref (а) ф 0) или (а € adh (L))) ,

то он называется пред полным.

Как и для полных языков, прп |Ej = 1 любой непустой язык является предполным. Непосредственно из приведённых определений следует, что полные языки являются подмножеством множества предполных. При этом (в случае более чем одно буквенного исходного алфавита) данное подмножество -собственное.

8 Другими словами: (Vor S Хш) (in pref (а) ф 0).

Теорема. Если А и В - полные языки, то АВ - также полный язык. Если А и В - предполные языки, то А В -также предполный язык.

Таким образом, что для каждого глобального надмоноида при этом образуется 11 его собственных подмоноидов. Однако некоторые из них попарно совпадают. Для исследования данных подмоноидов в диссертации-доказаны следующие утверждения.

Теорема. Пусть исходный алфавит состоит из 1 буквы. Тогда у глобального надмоноида имеется 2 различных собственных подмоноида- префиксный и ограниченный.

Теорема. Любой ограниченный предполный язык является полным. Любой префиксный полный язык над конечным алфавитом является ограниченным. Над бесконечным алфавитом существует префиксный полный язык, не являющийся ограниченным.

Из последней теоремы вытекают две следующие.

Теорема. Пусть исходный алфавит состоит из конечного числа букв, но более, чем из одной. Тогда у глобального надмоноида имеется 9 различных собственных подмоноидов.

Теорема. Пусть исходный алфавит состоит из счётного числа букв. Тогда у глобального надмоноида имеется 10 различных собственных подмоноидов.

Опишем все несовпадающие подионоиды. При описании они будут упорядочены по общему количеству наложенных ограничений (от 0 до 3). Всюду ниже будут опускаться слова «не входит ни в один подмоноид рассматриваемого моноида»,

Q

относящиеся к приводимым примерам языков. Подмоноид без ограничений

1. Собственно глобальный надмоноид. Язык задаётся регулярным выражением а*.

9 Определение обобщённых регулярных выражений согласовано со следующей монографией: D. Perrin : Finite Automata, Handbook of Theoret. Comput. Sci Elsevier Sci.Publ., 1990.

Подмоноиды с одним ограничением

2. Ограниченный иадмоноид. Язык {а,аа}.

3. Префиксный надмоноид. Язык задаётся обобщённым регулярным выражением а+Ь.

4■ Предполный падмоноид. Язык задаётся обобщённым регулярным выражением Ь*.

5. Полный надмоноид. Полный язык Е*. Подмоноиды с двумя ограничениями

6. Ограниченный префиксный надмоноид. Язык {а, Ъа}.

7. Ограниченный полный надмоноид. Язык {е, а} .

8. Префиксный предполный надмоноид. Язык задаётся регулярным выражением а*Ъ.

9. Префиксный полный надмоноид (не совпадает с ограниченным префиксным полным только в случае бесконечного числа атомов исходного свободного моноида). Пример необходимого языка приведён в тексте диссертации.

Подмонопд с тремя ограничениями

10. Ограниченный префиксный полный надмоноид. У этого моноида нет подмоноидов, определённых выше, и пример языка ({а,6}) нужен для того, чтобы показать, что множество его атомов непусто.

Теорема. Среди описанных подмоноидов глобального надмоноида свободными моноидами являются все префиксные надмоноиды, причём только они.

В заключительных разделах главы 6:

• определяются мощности множеств атомов подмоноидов в случае, когда число элементов исходного свободного моноида конечно;

• приведены ссылки на другие главы данной диссертации, а также на работы автора, в которых фактически рассматриваются многие из этих подмоноидов;

• а также приведены формулировки ещё не решённых проблем, связанных с рассматриваемыми в данной главе вопросами.

Как было сказано ранее, вторая часть диссертации называется «Применение свойств глобальных надмоноидов в различных задачах теории формальных языков».

Краткое содержание главы 7 («Ещё раз о конечных автоматах») следующее. В начале главы приведено специальное доказательство теоремы Клини, которое будет дважды использовано в дальнейших главах (для алгоритма специального объединения двух состояний недетерминированного конечного атомата, а также для описания связи множества регулярных языков и специального подкласса класса последователь-ностных языков). Далее приведены определения и доказаны некоторые свойства т. н. «функций разметки» состояний автомата (представляющих собой отображения состояний автомата в множества состояний эквивалентного канонического автомата, а также канонического к зеркальному). Эти функции будут использованы, например, при доказательстве корректности алгоритма объединения состояний недетерминированного конечного автомата. 10

Кроме этого, в приложении Б приведён «алгебраический» подход к известным алгоритмам теории конечных автоматов (НРС-автоматов): процедуре детерминизации, процедуре построения канонического конечного автомата, а также простое доказательство единственности последнего. 11

10 Этого алгоритма нет ни в одной из известных автору публикаций, посвященных конечным автоматам и их эквивалентным преобразованиям. В частности - в подробных моногафиях В. Брауэра «Введение в теорию конечных автоматов» (М., Радио и связь, 1987), а также II.Н.Иванова, Г.И.Михайлова, В.В.Руднева, и А.А.Таля «Конечные автоматы: эквивалентность и поведение» (М., Наука, 1984).

11 Автору неизвестны другие публикации на русском языке этих несложных ал-

Для дальнейшего изложения необходимы следующие определения. Будем рассматривать множества пар слов («скобок») над алфавитом Е. Эти множества будут обозначаться ¡1, иногда с нижними индексами. Всегда будем допускать случаи бесконечных множеств Е и ц. 12

Будем использовать следующие обозначения:

= { u ! (3«) (u,v)€ fJ.} , a(ji, v) = { и I (u, v) £ ц } ,

ß(fi) = { v I (Эи) (u, г.) € /л} , ß{fi,u) = {i;|(u,u) £ /1} .

Если Pr(a(/ü)) и Su(/3(/x)). то будем писать PrSu (fi).

горитмов, обладающие одновременно следующими двумя качествами: во-первых - достаточной степенью детализации, и во-вторых - простотой реализации.

Например, подробные алгоритмы из двух монографий, упомянутых в предыдущей сноске, тяжелы для практической реализация. Аналогично, по мнению самих авторов монографии А. Ахо и Дж. Ульмана «Теория синтаксического анализа, перевода и компиляции» (М., Мир, 1978), оба алгоритма построения канонического конечного автомата (алгоритмы 2.2 и 2.6) сформулированы неудачно. Эти неточности впоследствии были исправлены в монографии «Compilers: Principles, Techniques and Tools» (N.J., Addison-Wesley, 1985) этих же авторов (совместно с R.Sethi). Однако, во-первых, последняя монография на русский язык пс переведена, а во-вторых, автор настоящей диссертации непосредственно в процессе практического программирования убедился, что приведённый в приложении Б алгоритм построения канонического конечного автомата более удобен для реализации.

Например, для построения канонического конечного автомата в приложении Б настоящей диссертации строится только два бинарных отношения. А при реализации «стандартных» алгоритмов необходимо построение Лг —1 бинарного отношения (где Лг - число состояний рассматриваемого детермипированного автомата).

Кроме того, в упомянутой монографии А. Ахо и Дж.-Ульмана вместо доказательства единственности канонического конечного автомата (т.е. того факта, что канонический автомат является инвариантом регулярного языка) приведено лишь доказательство того, что все приведённые конечные автоматы, определяющие некоторый заданный регулярный язык, имеют одинаковое число состояний.

12 С точки зрения определяемых далее языков, такое допущение представляет собой выход за границы класса КС-языков, определявшихся для конечного множества правил, - и, следовательно, обязательно для конечного алфавита. Но все определения (грамматики, её языка, вывода и др.) при этом естественным образом переносятся па бесконечный случай.

Будем далее рассматривать языки, следующим образом определяемые через множества ц.

Для произвольного языка L положим

*°(/i,L) = L и ¥+1{fx,L) = {uV(n,L)v\(u,v) е ц] для каждого j > 0. Далее,

**(ß,L) = и *''(/*>£). = U «"'(/*,£)■

з>о i>1

Определённые таким образом множества слов L) называются простыми скобочными языками. Заметим, что в случае конечных множеств ц и L легко указать определяющую язык L) последовательностную КС-грамматику.

Для некоторых множеств L и (i рекуррентно определим скобочный язык, который будет далее обозначаться

[я,*]*,

с помощью следующих трёх правил:

• если u € L, то u € {fi,L]";

• если (u,v) & fi и w £ X, то uwv G [/i, L]*;

• если u 6 [ /¿,£]* mi £ [(I, L]*, то ut; G [¿¿,L]*.

Скобочные и простые скобочные языки, рассматриваемые е главах 8 и 9, очень важны для изучения всего класса КС-языков. 13 В главе 8 («Проблема равенства в классе скобочных

13 Например, см. в статье Е. Шамира (Е. Shamir: A Representation Theorem for Algebraic and Context-Free Power Series in Noncom muting Variables, Information and Control, 11 (1967) 239-254) теорему о возможности получения произвольного КС-языка применением специальных морфизмоз к языку, задаваемому приведённой далее грамматикой специального вида.

Отметим ещё, что оба эти множества языков не являются замкнутыми относительно операции объединения, - поэтому (согласно некоторым классификациям) не являются классами языков.

языков») приведены общие свойства скобочных и простых скобочных языков. Далее для однозначных скобочных языков при L = {е} (см. в тексте диссертации более подробное описание ограничений) вводятся обозначения

[/z]1 = -J uwv | (и, v) 6 и, w е [у"]*}, а для всех г > 2,

ЫМИМ/^

и рассматривается проблема равенства

Доказана теорема, что последнее равенство эквивалентно следующему, значительно более удобному для исследования в частных случаях:

• ым^]1.

Доказаны такие следствия последней теоремы.

• Для каждого г 6 N выполнено равенство = [^2]' ■

• Существует язык L £ £*, такой что

(«ЫГ « (а(^))% mrify « ((РЫ)НУ-

• Пусть Рг(а(//х)). Тогда существует префиксный язык А, такой что

а(т) € шр (Л), а(/л2) Е тр+(А).

• Пусть Su(/?(/ui)). Тогда существует префиксный язык В , такой что

С%1))Летр (В), №))л6тр(В).

В заключении главы 8 сформулированы проблемы для дальнейшего исследования скобочных языков.

Главу 9 («Проблемы равенства в классе простых скобочных языков») можно рассматривать как второе возможное развитие кандидатской диссертации автора. В этой главе исследуются проблемы равенства для двух простых скобочных языков при специальных ограничениях. Получены необходимые и достаточные условия равенства языков такого вида.

Рассматривая два множества (возможно, бесконечных) пар слов ц\ и /1-2, будем применять следующие обозначения. Употребление нижнего индекса г для некоторого множества, а также - для некоторого равенства (утверждения), будет далее означать, что мы в действительности рассматриваем два множества - для ¿€{1,2}. (Или, соответственно, что данное равенство выполняется для обоях индексов г; в этом случае получаются ровно два равенства - в одном каждое вхождение i заменяется на 1, а в другом - на 2.)

Для некоторого языка X будем писать

аналогично - для языков , а также Ф; для произвольного У € N. Положим

а.-(г') = ;

аналогично определяются а;, Д и Д(и).

Если некоторое множество (язык или множество пар слов) - одно и то же для обоих нижних индексов г Е {1,2}, то мы иногда будем записывать это множество без этих индексов. Например, если мы уже доказали, что Ф} = , то мы можем обозначать это множество Ф1.

Итак, для некоторых, возможно, бесконечных, языка Ь и множеств пар слов щ и /.¿а рассмотрим равенство

Ф* = Ф£

со следующими ограничениями:

Рг8и(Ь), Ргви (/г,-), IП Ф+ = ф ,

= 11 Ф1 = Ф2 ■

Доказана следующая теорема.

Основная теорема 2. При сформулированных выше ограничениях равенство

выполняется в том и только том случае, когда выполнено одно из следующих двух условий:

• для некоторых языков С и С, таких что СЬ — ЬС, и для некоторых чисел к\, к-2, 1ч > 0, таких что

к\ + 1х = к? +- 1-2,

выполняются равенства

^ = х С*' , /х2 = С*' х С'». .

Эта теорема формулирует общий случай, а её частные случаи представляют собой описания подмножеств множества КС-языков с разрешимой проблемой эквивалентности. Например, если множества Ь и конечные, то равенства

т = сх с'', /¿2 = сК- х ск-

могут быть проверены непосредственно. А если |Х| — 1, то выполняется такое следствие.

Теорема. Пусть РгЭи (//;). Тогда равенство

выполняется тогда и только тогда, когда выполнено одно из следующих двух условий:

• /¿1 = (¿2;

• для некоторого слова г и языков С и С, таких что С г — гС, и некоторых чисел Ь > 0, таких что ¿1-1-/1 =

к'1 + /2 • выполняются равенства

В заключении главы 9 сформулированы проблемы для дальнейшего исследования простых скобочных языков.

В главе 10 («Класс последовательностных языков, проблема равенства в нём и смежные вопросы») рассматриваются т.н. последовательностные контекстно-свободные языки и грамматики. Они не исследовались ни в одной из монографий, известных автору настоящей диссертации и рецензентам его работ.

Основная причина включения данной главы в настоящую диссертацию - возможность представления языка РЬ/014 в виде конечной последовательности простых скобочных языков. (Эти результаты приведены далее в главах 10 и 11.) Кроме того, при исследовании всего класса этих языков в качестве «побочных» результатов получены несколько теорем о его структуре, классификация его подклассов, а также показано, что предложенное в главе 7 неканоническое доказательство теоремы Клнни показывает, среди прочего, совпадение класса регулярных языков с одним из подобных подклассов.

Структура главы 10 следующая. После основных определений показывается, что всё множество последовательностных языков замкнуто относительно объединения, итерации и мор-

14 См. монографию Н.Вирта оАлгоритмы, + структуры данных = программы) (М., Мир, 1986). Грамматика языка РЬ/0 очень проста, однако он включает практически все возможности реальных »необъектных» языков программирования. Как известно автору, язык РЬ/О часто используется в ВУЗовскцх курсах - например, для написания «учебных» трансляторов.

физма, но не замкнуто относительно пересечения с регулярными языками. Предложена классификация подклассов класса последовательностных грамматик и языков с точки зрения естественно выбранного критерия 15 - максимального числа вхождений нетерминала в правую часть «своего» правила. Исследованы свойства замкнутости этих подклассов. Кроме того, показано, что предложенная классификация корректна, т.е. каждый из бесконечного числа получающихся подклассов класса последовательностных грамматик (языков) является собственным подмножеством следующего подкласса. Далее доказываются необходимые условия равенства двух последовательностных языков. А в заключении главы 10 приведены обстоятельства, в связи с которыми необходимо (по мнению автора) продолжать исследование всего класса последовательностных языков. Важнейшее из этих обстоятельств - существование языка РЬ/0, т. е. существование «реальных» КС-языков, языков программирования, которые могут быть преобразованы в последовательностную форму.

В главе 11 («Простые скобочные и последовательностные языки как грамматические структуры в языках программирования») рассмотрены примеры применения доказанных выше фактов для конкретных грамматических структур в языках программирования. Например, приведена сложная рекурсивная конструкция Паскаля - <задание комбинированного типа? - как простой скобочный язык; при этом все ограничения, наложенные в главе 9, выполняются.

Итак, возможно простейшее определение данной граммати-

15 Естественным этот критерий является именно для последовательностных языков.

ческой структуры16:

«задание комбинированного хипа>

record «список полеи> end. «список иолей> ::=

«секция записи> -С ; «секция эаписи> } «секция за.писи> : : =

<имя поля> { , <имя поля> } : <тип>

При этом одна из возможностей для конструкции <тип> (т. е. одна из правых частей <гип>-правпл) есть именно <задание комбинированного типа>.

Для дальнейшего определим

<имена полей> ::= «имя пояя> ■{ , «имя поля> }

Теперь правило для нетерминала <секция эаписи> может быть переписано следующим образом:

<секция записи> ::= «имена полей> : <тип>

Приведённое рекуррентное определение для нетерминала «задание комбинированного типа> есть ЯЗЫК Ф*(/г, Ь), где Ь - язык, соответствующий грамматической структуре <тип>, но полученный без правил для нетерминала «задание

16 Применяем следующие соглашения:

• фигурные скобки употребляются для обозначения итерации языка;

• шрифтом, имитирующем пишущую калинку, набраны терминалы языка, а обычным «формульным» шрифтом в формулах набраны метасимволы;

• в формулах, заданиющих языки и множества пар слов, и тем более - в правилах грамматик, иногда опускаем знаки препинания (относящиеся к фразам данной диссертации), т.к. их легко перепутать с терминалами описываемых языков.

комбинированного типа>, а ц - бесконечное множество пар слов, задаваемое в виде

fi =Ах В,

где

А ~ | record UV : | U есть{<секция эаписи>;}, V есть «имена полей> J ,

В = | и end j U есть{;«секция записи>} | .

Однако при таком способе задания не выполняются требования префиксности и суффиксности некоторых языков (например, не выполнены условия. Pr (L) и Рг (а(//))).

Несмотря на это, мы всё же можем удовлетворить требованиям, наложенным в главе 9. Для этого зададим язык, соответствующий рассмотренной выше конструкции «задание комбинированного типа>, как

га nd

при'

L = { cord V, е | U есть «список полей> }, и опять же

fi — Ах В,

где

А = j cord UV : re U есть{«секция записи);},

V есть «имена полеи> В = | пй и в | и есть {; «секция залиси>}

При таком способе задания множество а(ц) префиксно (поскольку каждое слово из а(^г) оканчивается на ге), аналогично, р(/л) суффиксно, а Ь - префиксно и суффиксно.

Далее в главе 11 приведена последовательностная грамматика 2-го порядка, задающая язык программирования PL/0. После этого приведена запись этого же языка в виде конечной последовательности

Lq, LI, ... , Ln, где для каждого i £l,n выполнено равенство

Приведём краткую запись этой последовательности (подробнее см. в тексте диссертационной работы). Обозначения нетерминалов: Р - программа (стартовый нетерминал); Б - блок;

DPP - раздел процедур;

dcc - раздел констант;

DC - определение константы;

dnn — раздел переменных;

S и S' — оператор;

ss - последовательность операторов;

с - условие;

Е - арифметическое выражение; I - идентификатор; N - число;

temp - вспомогательный нетерминал.

Последовательностная грамматика включает следующие правила (для идентификатора и числа правила опущены):

Р

в

DPP DCC DC

= в' .

= const DCC ; var DNN ; DPP S

= procedure I ; const DCC ; var DNN ; DPP S ; DPP

DC TEMP

DC , DCC I ■ N

= if С then TEMP = while С do TEMP

dun s

= I

= I , DM = I := E = call I = if C then S = while C do S = begin SS end = S'

= S' ; SS = TEMP S' = TEMP S' ; SS = begin SS end = begin SS end ; SS = TEMP begin SS end = TEMP begin SS end

SS

I := E call I if С then S' while С do S' odd E E = E E < E E <= E + E

При этом нетермината упорядочены в том порядке, в котором указаны правила, т.е.

Последовательность языков записывается следующим обра-

зом:

odpp = ¿(tempi) /?е1,р = lm? = {е} Q'dcc = £(DC) , /?DC0 = {e} Lncc = £(DC)

<*dkn = , /3DfIN = {fi} I'd nn = £(l)

qs = £(tenp2) д = {e} Ls = £(темрз) hss = £(temp4) x {e} U £(темрб) x £(temp6) , «temp = £(TEMP2) /?temp = £(temp) = {e} as. = £(temp2) [3s, = {e} Lb- = £(темрэ) = £(tempio) x {e} U {(} x {)}, Lz = £(i) U £(м).

= procedure I ; const DCC ; var DNN ; DPP S ; » if C then = while C do ■ I E - call I = begin SS end = TEMP7 S' TEMP8

= TEMP7 begin

= end = end ; SS

= TEMP

= i := e

= call I = +

= E + = E -= E * = E /

А в заключении главы 11 перечислены обстоятельства, в связи с которыми в системах автоматизации построения трансляторов может найти применение представление некоторого языка программирования последовательностью простых скобочных языков. Вот наиболее важные из них.

• Грамматические конструкции, подобные приведённым в настоящей работе для языка PL/0 и конструкциям Паскаля «условный оператор> и «задание комбинированного типа>, встречаются во всех «реальных» языках программирования. Более того, автор даже считает, что все

TEMPI ТЕМР2

ТЕМРЗ

ТЕМР4 ТЕМР5 ТЕМР6 ТЕМР6 ТЕМР7 ТЕМР7 ТЕНР8 ГЕМР8 ГЕМР9

TEMP 10

грамматические конструкции всех известных ему языков программирования могут быть описаны с помощью теории, приведённой в главах 9-11.

• В системах автоматизации построения трансляторов должны оказаться полезными не обязательно необходимые и достаточные условия равенства двух грамматических конструкций (последовательностньгх и / или простых скобочных языков), но п только необходимые условия (для отрицательного ответа на вопрос'о предполагаемом равенстве двух грамматических конструкций). А некоторые необходимые условия равенства последовательност-ных языков и были рассмотрены в данной главе.

В заключении диссертации (глава 12) сформулированы основные результаты, диссертации, приведён список конференций и семинаров, на которых они доклаывались (см. ниже). Кроме того, собраны (ещё) не решённые задачи, упоминавшиеся в предыдущих главах диссертации. Они сформулированы или.как вопросы, или как гипотезы. Над большинством из них в настоящее время работают аспиранты.

Как было отмечено выше, диссертация включает 3 приложения. Приложение А - «Алгоритм проверки условия А* оо В* »-можно рассматривать как ещё одно (третье) возможное развитие кандидатской диссертации автора. О содержании приложения Б - «"Алгебраические" формулировки некоторых алгоритмов эквивалентного преобразования конечных автоматов»

- было сказано выше. Содержание приложения В - «Ещё одна грамматическая структура как простой скобочный язык»

- схоже с одним из примеров главы 11.

Основные результаты диссертации

Основные результаты диссертации состоят в следующем:

• Исследованы алгебраические свойства глобальных надмоноидов свободных моноидов, а именно:

- предложен метод исследования бесконечных итераций языков (в том числе - бесконечных языков): показано, например, что равенство Аш- = В" в случае префиксных языков А и В равносильно существованию специального инверсного морфизма, отображающего А и В в максимальные префисные коды;

- полученные результаты применены для исследования специальных проблем равенства в глобальном надмоноиде свободного моноида (среди них -

А-В = В-А, Ат-Ь=Ь-Вп

и др.); получены необходимые (а в ряде случаев - и достаточные) условия исследуемых равенств;

- предложена классификация специальных подмо-ноидов глобального надмоноида свободного моноида, исследованы алгебраические свойства этих подмоноидов.

• Указанные свойства глобальных надмоноидов применены в различных задачах теории формальных языков. А именно, получены необходимые (а в некоторых частных случаях - и достаточные) условия равенства двух языков в следующих подклассах класса контекстно-свободных языков:

— классе скобочных языков;

— классе простых скобочных языков - при этом допускаются бесконечный алфавит и бесконечное (счётное) число пар скобок;

— классе последовательностных языков.

Первые два из этих подклассов также были определены и исследованы автором.

Показана возможность применения полученных необходимых и достаточных условий равенства двух простых скобочных языков, полученных в случае бесконечного числа скобок над конечным алфавитом, для определения необходимых и достаточных условий равенства специальных контекстно-свободных языков - языков некоторых грамматических структур, имеющихся в языках программирования. Это даёт возможность применить полученные- результаты для проверки эквивалентности различных грамматических структур в системах автоматизации построения трансляторов.

В качестве «сопутствующих» получены следующие результаты для классов регулярных и последовательностных языков:

— дано ещё одно описание класса регулярных языков - как специального подкласса класса последовательностных языков;

— предложен новый алгоритм объединения двух состояний (недетерминированного) конечного автомата;

— предложена классификация последовательностных языков и исследованы свойства описанных подклассов.

Публикации. Результаты диссертации опубликованы автором в 14 научных работах. Основные из них:

• Некоторые следствия условна эквивалентности однозначных скобочных грамматик. - Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка, 3 (1991) 51-53.

• The Equality Condition for Infinite Catenations of Two Sets of Finite Words. - Int. J. of Found, of Сотр. Sel, 4 3 (1993) 267-274.

в Об одной классификации последовательностных контекстно-свободных языков и грамматик. - Вестник Моск. ун-та, сер. Вычисл. матем. и ки,б-ка, 3 (1993) 64-69.

• Некоторые проблемы равенства в глобальном надмоноиде свободного моноида. - Б кн.: Фундаментальные проблемы математики и механики (Программа «Университеты России»), М., Изд-во Моск. ун-та, 1994, 304-305.

• Подклассы класса контекстно-свободных языков (монография, 175 е.), М., Изд-во Моск. ун-та, 1995.

• Some Equivalence Problems for Free Monoids and for Subclasses of the CF-Grammars Class. - В кн.: Number theoretic and algebraic methods in computer science, World Sci. Publ., 1995, 125-137.

• Об одном расширении класса контекстно-свободных языков. - Программирование (РАН) 6 (1995) 46-58.

• Алгоритм проверки равенства бесконечных итераций конечных языков. - Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка, 4 (1996) 49-54.

Апробация работы. Изложенные в работе результаты докладывались автором:

• на Московском городском семинаре по автоматизации программирования (апрель 1992 г. и май 1996 г.);

• на научном семинаре кафедры Алгебро-геометрических вычислений Ульяновского филиала МГУ (декабрь 1992 г. и февраль 1994 г.);

• на Международной конференции «Теоретико-числовые и алгебраические методы в компьютерных науках» (июнь-июль 1993 г.);

• на научном семинаре «Алгебра и ее приложения» кафедры Высшей алгебры МГУ (октябрь 1993 г. и март 1994 г.);

• на научном семинаре кафедры Математической теории интеллектуальных систем МГУ (март 1994 г. и май 1994 г.);

• на XI Международной конференции по проблемам теоретической кибернетики (июнь 1996 г.);

• научно-техническом совете факультета Информационных технологий и систем Ульяновского государственного по- | литехнического университета (июнь 1996 г.);

• на региональной конференции «Современные проблемы математики и механики» (Ульяновск, сентябрь 1996 г.),

• на научном семинаре кафедры Теоретических основ информатики Саратовского государственного университета (октябрь 1997 г.),

а также постоянно - на научных семинарах кафедры Математической кибернетики и информатики Ульяновского государственного университета (до января 1996 г. - Ульяновский филиал МГУ).

Подписано в печать 07.10.97. Формат 84x108/32. Усл. печ. л. 2. Тираж 100 экз.

Заказ №120/

Отпечатано с оригинал-макета в лаборатории оперативной полиграфии Ульяновского государственного университета 432700, г.Ульяновск, ул.Л.Толстого, 42