Полугрупповые представления контекстно-свободных языков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

) 6 9 2

КИЕВСКИЙ УНИВЕРСИТЕТ ИМЕНИ ТАРАСЛ ШЕВЧЕНКО

На правах рукописи

ЙОРДЕЕВ Красимир Яшсов

ШШШШОШВ ПРЕДСТАВЛЕНИЯ КОНТЕКСТНО-СЮБОДНЫХ ЯЗЫКОВ

Специальноегь 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

К я о в - I 9 9 2 г,

Работа выполнена ка кафедре математической информатики Киевского университета им. Тараса Шевченко.

Научный руководитель; доктор физико-математических наук

профессор АНИСИМОВ A.B.

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

ЦЕЙТЛИН Г.Е.

кавдидат физико-математических нау ШЕВЧЕНКО В.П.

Ведущая организация: институт кибернетики АН Укравни

им. В.М.Глушова

Защита состоится " ^Lf" 1992 г. в_час

на заседании специализированного совета Д 068.18.16 в Киввоком университете имени Тараса Шевченко ло адресу:

Кйвв-127, пр. Глушкова 6, факультет кибернетики.

О диссертацией можно ознакомиться в библиотеке Киевского университета.

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

Ученый секретарь ,

специализированного совета

кандидат физ.-мат. наук ИЗЬШН А,В-

Sí''

" I

ЗОЯМ X ¡VP AKT KF11С ТИКА РАБОТЫ

Актуальность. Известно огромное значение теории кою'-зкстно-збодних языков для современного развития информатики. На ocie результатов в этой области разработано много практических сложений, которие с основанием модно утоерждать, являются од-Í из причин для быстрого темпа развития вычислительной тех-ки и программирования.

Имеются разине подхол" /ри изучении свойства контекстно-' ободных языков и один из ¡'их - это применение теории полутрупп, от аппарат используется и в диссертации для решения конкрет-х задач.

Как известно, алгоритмы, работающие за полиномиальное время ляются одними из лучших ачгоритмов. В 1981 г. Ц, Siems и И uní , 19У6 Г. A. Weéer И Н. Seidle ИВ 89 г. ]!/. Ки.сй нашли полином/.лтьные алгоритмы для провер-одноэначности конечных автоматов. А.В.Анисимов в 1981 г. казал, что проверка однозначности конечно-автоматных отобраяе-й является следствием задачи о проверке включения контекотно-ободчых языков в групповие языки группы с разрешимой проблемой юенства слов и показал соответствующий алгоритм решающий эту дачу. Как описан этот алгоритм не следует, что он полиномиальный. 1ким образом возникает вопрос о возможности модифицировать [горитм А.В.Анисимова, так, чтобы он работал за полиномиальное >емя, Одновременно о этим интерес представляют и чисто теоре-!ческие разработки, связанные с этой проблемой.

Как доказал [. Ыггвп в 1975 г. формальный язык зляется кусочно-тестируемым тогда и только тогда, когда его штаксический моноид является Í - тривиальным. Таким образом

естественно возникает вопрос когда данная полугруппа является ^ - тривиальной. В этом аспекте в работе рассмотрен клас линейно-упорядочонних периодических полугрупп.

Цели и задачи рабрта,

- Исследовать класс линейно-упорядоченных полугрупп и связи с кусочно-тестируемыми языками. Показать когда произвольная пер дическая полугруппа является линейно-упорядочиваемая и когда линейно-упорядоченная периодическая подгруппа является ^ -виальной.

- Получение новых методов описания контекстно-свободных языко

- Модифицировать алгоритм Л.В.Анисимова, так, чтобы он работа за полиномиальное время.

Методы исследования. Гри роыении поставленных задач иена, зовался аппарат теории полугрупп, теории графов, теории замки; тих полуколец, теории матриц, теории контекстно-свободных язи и теории автоматов.

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

Апробация работы. Основные результата работы докладывали! на международной конференции по теории полугрупп (г.Сегед, Вш грия, август 1987 г.), Двенадцатой научной конференции болгарских аспирантов в СССР с международным участием (Москва, июнь 1990 г.). Четырнадцатой (Солнечный берег, Болгария, апрель 1985 г.) и Двадцатой (Варна, Дружба, Болгария, апрель 1991 т.] весенних -конференций союза математиков Болгарии.

Публикации■ По теме диссертации опубликовано девять пэчат-работ.

Структура и объём ;.;1отн. диссертационная работа состоит введения, трех глав, каждая глава из трех параграфов и списка ературы. Объём работы 115 страниц. Список литература ючаег 167 наименований,

СОДЕРЖАНИЕ РАБОТЫ.

Во введении обоснована актуальность диссертационной работа, »рмулированы цвлъ и задачи диссертационной работы, приведены зая характеристика работы и основные, полученные в ней. науч-э результаты.

Первая глава имес.^ более теоретический характер. Она ло-ящеиа рассмотрению линейно-упорядоченных полугрупп и их связи кусочно-тестируемыми языками.

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

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

^^¿Aitrt " произвольное семейство подмножеств

;акое, что У И^-П а Мл Л -

■Li А #

и назови;.) у - разбиение, с ели в каждом подмножество

и б индексном множестве А нпедошш линейные порядки

СОО'ГВбТОТБОНКО И . Ь'СЛИ .X (. .М^ . ЛЛЯ

некоторого с^ £ Л , то полагаем: ЛЛ = I г * I г *х )

Л* = М„ ) и хл

Тсюрема: Группоид лштНао упорядочиваем тогда и

только тогда, когда сущпстпуо? у ~ разбиение группоида 7* . такое, что Ал/\у & А^ ялл всех *'Т

В диссертации прджшено ноша доказательство известной тио-реш Е.Я.Габовича, рошавдяч аналогичную задачу. Используя доказанное для произвольного группоида и учитывая свойства периодической полугруппы доказана следующая тооршн:

Теоузпма: Периодическая полугруппа $ с множеством идвм-ПОТ0НЮВ линейно-упорядочиваомая тогда и только тогда,

когда выполнен!! следующие условия:

а) Е"5 - линейно упорядочиваемая идемпотентная полугруппа;

б) для каждого с , класс тора и и К-е = ~{осб$13п: ос" - е } лмюйно-уиорвдоченная нильполу-

групда с пулом е ;

в) [ вместе с порядками из пунктов а) и б) является у - разбиением, такое, что А^ А у =

для всех эс , у е 5 Т?4'. как каждая конечная полугруппа периодическая, то найдены в в , диссертации необходимые и достаточные условия для линейно-упоря-дочивания периодических полугрупп в частности дают ответ и на поставлешш Б.Ы.Шайном на страницах журнала ¿ет^гоир Роги.™, !, ИЮ

вопрос: когда коночная полугруппа яяляется лшшйно-унорядочен-ной.

параграф [.3,, даот ответ на вопрос когда линейно-упорядоченная нериодичоскан полугруппа лпляогся ^--тривиальной. Пусть 5 полугруппа и а 6 е Б Полагаем а ,/ € , тогда и только тогда, когда а и С порождает один и тот жо главный дву-

сторошш!! идеал. Полугруппа 5 наливается ^ - тривпаль-

ы

ной, если отношение ^ совпадает с отношением равенства.

Далоо полагаем а ¿К £ тогда и только тогда, когда существу-

м й"

от идемпотентей натуральное число п , такие, что а - ь -е Дая каждого идешютента е класс торзии определяется

как множество Ке = [ * е 5 13 п : .¡с" - е } . Решение поставленной в параграфе задачи сформулировано в следующую теорему.

Теорема. Для лииейно-унорядочениой периодической полугруппы следующие условия эквивалентна:

( £ ) Для каждых <?,/ <=Е5 , Ке К^ & 1<г/ ( а ) 5 - полурешетка нильполугрупп; ( с <-1 ) 5 - слабо коммутативная; ( I V ) £$ - коммутативная подполугруппа;

(V ) 5 - 3 - тривиальная^ )

Как следствиедоказывается, что для линейно-упорядоченной полугруппы с конечным множеством идемпотектов существует гсоли-номиальннй алгоритм, проверяющий является ли эта полугруппа ^ - тривиальной. С помощью условий ( I V ) описан пример, доказывающий существование линейко-упорядочешшх периодических полугрупп, которые не являются ^ - тривиальными.

Глава 2 посвящена некоторым методам описания произвольной контекстно-свободной гргмыатшсв. Эти метода используются в главе 3,

С помощью параграфа 2.1. делается введение в теорию контекс нэ-свободнш: языков. Здесь дается все сведения необходимые дая работы в последующих параграфах и в главе 3. Перечисляются некоторые известные результаты в этой области.

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

нетерминальными символами отроится диаграмма переходов с 2 п

элементами,

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

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

В параграфе 2,3. рассмотрено замкнутое полукольцо .

где Ж* ' - свободный моноид над конечным алфавитом 2

г*4* _ *

¿х* состоит из всех подмножеств , включая и пусг

Операция сложения в - это объединения множеств. Если

, то АЬ = { а. 4 I иеА , -¿е Ь } .Единичны! элемент будет множество (. г 3 , содержащее только пустое слов! £ , а нулевой элемент -это пустое множество. Пусть Г контекстно-свободная грамматика в нормальной форме Хомского с множеством нетерминалов К - £ Б,, Б* , .. . , 5», } • В параграфе указаны две матрицы, которые вполне определяют язык, пораждаамш Г . Первая матрица А = ) - трехмерная» размерш

пжпг.п и состоит только с нулей и единиц, при этом

а .V - 1 тогда и только тогда, когда в Г оувдествуот

правило Б - —> 5- Б,, » иначе ее • к - О . Вторая

матрица II = (. ^ ) - двухмерная, диагональная, размер-

<2'

ности п - п с элементами из замкнутого полукольца ,

При этом г^ - I х ь 2 I существует правило в Г 5, и т - О . если с .В работе показано как о помощьв

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

Глава 3, рассматривает вопрос о включении контекотно-ово-бодных языков в групповые языки групп о разрешимой проблемой равенства слов. Зга задача тесно связана с задачей о проверка однозначности коньчно-автоматкшс отображений. Как доказал А.В.Анисимов из существования алгоритма для проверки включения контекстно-свободного языка в групповой язык следует существование алгоритма для проверки однозначности конечно-автоматных отображений.

Определение. Пусть Ь - группа с множеством образующих X = 2 и 2 = I , кг,..., х„1 х;', х1', ■. ., ос} г множеством определяющих соотношений & , единицей -е и о разрешимой проблемой равенства слов. Тогда множество олов т*(идТ' называется групповым языком, задающим группу 6 .

Параграф 3.1. служит для введения в проблему. Кроме необходимых определений цитируется результат А/В.Анисимова, который служит для основы последующих исследований.

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

К) ~

регулярных языков, заданных с помощью конечных автоматов. Ра смагччшаптся диаграмма нороходоп, которая соответствует кона пому автомату и с помощью её найдены различные конечные множ ва, каждое из которых включается в групповой язык ггх тог и только тогда, когда рассматриваемый регулярный язык включа в 7гг .Б результат*- описан полиномиальный алгоритм, про ряющий включается ли данный регулярный язик в групповой язык группы с разрешимой проблемой равенства слов.

. В параграфе 3.3. решается аналогичная задача для линсйн

I лцнййной

языкаи,заданного с помощью грамматики. Снова строится диагра

переходов, соответствующая этой грамматике и дается ещё два

ночные множества, каздов из которых включается в тп , тог

и только тогда, когда ¡_ % пх . Эти множества соображены со

свойствами линейных языков. Дается алгоритм, работающий за п

номиальиое время и проверяющий включение & гп

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, полученные в диссертационной рабо1

1. Исследована основные свойства линейно-упорядоченных периодических полугрупп в связи с кусочно-тестируемыми язикш

2. Найдены необходимые и достаточные условия для линей» упорядочивания произвольного группоида.

3. Показано новое доказательство известной теоремы Е.ЯГ.] бовича, решающая аналогичную задачу задаче из пункта 2.

4. Получены необходимые и достаточные условия для линей! упорядочивания произвольной периодической полутруппы.

5. Показаны пять условий, эквивалетных условию произвол! линейно-упорядоченной периодической полугруппы быть ^ - т] альной.

6. Произвольный контекстно-свободный язык описывается с помощью конечного ориентированного графа, все ребра которого

¡сип элементами дшшоН полугрупп».

7. Дается матричноо продсталлоиио контокогяо-оиобоцних лзн-

H. JUui произвольного регулярного нзшсн L нпНдшш дна чшн! множистиа Кг и Ws , такие, что lint , rao т

¡ПОКОЙ ЯЗИК ГруШШ С разрешимой Проблемой ]VUH>HCTjm слил,

w и только тогда, когда ]VÍ i >п , тогда и только тогда, ¡a ll/j i т

9. Мя рлгулярцого языка L показал алгоритм, работал-за цчлштмнадышо нр(:мя и провпрлодиИ пклщоино L » т

10. Как и в пункт.) ¡i poffiunmi ашишгичиш образом та лш ача для линойннх и:ткои.

11. Для линоЛного языка L и группового язика т

ican алгоритм, работавши!! за полшюмиальноп время и проворящий шчонис L í 'пс

CífilCOK ОИУШШШПШ РАЮТ.

I. Норджов К.Л., Тодоров K.I. Bipxy ликайката каредимост полугрупп от краоп род// Математика и матоматичаоко образова-

е, т.14, София: Волг. All, I9B5, 0.253-262,

'¿.Tadorov К loreIjev К. On some conditions ir íalal оrdzru-éility of aemiyroups-// Colloquium n Ser» i <j rou j3S ( Jots*/ Aiiilu. University f S te.<j&d,

187 , p- 45.

3. Йордасев К.Я. Включение некоторых классов языков в группо-ыэ яэшш// дапон. в ЦШ1ТЙ - Болгария, 1930, haíí'Oé/sa, it t.

4. йорджев К.Я. Моделирование контекстно-свободных языков

/

помощью конечных графов// депон. в ЦИЬ'ТИ - Болгария, 1990,KAJ

5. йордаев К.Я. Контекотно-свободпно языки и конечные графы// !атвматика и матем. образование» т.20, София: БАН, 1991, c.28Q--264.

6. йорджев К.Я. О включении контекстно-свободных языков

в групповые языки// Модели и системы обработки информации, вып. 10, 1991, с.21-27.

7. йорджев К.Я. Матричное представление контекстно-свободных языков// Математика и иагем. образование, т.21, София: БАН, 1992.

' 8, йорджев К.Я. Ефективкий алгоритм знаходженНя во1х сл1в обмеженою довжиною дано1 контексгяо-в1льно1 граматики// Модели в оистемн обработай информации (в печати).

9. йорджев К.Я. Линейно-упорядоченные периодические полугруппы в связи с кусочно-тестируемыми языками// Модели и системы обработки информации (в печати).

Зак. 103,тир. ЮО.Уч.тип. Киевского университета Киеа.Бупьвар Шевяе(1коД4.19Й2г»