Выразительная мощность GF(2)-грамматик тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Макаров Владислав Маратович

• Макаров Владислав Маратович
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Макаров Владислав Маратович

Предисловие

Научное признание работы

Положения, выносимые на защиту

Основные научные результаты

Глава 1 Некоторые основные свойства СГ (2) -грамматик

1.1 Понятия о СГ(2)-операциях и (;К(2)-грн.\1.м;п нкнх

1.2 СГ(2)-грамматики в нормальном виде Хомского

1.3 СГ(2)-грамматики над односимвольным алфавитом

1.4 Переход к коммутативным степенным рядам

1.5 Замкнутость относительно преобразователей

Глава 2 Задаваемые СГ(2)-грамматиками подмножества а*Ь* и а*Ь*с*

2.1 Буквенно-ограниченный нормальный вид

2.2 Подмножества а*Ь*

2.3 Применения теоремы

2.4 Подмножества а*Ь*с*

2.5 Язык { апЬпсп | п ^ 0 } и его друзья

2.6 Другие применения

2.7 Верны ли обратные утверждения?

2.8 Структура кольца на С(а,Ь)

Глава 3 Более тонкая характеризация для к ^

3.1 Общая верхняя оценка для подмножеств а* а* ...а*к

3.2 Нижняя оценка

3.3 Общие ограниченные языки

Глава 4 Заключение

Литература

Введение диссертации (часть автореферата) на тему «Выразительная мощность GF(2)-грамматик»

Введение

Предисловие

Формальным языком называют множество из некоторых строк конечной длины над каким-то конечным алфавитом. Теория формальных языков — область теоретической информатики, изучающая формальные языки и задающие их описательные модели. Описательные модели для формальных языков бывают разные: конечные автоматы, регулярные выражения, магазинные автоматы, формальные грамматики и многие другие. Большинство из них явно или неявно определены в терминах классических операций над формальными языками: объединения множеств и конкатенации языков,

И объединение, и конкатенация основаны на булевой логике: объединение К и Ь — это множество строк /ш, для которых т Е К или т Е Ь, что является дизъюнкцией двух условий; аналогично, вхождение строки т в конкатенацию К ■ Ь — это дизъюнкция по всем разбиениям т = иу конъюнкции и Е К и V Е Ь.

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

Наверное, самой простой модификацией такого рода является рассмотрение муль-тиязыков (мультимножеств строк) вместо языков (множеств строк), как это сделал Кнут [17]. Оказалось, что это — частный случай более общего подхода, добавляющего к полукольцу некоторые требования о монотонности, за подробностями которого можно обратиться к обзорной статье Петре и Саломаа [25]. В обоих случаях важно то, что изменение основополагающего полукольца приводит к схожему изменению описательных моделей: Кнут изучал мультиграмматики [17], в то время как более общая теория включает в себя автоматы с весами и играющие роль взвешенных грамматик системы уравнений над некоммутативными формальными степенными рядами [25].

Однако полученные объекты — функции из множества всех строк над каким-то алфавитом в полукольцо и, вообще говоря, не являются языками. Следовательно, есть только один способ определить полукольцо как-то по-другому и всё равно получить именно формальные языки: заменить булево полукольцо на поле из двух элементов, иногда также обозначаемое как СГ(2). По этой причине Бакинова и др. [4] ввели понятие СР(2)-операций, определяемое с помощью замены основополагающей логики классических операций над языками с булевой на поле Е2. То есть объеди-

нение меняется на симметрическую разность, а конкатенация языков — на новую операцию, называемую СР (2)-конкатенацией. СЕ(2)-конкатенация К и Ь, обозначаемая за К © Ь, состоит из всех строк с нечётным количеством разбиений на строку из К и строку из Ь. В алгебраических терминах, СЕ(2)-операции — результат интерпретации сложения и умножения в кольце некоммутативных степенных рядов над в терминах формальных языков.

Стоит заметить, что СЕ(2)-операции не удовлетворяют условиям монотонности, необходимых для работы вышеупомянутой общей теории, С другой стороны, у них есть много интересных алгебраических свойств, отмеченных Бакиновой и др. в их статье. Например, множество всех языков над каким-то алфавитом вместе с (IКооперациями образует кольцо (а не просто полукольцо). Более того, в этом кольце у каждого содержащего пустую строку языка есть обратный по умножению [4].

Как я уже упоминал выше, изменение полукольца влечёт за собой соответствующее изменение описательных моделей. По этой причине Бакинова и др. ввели понятие [4] СР(2)-грамматик — варианта обыкновенных бесконтекстных грамматик, основанного на СЕ(2)-операциях вместо классических языковых операций. Формально они определены в терминах деревьев разбора: в предположении, что у каждой строки лишь конечное количество деревьев разбора, СЕ(2)-грамматика задаёт в точности все строки с нечётным количеством деревьев разбора. Если же у хотя бы одной строки бесконечно много деревьев разбора, то СЕ(2)-грамматика считается некорректной.

Важно заметить, что любая однозначная грамматика (то есть такая обыкновенная грамматика, что у каждой строки не больше одного дерева разбора) — корректная (;К(2)-грн.\1.\1н'1 нкн. задающая тот же самый язык. Если же есть какие-то неоднозначности, то обыкновенные грамматики говорят о существовании дерева разбора, в то время как СЕ(2)-грамматики проверяют чётность их количества. По этой причине обыкновенные и СЕ(2)-грамматпкн являются двумя разными обобщениями однозначных грамматик. Следовательно, (;К(2)-гра.\1.ма1 нкн полезны для доказательства того, что язык является существенно неоднозначным, то есть не может быть задан однозначной грамматикой, С другой стороны, как будет видно дальше, (1К(2)-гра.\1.\1а'1 нкн очень податливы к алгебраическим подходам из-за своих хороших алгебраических свойств,

В своей работе Бакинова и др. доказали для (;К(2)-гра.\1.ма1 пк много удобных алгоритмических свойств, которыми обладают обыкновенные грамматики. Во-первых, они показали, что корректность СЕ(2)-грамматики можно проверить за полиномиальное время [4], Во-вторых, они показали, что, по аналогии с обыкновенными грамматиками, каждую (;К(2)-гра.\1.ма1 пку можно преобразовать в нормальный вид Хомского, не изменив задаваемый ею язык [4], В третьих, для (;К(2)-гра.\1.ма1 нкн в нормальном виде Хомского они представили варианты алгоритмов Кокке-Касами-Янгера и Валианта [29] для разбора строки.

Кроме того, они привели много интересных примеров языков, задаваемых СЕ(2)-грамматиками. Однако они не представили никаких способов доказывать отсутствие СЕ(2)-грамматнкн для языка, за исключением простого подхода, работающего только для языков над односимвольным алфавитом [4], Здесь как раз и наступает мой черёд, В своей диссертации я представляю много результатов об буквенно-ограниченных и ограниченных языках, задаваемых (;К(2)-гра.\1.ма1 пка.мп.

Язык называется буквенно-ограниченным, если он — подмножество а*а* ... а*к, где

ai, a2, ..., ak~ различные символы алфавита. Язык называется ограниченным, если он — подмножество w* w2* ... u>* для каких-то с трок ..., Wk- Ограниченные

языки изучаются с самого становления теории формальных языков [14, 16] как очень хороший частный случай всех языков, который одновременно и достаточно прост для того, чтобы на многие естественные вопросы о них были бы удовлетворительные ответы, и достаточно общ для того, чтобы быть очень полезным для понимания выразительной мощности разных описательных моделей.

Если простыми словами, то главной темой моей диссертации является следующий вопрос: «Какие ограниченные языки можно задать СГ(2)-грамматикой, а какие нельзя?» Для ответа на этот вопрос я разработал алгебраический подход, позволивший мне и моим соавторам доказать верхние и нижние оценки на семейство задаваемых (iF(2)-rpH.\i.\i;nнкн.мн буквенно-ограниченных языков [21], К сожалению, оценки не сходятся полностью, различаясь на тонкое алгебраическое условие. Тем не менее, оценки достаточно близки для многих практических целей. Кроме того, я доказал, что кажущийся более сложным случай общих ограниченных языков может быть сведён к кажущемуся более простым буквенно-ограниченному случаю [20],

Далее, я показываю, что немедленным следствием из полученных результатов будет отсутствие СГ(2)-грамматики для языка {anbmcl | п = m ми m = I}, В частности, этот язык существенно неоднозначен. Вопрос о его существенной неоднозначности, поставленный Отербе и др. [2, стр. 375], оставался открытым очень долго. Однако стоит заметить, что позже, уже после того как я представил этот результат на конференции DLT 2021 [19], Кёхлин [18] нашёл новый алгебраический способ доказать существенную неоднозначность этого языка.

Другим научным вкладом моей работы являются многие свойства замкнутости, позволяющие доказывать задаваем,ость языка СГ(2)-грамматикой без её явного построения, Эти результаты позволяют рассуждать про семейство задаваемых GF(2)-грамматиками (не обязательно ограниченных) языков настолько же просто (и иногда даже проще), как и про семейство языков, задаваемых обыкновенными грамматиками.

Моя диссертация основана на трёх написанных мною статьях: «On the expressive power of GF(2)-grammars» [22] (в соавторстве с Александром Охотиным), «Ограниченные языки, задаваемые СГ(2)-грамматиками» [20] (без соавторов) и «Более тонкая характеризация буквенно-ограниченных языков, задаваемых GF(2)-грамматиками» [21] (в соавторстве с Маратом Мовеиным), Для удобства читателей я переставил результаты в порядке, делающем изложение более последовательным. Наконец, я хотел бы выразить свои благодарности всем тем, кто сделал возможным опубликовать эту диссертацию. Во-первых, я благодарю А, Охотина и М, Мов-сипа за многочисленные полезные обсуждения и за соавторство двух из представленных в диссертации статей. Во-вторых, я благодарю многих анонимных рецензентов, советы которых сильно повлияли на то, как я представляю мои рассуждения сегодня, В третьих, я благодарю Российский научный фонд и Министерство науки и высшего образования за их финансовую поддержку исследований, приведших к представляемым в этой диссертации результатам. Кроме того, я благодарю сотрудников факультета математики и компьютерных наук Санкт-Петербургского государственного университета за их помощь по многим техническим вопросам. Наконец, я хочу поблагодарить мою семью, искренне поддерживавшую меня всё это время.

Научное признание работы

Результаты этой диссертации были представлены на следующих международных конференциях с рецензируемыми сборниками докладов:

1, The 45th International Conference on Current Trends in Theory and Practice of Computer Science, Novv Smokovee, Slovakia, January 27-30, 2019 (статья была написана в соавторстве с Александром Охотиным [22]),

2, The 25th International Conference on Developments in Language Theory (DLT 2021), Porto, Portugal, August 16-20, 2021.

Все главные результаты диссертации представлены в статьях «Ограниченные языки, задаваемые Ъг(2)-грамматнкамн» [20] и «Более тонкая характеризация буквенно-ограниченных языков, задаваемых СГ(2)-грамматиками» [21], обе из которых были опубликованы в рецензируемых научных журналах.

Положения, выносимые на защиту

1. Верхняя и нижняя оценки на буквенно-ограниченные языки, задаваемые (II-'(2)-rpa.\i.\ia i пка.мп.

2. Способ сведения вопросов об общих ограниченных языках, задаваемых GF(2)-грамматиками, к похожим вопросам о буквенно-ограниченных языках.

3. Новый метод доказательства существенной неоднозначности языков.

4. Алгебраические свойства подмножеств а*Ь*, задаваемых СР(2)-грамматиками.

Основные научные результаты

1. Доказательство [20, стр. 260, теорема 2] того, что язык { anbmcl | п = ^ши m = I} не задаётся никакой однозначной грамматикой (теорема 12).

2. Верхняя оценка [21, стр. 226, теорема 2] на подмножества а*а*2 ... а*к, задаваемые (II-'(2)-rpa.\i.\iaiпка.мп (теорема 16). Личный вклад автора составляет 50%.

3. Нижняя оценка [21, стр. 232, теорема 3] на задаваемые (1К(2)-грамма'1 пка.мп подмножества а*а2,.. .a*kJ которая «почти» совпадает с вышеупомянутой верхней оценкой (теорема 17). Личный вклад автора составляет 50%.

4. Теорема [20, стр. 266, теорема 5], показывающая, что для любого ограниченного языка L Ç w*w^ ... w*, существует такой соответствующий буквенно-ограниченный язык La Ç а*а*... а*, что L задаётся СР(2)-грамматикой, если и только если задаётся La (теорема 19). Неформально, эта теорема сводит общий вопрос об ограниченных языках, задаваемых (II-'(2)-грамм ai пка.мп. к кажущемуся более простым вопросу о буквенно-ограниченных языках, задаваемых (II-'(2)-грамм ai пка.мп.

5, Результат [21, стр. 216, теорема 1] о том, что задаваемые (;К(2)-грн.\1.мн1 нкн.мн подмножества а*Ь* образуют кольцо относительно выбранных некоторым естественным образом операций (теорема 15), Личный вклад автора составляет 50%.

.....I......I с^Т^с"^1 -в-

Некоторые основные свойства СЕ(2)-грамматик

1.1 Понятия о СГ(2)-операциях и GF(2)-грамматиках

Относительно недавно Бакинова и др. [4] ввели понятие СЕ(2)-онераций над формальными языками. Изучение (;К(2)-ош'рнцнн — тема на пересечении алгебры и теории формальных языков. Цель этой работы — охарактеризовать некоторые изучаемые теорией формальных языков объекты в терминах различных алгебраических структур, таких как кольца и векторные пространства. Поэтому нужно будет вспомнить некоторые определения и результаты из теории формальных языков, уделяя особенное внимание их интерпретации в алгебраических терминах.

Определение 1. Алфавит — это просто непустое конечное множество. Элементы алфавита обычно называют символами или буквам,и. Конечная (возможно, пустая) последовательность символов алфавита Е обычно называется строкой или словом над алфавитом Е, Множество строк над каким-либо алфавитом называется языком.

Определение 2. Если т = .. .тп а V = У\ь2 ... ьт — строки над алфавитом Е (такая запись означает, что т — это строка из п символов, в которой г-ый символ от начала строки равен тг Е Е; аналогиино, V — это строка из т символов ^ Е Е), то строка /ш\'ш2 ... .. .ьт над Е называется конкатснацией т и V а обычно

обозначается ту.

Определение 3. Множество всех строк над алфавитом Е обозначается Е*. В чаетЕ*

волов строку над Е), Будем обозначать пустую с троку за е. Несложно проверить,

Е*

Е* Е

Е*

Е

конкатенации. Идея языковых операций похожа, но она получается путём задания алгебраической структуры па множестве 2е* всех подмножеств Е*. Точнее, можно задать структуру полукольца на множестве всех языков: объединение множеств будет

играть роль суммы, а более сложная операция конкатенации языков (определённая ниже) будет играть роль произведения.

Определение 4. Если К и Ь — языки над алфавитом Е, то их конкатенация (обычно обозначается КЬ) — это язык всех строк, у которых есть хотя бы одно представление в виде конкатенации строки из К и строки из Ь. Другими словами,

К ■ Ь = { т | число разбивний т = иу, в которых и Е К ж V Е Ь, те равно нулю }.

Полезно сравнить это определение с операцией объединения множеств:

К и Ь = { т | хотя бы одно из условий т Е К и т Е Ь верно }.

Обе операции определены в терминах существования чего-то,

Е

кольцо, в котором объединение мможеств — сумма, конкатенация языков — произведение, пустой язык 0 — нейтральный элем,ент для, сложения («ноль») и состоящий только из пустой строки язык {е} — нейтральный эл,ем,ент для, умножения ( «единица» ).

Известно, что теорема А — следствие более общей теории некоммутативных формальных степенных рядов над полукольцом.

Определение 5. Пусть Е — алфавит, а 5 — полукольцо. Рассмотрим произвольное отображение из Е* в Б. Скажем, что образ строки т Е Е* под этим отображением есть Е Б. Тогда можно рассмотреть формальную сумму / = ^ т. Такая фор-

твЕ*

мальная сумма f называется некоммутативным формальным степенным рядом над полукольцом Б. Значения обычно называют коэффициентами некоммутативного формального степенного ряда f.

Е

ми, а каждую строку т — некоммутативным произведением её символов. Другими словами, я смотрю на каждую т как на элемент свободного моноида Е*, порождён-Е

Тогда, используя представление формальных степенных рядов в виде формальной суммы, можно определить сложение и умножение по следующим формулам: (/ + 9)'ш = /ад + От и (¡д)'Ш = ^ ¡и9и- Обозначим полученную алгебраическую

) иуь •

иь=т

структуру за Б((Е*)), Можно показать, что Б((Е*)) — полукольцо, в котором роль нейтрального элемента по сложению играет формальная сумма ^ 0 ■ и>, делающая

каждый коэффициент нулём, а роль нейтрального элемента по умножению играет формальная сумма 1 ■ е + ^ 0 ■ и>, делающая коэффициент перед пустой строкой

адвЕ* ,т=е

единицей, а все остальные коэффициенты нулём. Более того, можно показать, что если Б — кольцо, то Б((Е*)) — тоже кольцо

Если точнее, то кольцо формальных языков с классическими языковыми операциями — это кольцо некоммутативных формальных степенных рядов, в котором Б — это булево полукольцо В, Следовательно, на классические языковые операции можно смотреть следующим образом: задаётся алгебраическая структура В((Е*)) па

множестве 2е*. Что произойдёт, если выбрать другое полукольцо 5? Если в 5 больше двух элементов, то для каждой строки нужно знать больше одного бита информации, чтобы определить коэффициент при ней. Следовательно, большие $ не подходят для задания алгебраической структуры па исходном множестве 2 е* (а не на каком-то более сложном множестве).

Таким образом, СЕ(2)-операции, введённые Бакиновой и др. [4], можно рассматривать как альтернативный способ задать алгебраическую структуру на множестве 2е* всех языков над алфавитом Е: вместо полукольца В((Е*)) некоммутативных формальных степенных рядов с булевыми коэффициентами рассматривается полукольцо некоммутативных формальных степенных рядов с коэффициентами из поля из двух элементов: Е2((Е*)).

Теперь можно определить СЕ(2)-операции как языковые операции, соответствующие сложению и умножению в кольце Е2((Е*)) при естественной биекции между 2е* и Е2((Е*)), Сложение в Е2((Е*)) соответствует симметрической разности языков (здесь и далее я буду обозначать симметрическую разность значком ф суммы по модулю 2), а умножение соответствует более сложной операции, называемой СР(2)-конкатенацией.

Определение 6 ([4]). Если К и Ь — языки над алфавитом Е, то их СР(2)-конкатенация (обозначается К © Ь) — это язык всех строк, у которых нечётное количество представлений в виде конкатенации строки из К и строки из Ь. Другими словами,

К © Ь = { т | число разбив ний т = иу, в которых и € К и V € Ь, печёт но }.

Чтобы ещё больше прояснить схожесть этого определения с определением 4, выпишем явно смысл операции симметрической разности:

К ф Ь = { т | ровно одно из условий т € К и т € Ь верно }.

Аналогично тому, как обе классические языковые операции определяются в терминах существования, чего-то, обе СЕ(2)-операцпн определяются в терминах нечётности некоторой величины (для симметрической разности важно, что 1 — единственное нечётное число во множестве {0,1, 2}),

Это «новое» кольцо имеет гораздо более богатые алгебраические свойства, чем полукольцо В((Е*)) языков с классическими языковыми операциями. Например, как замечено Бакиновой и др., каждый содержащий е язык имеет обратный по умножению [4]. Упомянутые алгебраические свойства позволяют использовать сильные алгебраические методы для изучения языков относительно (;К(2)-ош'рацпп. методы, неприменимые к классическим операциям над формальными языками. Следовательно, есть надежда, что изучение (;К(2)-ош'рацпп может привести к более глубокому пониманию классических операций над формальными языками,

И новый взгляд действительно показал себя достаточно плодотворным. Один из главных результатов этой диссертации (теорема 12), впервые представленный мною на конференции БЬТ 2021 [19], «закрыл» долго бывший открытым вопрос в теории формальных языков, не поддававшийся классическим подходам десятилетиями (однако стоит отметить, что Кёхлин позже доказал тот же самый результат другим

и

алгебраическим методом, не используя СГ(2)-грамматики [18]), А именно, я доказал, что нет однозначной грамматики, задающей язык { апЬтс1 | п = ^ши т = I}, Формальное определение однозначной грамматики будет дано дальше по тексту. Перед этим мне нужно объяснить некоторые другие определения и описать контекст, в котором они существуют.

Точная тема моей диссертации может быть сформулирована так: «описать ограниченные языки, задаваемые СГ(2)-грамматиками», Давайте по очереди поймём все появляющиеся здесь слова. Во-первых, что значат слова «ограниченный язык»? Многие задачи о различных версиях обыкновенных бесконтекстных грамматик (я определю их ниже) очень сложны: либо "по-человечески" сложны, либо доказуемо на границах человеческого понимания. Например, многие естественные вопросы об обыкновенных и однозначных грамматиках алгоритмически неразрешимы, В частности, неразрешима задача проверки однозначности данной обыкновенной грамматики. Мне нравится интерпретировать этот факт следующим образом: нет никакого общего всегда работающего подхода для доказательства неоднозначности грамматики; единственное, что мы можем сделать — это находить всё более и более сильные методы, работающие иногда, надеясь, что в итоге все интересующие нас ситуации окажутся в пределах этого «иногда». Ограниченные языки — полезный частный случай, в котором задачи, являющиеся «сильно» неразрешимыми для произвольных языков, оказываются, пусть и не простыми, но хотя бы полностью подвластными общим алгоритмам. Первые результаты подобного рода были доказаны Гинзбургом и Спа-ниером [14] и Гинзбургом и Уллианом [16], А позже было получено ещё много схожих результатов.

Определение 7. Для символа а Е Е обозначим за а* язык всех состоящих только из символа а строк (включая пустую строку). Другими словами, а* = {е,а,а2,а3,...}. Язык над алфавитом Е = {а\,а2,... ,ак} называется буквенно-ограниченным, если он — подмножество языка а* ■ а*2 ■... ■ а*к, где произведение — это конкатенация языков.

Замечание 1. Аналогично а*, обозначен не а+ соответствует языку всех непустых строк, состоящих только из символа а: а+ = {а, а2,а3,...} = (а*) \ {е}.

Так как а* и а+ — это языки, к ним можно применять языковые операции. Например, а*а* ... — это язык всех строк над алфавитом {а\, а2,..., а,к}, «отсортированных относительно порядка а\ < а2 < ... < ак»'. они начинаются па повторённый несколько (возможно, ноль) раз символ а\, продолжаются повторённым несколько (возможно, ноль) раз символом а2, ..., закапчиваются па повторённый несколько (возможно, ноль) раз символ Аналогично, а+а+.. .а+ — язык всех «отсортированных» строк над алфавитом {а\,а2,... ,ак}, содержащих каждый символ а,г хотя бы по разу.

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

Определение 8. Язык Ь над адфавитом Е называется ограниченным, если существуют положительное целое число к и к строк и>2, ,,,, ^^ над Е, таких что Ь С и)**т* ...т*к.

Чтобы лучше понять, откуда берётся определение (;К(2)-грн.\1.м;пнк. вспомним определения детерминированного конечного автомата и обыкновенной бескон-

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

Неформально, детерминированный конечный автомат — это конечный ориенти-

Е

Вершины графа называются состояниями автомата. Какое-то состояние помечено как начальное состояние. Более того, для каждого состояния д и каждого символа с из алфавита, есть ровно одна помеченная символом с исходящая из д дуга. Наконец, некоторые состояния названы принимающими. Если все условия выше удовлетворены, то можно определить поведение автомата на строке 5 € Е*: стартуя из начального состояния, он читает символы в по одному слева направо и, на каждом шаге, ходит по помеченной только что прочитанным символом исходящей дуге из его текущего

Е

5 € Е* лежит в задаваемом автоматом языке, если после прочтения всей строки в автомат пришёл в принимающее состояние. Иначе — не лежит. Формальные определения автомата и задаваемого языка можно найти ниже.

Определение 9 ([28]). Детерминированный конечный автомат (ДКА, БРА по-английски) — это пятёрка Е,8,д0, Р), где

1. Q — конечное множество состояний, Е

3, 8: Ц х Е ^ Ц — функция переходов,

4, д0 € Ц — начальное состояние, и

5, Р С Ц — множество принимающих состояний.

Определение 10 ([28]). Пусть М = Е, 8, д0,Р) — ДКА, а» = .. .тп — строка над алфавитом Е, Говорят, что автомат М принимает строку гм, если существует такая последовательность г0, Г\,..., гп из п + 1 состояний из Q, что выполняются следующие условия:

1- го = до,

2. 8{г'г, Ы+х) = Гг+1 для % = 0, 1, . . . ,П — 1,

3. гп € Р.

Задаваемый автоматом М язык Ь(М) определяется как язык всех принимаемых М строк. Другими словами, Ь(М) := { т | т € Е*, М принимает т },

Определение 11 ([28]). Язык называется регулярным, если он задаётся каким-то ДКА.

В данном выше определении функция обязана быть полной функцией х Е, Иногда я буду рассматривать неполные ДКА: ДКА, в которых функция переходов может быть не задана для некоторых пар (д, с), где д € и с € Е, Этому придаётся следующий смысл: если автомат читает символ с, находясь в состоянии д, вычисление останавливается и строка отвергается. Каждый неполный ДКА может быть

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

Определение обыкновенных бесконтекстных грамматик намного более сложное. Интуитивно, обыкновенная бесконтекстная грамматика определяет конечное количество синтаксических категории для строк над алфавитом Е. Синтаксическая категория — это свойство, которым строка обладает или не обладает; другими словами, синтаксическая категория определяет язык над Е, Кроме того, есть правила, позволяющие определять синтаксические категории в терминах других синтаксических категорий. Например, «noun phrase» — синтаксическая категория, которую можно разобрать как «noun», «adjective ■ noun» (что задаёт собой все строки, предетавимые в виде конкатенации строки, являющейся «adjective», и строки, являющейся «noun») и некоторыми другими способами. Здесь важно, что каждое правило представляет собой возможный способ интерпретировать одну синтаксическую категорию в терминах других синтаксических категорий и символов алфавита.

Список литературы диссертационного исследования кандидат наук Макаров Владислав Маратович, 2026 год

Литература

[1] J.-P. Allouche, J, Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003,

[2] J.-M, Autebert, J, Beauquier, L, Boasson, M, Nival. "Quelques problèmes ouverts en théorie des langages algébriques", RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 13, number 4 (1979), 363-378,

[3] J.-M, Autebert, J, Berstel, L, Boasson, "Context-free languages and pushdown automata", in: Eozenberg, Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, Berlin, 1997, 111-174.

[4] E. Bakinova, A. Basharin, I. Batmanov, K. Lvubort, A. Okhotin, E. Sazhneva, "Formal languages over GF(2)", Information and Computation, 283 (2022), article 104672.

[5] Y. Bar-Hillel, M, Perles, E. Shamir, "On formal properties of simple phrase-structure grammars", Zeitschrift fur Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (1961), 143-177,

[6] N. Chomsky, M, P. Sehiitzenberger, "Algebraic theory of context-free languages", Studies in Logic and the Foundations of Mathematics, 35 (1963), 118-161.

[7] S. Eilenberg, Automata, Languages and Machines, Volume A, Academic Press, 1974.

[8] C. C. Elgot, J. E. Mezei, "On relations defined by generalized finite automata", IBM Journal of Research and Development, 9:1 (1965), 47-68.

[9] P. Flajolet, "Analytic methods and ambiguity of context-free languages", Theoretical Computer Science, 49 (1987), 283-309.

[10] G. Christol, "Ensembles presque périodiques fc-reeonnaissables", Theoretical Computer Science, 9 (1979), 141-145.

[11] T. N. Hibbard, J. Ullian, "The independence of inherent ambiguity from complementedness among context-free languages", Journal of the ACM, 13 (1966), 588-593.

[12] S. Ginsburg, A. Greibach, M, A. Harrison, "One-way stack automata", Journal of the ACM, 14:2 (1967), 389-418.

[13] S. Ginsburg, H. G. Rice, "Two families of languages related to ALGOL", Journal of the ACM, 9 (1962), 350-371.

[14] S, Ginsburg, E, H, Spanier, "Bounded ALGOL-like languages", Transactions of the American Mathematical Society, Volume 113, number 2 (1964), 333-368,

[15] S, Ginsburg, E, H, Spanier, "Semigroups, Presburger formulas, and languages", Pacific Journal of Mathematics, Volume 16, number 2 (1966), 285-296,

[16] S, Ginsburg, J, Ullian, Ambiguity in context-free languages Journal of the ACM, 13 (1966), 62-89.

[17] D, E, Knuth, "Context-free multilanguages", Theoretical Stuides in Computer Science, Academic Press, 1992, 1-13,

[18] F, Koeehlin, "New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Language", Foundations of Software Technology and Theoretical Computer Science 2022 (Chennai, India, 2022),

[19] V, Makarov, "Bounded languages described by GF(2)-grammars", Developments in Language Theory (DLT 2021, Porto, Portugal, August 16-20, 2021), LNCS 12811, 279-290.

[20] В. Макаров, «Ограниченные языки, задаваемые GI-'(2)-rpa.\i.\iaiнка.мн (анонс)», Записки научных семинаров ПОМИ, 546 (2025), 259-267.

[21] В. Макаров, М. Мовсин, «Более тонкая характеризация буквенно-ограниченных языков, задаваемых GI-'(2)-rpa.\i.\iaiнка.мнАлгебра и анализ, 38:1 (2026), 198234.

[22] V. Makarov, A. Okhotin, "On the expressive power of GF(2)-grammars", SOFSEM 2019: Theory and Practice of Computer Science (Novv Smokovee, Slovakia, 27-30 January 2019), LNCS 11376, 310-323.

[23] O. Martvnova, A. Okhotin, "Non-closure under complementation for unambiguous linear grammars", Information and Computation, 292 (2023), article 105031.

[24] M. Mikhelson, A. Okhotin, "A parallel algorithm for counting parse trees", Information and Computation, 303 (2025), 105237 .

[25] I. Petre, A. Salomaa, "Algebraic systems and pushdown automata", in: Droste, Kuich, Vogler (Eds.), Handbook of Weighted Automata", Springer, 2009, 257-289.

[26] W, Ogden, "A helpful result for proving inherent ambiguity", Mathematical systems theory, 2:3 (1968), 191-194.

[27] E. Parikh, "On Context-Free Languages", Journal of the ACM, 13:4 (1966), 570-581.

[28] M. Sipser, Introduction to the Theory of Computation, Third Edition, Cengage Learning, 2013.

[29] L. G. Valiant, "General context-free recognition in less than cubic time", Journal of Computer and System Sciences, 10:2 (1975), 308-314.