Программирование

Оглавление Перечень определений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Перечень теорем и лемм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. Основные определения и обозначения . . . . . . . . . . . . . . . . . . . . . 9 1.1. Множества и операции над ними . . . . . . . . . . . . . . . . . . . . . . 9 1.2. Отношения на множествах . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2. Языки и операции над ними . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1. Алфавит и цепочки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2. Понятие языка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3. Операции над языками . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4. Способы задания языков . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. Системы текстовых замен . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4. Грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.1. Формальное определение грамматики . . . . . . . . . . . . . . . . . . . . 27 4.2. Классификация грамматик по Хомскому . . . . . . . . . . . . . . . . . . 31 4.3. Свойства языков и грамматик . . . . . . . . . . . . . . . . . . . . . . . . 32 5. Иерархия автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.1. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.1.1. Конечные детерминированные автоматы . . . . . . . . . . . . . . . 50 5.1.2. Конечные недетерминированные автоматы . . . . . . . . . . . . . 50 5.1.3. Способы описания конечных автоматов . . . . . . . . . . . . . . . 51 5.1.4. Свойства автоматных языков . . . . . . . . . . . . . . . . . . . . . 54 5.2. Автоматы с магазинной памятью . . . . . . . . . . . . . . . . . . . . . . 70 5.3. Линейные ограниченные автоматы . . . . . . . . . . . . . . . . . . . . . 72 5.4. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 . . . . . . . . . . . . . . . . . 76 6.1. Регулярные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6. Регулярные и контекстно-свободные языки 2 6.2. Регулярные выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.3. Уравнения с регулярными коэффициентами . . . . . . . . . . . . . . . . 78 6.4. Самовставленные языки . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.5. Лемма о накачке для регулярных языков . . . . . . . . . . . . . . . . . . 86 6.6. Деревья вывода и однозначность грамматик типа 2 . . . . . . . . . . . . 88 6.7. Преобразования КС-грамматик . . . . . . . . . . . . . . . . . . . . . . . . 93 6.8. Лемма о накачке для КС-языков . . . . . . . . . . . . . . . . . . . . . . . 98 Перечень определений 1 Определение (Подмножество) . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Определение (Равенство множеств) . . . . . . . . . . . . . . . . . . . . . 9 3 Определение (Собственное подмножество) . . . . . . . . . . . . . . . . . 10 4 Определение (Объединение множеств) . . . . . . . . . . . . . . . . . . . 10 5 Определение (Пересечение множеств) . . . . . . . . . . . . . . . . . . . 10 6 Определение (Разность множеств) . . . . . . . . . . . . . . . . . . . . . 10 7 Определение (Пустое множество) . . . . . . . . . . . . . . . . . . . . . . 10 8 Определение (Конечное множество) . . . . . . . . . . . . . . . . . . . . 10 9 Определение (Декартово произведение множеств) . . . . . . . . . . . . 11 10 Определение (Бинарное отношение двух множеств) . . . . . . . . . . . 11 11 Определение (Бинарное отношение на множестве) . . . . . . . . . . . . 12 12 Определение (Степень отношения) . . . . . . . . . . . . . . . . . . . . . 12 13 Определение (Рефлексивное отношение) . . . . . . . . . . . . . . . . . . 13 14 Определение (Антирефлексивное отношение) . . . . . . . . . . . . . . . 13 15 Определение (Транзитивное отношение) . . . . . . . . . . . . . . . . . . 13 16 Определение (Симметричное отношение) . . . . . . . . . . . . . . . . . 13 17 Определение (Антисимметричное отношение) . . . . . . . . . . . . . . . 13 18 Определение (Отношение эквивалентности) . . . . . . . . . . . . . . . . 13 19 Определение (Класс эквивалентности) . . . . . . . . . . . . . . . . . . . 13 20 Определение (Замыкание отношения) . . . . . . . . . . . . . . . . . . . 13 21 Определение (Отношение частичного порядка) . . . . . . . . . . . . . . 14 22 Определение (Отношение рефлексивного порядка) . . . . . . . . . . . . 14 23 Определение (Отношение строгого порядка) . . . . . . . . . . . . . . . . 14 24 Определение (Отношение линейного порядка) . . . . . . . . . . . . . . . 15 25 Определение (Алфавит) . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 26 Определение (Цепочка) . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 27 Определение (Пустая цепочка) . . . . . . . . . . . . . . . . . . . . . . . 16 28 Определение (Длина цепочки) . . . . . . . . . . . . . . . . . . . . . . . 16 29 Определение (Конкатенация) . . . . . . . . . . . . . . . . . . . . . . . . 16 30 Определение (Подцепочка) . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 31 Определение (Степень алфавита) . . . . . . . . . . . . . . . . . . . . . . 17 32 Определение (Зеркальное отражение цепочки) . . . . . . . . . . . . . . 17 33 Определение (Язык) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 34 Определение (Конечный язык) . . . . . . . . . . . . . . . . . . . . . . . 18 35 Определение (Разность языков) . . . . . . . . . . . . . . . . . . . . . . . 18 36 Определение (Дополнение языка) . . . . . . . . . . . . . . . . . . . . . . 18 37 Определение (Конкатенация языков) . . . . . . . . . . . . . . . . . . . . 18 38 Определение (Левое частное) . . . . . . . . . . . . . . . . . . . . . . . . 19 39 Определение (Правое частное) . . . . . . . . . . . . . . . . . . . . . . . 19 40 Определение (Степень языка) . . . . . . . . . . . . . . . . . . . . . . . . 19 41 Определение (Итерация языка) . . . . . . . . . . . . . . . . . . . . . . . 20 42 Определение (Регулярные операции) . . . . . . . . . . . . . . . . . . . . 20 43 Определение (Положительная итерация языка) . . . . . . . . . . . . . . 20 44 Определение (Зеркальное отражение языка) . . . . . . . . . . . . . . . . 20 45 Определение (Подстановка) . . . . . . . . . . . . . . . . . . . . . . . . . 20 46 Определение (Гомоморфизм) . . . . . . . . . . . . . . . . . . . . . . . . . 21 47 Определение (Спецификаторы свойств языка) . . . . . . . . . . . . . . . 21 48 Определение (Конструктор) . . . . . . . . . . . . . . . . . . . . . . . . . 22 49 Определение (Распознаватель) . . . . . . . . . . . . . . . . . . . . . . . 22 50 Определение (Система текстовых замен) . . . . . . . . . . . . . . . . . . 24 51 Определение (Отношение непосредственной выводимости) . . . . . . . . 24 52 Определение (Отношение нетривиальной выводимости) . . . . . . . . . 24 53 Определение (Отношение выводимости) . . . . . . . . . . . . . . . . . . 24 54 Определение (Вывод цепочки) . . . . . . . . . . . . . . . . . . . . . . . . 24 55 Определение (Язык, порожденный системой текстовых замен) . . . . . 25 56 Определение (Язык, допускаемый системой текстовых замен) . . . . . . 25 57 Определение (Порождающая грамматика) . . . . . . . . . . . . . . . . . 27 58 Определение (Язык, порожденный грамматикой) . . . . . . . . . . . . . 27 59 Определение (Эквивалентные грамматики) . . . . . . . . . . . . . . . . 28 60 Определение (Аналитическая грамматика) . . . . . . . . . . . . . . . . . 30 61 Определение (Язык, допускаемый грамматикой) . . . . . . . . . . . . . 30 5 62 Определение (Двойственная грамматика) . . . . . . . . . . . . . . . . . 30 63 Определение (Грамматика типа 1) . . . . . . . . . . . . . . . . . . . . . 31 64 Определение (Грамматика типа 2) . . . . . . . . . . . . . . . . . . . . . 32 65 Определение (Грамматика типа 3) . . . . . . . . . . . . . . . . . . . . . 32 66 Определение (Неукорачивающие грамматики) . . . . . . . . . . . . . . . 32 67 Определение (Конечный детерминированный автомат) . . . . . . . . . . 50 68 Определение (Язык допускаемый КДА) . . . . . . . . . . . . . . . . . . 50 69 Определение (Конечный недетерминированный автомат) . . . . . . . . . 50 70 Определение (Язык допускаемый НКА) . . . . . . . . . . . . . . . . . . 51 71 Определение (Таблица переходов) . . . . . . . . . . . . . . . . . . . . . 51 72 Определение (Диаграмма переходов) . . . . . . . . . . . . . . . . . . . . 54 73 Определение (Полностью определенный конечный автомат) . . . . . . . 54 74 Определение (Недостижимое состояние) . . . . . . . . . . . . . . . . . . 62 75 Определение (Различение состояний автомата) . . . . . . . . . . . . . . 65 76 Определение (k-неразличимые состояния) . . . . . . . . . . . . . . . . . 65 77 Определение (Эквивалентные состояния) . . . . . . . . . . . . . . . . . 65 78 Определение (Эквивалентные автоматы) . . . . . . . . . . . . . . . . . . 68 79 Определение (Автомат с магазинной памятью) . . . . . . . . . . . . . . 70 80 Определение (Язык, допускаемый МП-автоматом) . . . . . . . . . . . . 71 81 Определение (Детерминированный МП-автомат) . . . . . . . . . . . . . 72 82 Определение (Детерминированный язык типа 2) . . . . . . . . . . . . . 72 83 Определение (Линейный ограниченный автомат) . . . . . . . . . . . . . 72 84 Определение (Язык, допускаемый ЛО-автоматом) . . . . . . . . . . . . 73 85 Определение (Детерминированный ЛО-автомат) . . . . . . . . . . . . . 73 86 Определение (Машина Тьюринга) . . . . . . . . . . . . . . . . . . . . . 73 87 Определение (Финализирующая цепочка) . . . . . . . . . . . . . . . . . 74 88 Определение (Язык, допускаемый машиной Тьюринга) . . . . . . . . . . 74 89 Определение (Регулярное множество) . . . . . . . . . . . . . . . . . . . 76 90 Определение (Регулярный язык) . . . . . . . . . . . . . . . . . . . . . . 76 91 Определение (Регулярное выражение) . . . . . . . . . . . . . . . . . . . 76 92 Определение (Уравнение с регулярными коэффициентами) . . . . . . . 78 6 93 Определение (Леволинейное уравнение с регулярными коэффициентами) 78 94 Определение (Минимальная неподвижная точка уравнения с регуляр­ ными коэффициентами) . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Определение (Леволинейная система уравнений с регулярными коэф­ фициентами) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 79 80 Определение (Минимальная неподвижная точка системы уравнений с регулярными коэффициентами) . . . . . . . . . . . . . . . . . . . . . . . 80 97 Определение (Линейная грамматика) . . . . . . . . . . . . . . . . . . . . 83 98 Определение (Самовставленная грамматика) . . . . . . . . . . . . . . . 84 99 Определение (Самовставленный язык) . . . . . . . . . . . . . . . . . . . 84 100 Определение (Дерево вывода) . . . . . . . . . . . . . . . . . . . . . . . . 88 101 Определение (Крона дерева вывода) . . . . . . . . . . . . . . . . . . . . 89 102 Определение (Сечение дерева вывода) . . . . . . . . . . . . . . . . . . . 89 103 Определение (Крона сечения) . . . . . . . . . . . . . . . . . . . . . . . . 89 104 Определение (Неоднозначная грамматика) . . . . . . . . . . . . . . . . . 90 105 Определение (Существенно неоднозначный язык) . . . . . . . . . . . . . 93 106 Определение (ε-правило) . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 107 Определение (A-правило) . . . . . . . . . . . . . . . . . . . . . . . . . . 93 108 Определение (Цепное правило) . . . . . . . . . . . . . . . . . . . . . . . 93 109 Определение (Грамматика без ε-правил) . . . . . . . . . . . . . . . . . . 93 110 Определение (Нормальная форма Хомского) . . . . . . . . . . . . . . . . 97 Перечень теорем и лемм 1 Лемма (О транзитивном замыкании отношения) . . . . . . . . . . . . . 14 2 Лемма (О рефлексивном транзитивном замыкании отношения) . . . . . 14 1 Теорема (О двойственной грамматике) . . . . . . . . . . . . . . . . . . . 30 2 Теорема (О существовании эквивалентной грамматики с ограничением на наличие терминальных символов) . . . . . . . . . . . . . . . . . . . . 32 3 Теорема (О неукорачиваемости контекстно-зависимых языков) . . . . . 34 4 Теорема (Классификация конечных языков) . . . . . . . . . . . . . . . . 36 5 Теорема (О замкнутости класса L3 относительно регулярных операций) 37 6 Теорема (О замкнутости класса L2 относительно регулярных операций) 40 7 Теорема (О замкнутости класса L1 относительно регулярных операций) 42 8 Теорема (О замкнутости класса L0 относительно регулярных операций) 45 9 Теорема (О замкнутости классов языков относительно положительной итерации) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 47 Теорема (О замкнутости классов языков относительно зеркального от­ ражения) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Теорема (О замкнутости L0 и L2 относительно подстановки) . . . . . . 47 11.1 Следствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 12 Теорема (О замкнутости класса L0 относительно пересечения) . . . . . 48 13 Теорема (Признаки непустоты и бесконечности автоматного языка) . . 54 14 Теорема (Об автоматности языков типа 3) . . . . . . . . . . . . . . . . . 56 14.1 Следствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 14.2 Следствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 15 Теорема (О КДА без недостижимых состояний) . . . . . . . . . . . . . 62 16 Теорема (Критерий неразличимости состояний автомата) . . . . . . . . 65 17 Теорема (О минимальном автомате) . . . . . . . . . . . . . . . . . . . . 68 1 Утверждение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2 Утверждение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 18 Теорема (О классе языков, допускаемых машиной Тьюринга) . . . . . . 74 3 Утверждение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 11 8 3 Лемма (Эквивалентные регулярные выражения) . . . . . . . . . . . . . 4 Лемма (О решении леволинейного уравнения с регулярными коэффи­ 77 циентами) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 19 Теорема (О регулярности языков типа 3) . . . . . . . . . . . . . . . . . 81 20 Теорема (О замкнутости языков типа 3 относительно зеркального отра­ жения и подстановки) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 21 Теорема (О праволинейности языков типа 3) . . . . . . . . . . . . . . . 84 22 Теорема (О несамовставленных языках типа 2) . . . . . . . . . . . . . . 84 23 Теорема (Об эквивалентности представлений языков типа 3) . . . . . . 86 24 Теорема (Лемма о накачке (о разрастании) регулярных языков) . . . . . 86 4 Утверждение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 25 Теорема (Об однозначности языков типа 3) . . . . . . . . . . . . . . . . 93 26 Теорема (О грамматиках без ε-правил) . . . . . . . . . . . . . . . . . . . 93 26.1 Следствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 27 Теорема (О грамматиках без цепных правил) . . . . . . . . . . . . . . . 95 28 Теорема (О грамматиках в нормальной форме Хомского) . . . . . . . . 97 5 Лемма (О длине выводимой цепочки) . . . . . . . . . . . . . . . . . . . 98 29 Теорема (Лемма о накачке (о разрастании) для КС-языков) . . . . . . . 99 1. Основные определения и обозначения 1.1. Множества и операции над ними Понятия множества и элемента множества являются первичными, т.е. не подлежат определениям в строго математическом смысле. Обозначают x ∈ X, если элемент x содержится в множестве X (или, другими словами, x принадлежит X). Обозначают x ∈ / X, если элемент x не содержится в множестве X (или, другими словами, x не принадлежит X). Множества натуральных, целых и вещественных чисел будем обозначать соответ­ ственно N, Z и R. Обычно в приложениях рассматриваются только те множества, которые содержат­ ся в некотором фиксированном множестве, называемом универсальным (универсу­ мом) — U . Тогда любое множество X определяется следующим образом: X = {x ∈ U | P(x)}, (1.1) где P(x) — некоторый предикат, который выполняется только для элементов множе­ ства X. Выражение (1.1) читается так: X — множество, состоящее из всех таких эле­ ментов x из U , для которых выполняется P(x). Замечание 1. Во многих случаях, если это не приводит к двусмысленности, множе­ ство U в (1.1) опускают и пишут X = {x | P(x)}. Замечание 2. В логических выражениях операцию конъюнкции иногда будем заме­ нять запятой, если это не приведет к двусмысленности. Определение 1 (Подмножество). Множество A называют подмножеством множества B, и пишут A ⊆ B, если каждый элемент A содержится в B, т. е. A ⊆ B ⇔ (∀x, (x ∈ A) → (x ∈ B)). Определение 2 (Равенство множеств). Множество A называют равным множеству B, и пишут A = B, если каждый элемент A содержится в B, и каждый элемент из B содержится в A, т. е. A = B ⇔ (∀x, (x ∈ A) ⇔ (x ∈ B)). 10 Другими словами множества A и B равны, если A ⊆ B и B ⊆ A. Если равенство множеств A и B не выполняется, пишут A ̸= B и говорят, что A не равно B. Определение 3 (Собственное подмножество). Множество A называют собственным подмножеством множества B, и пишут A ⊂ B, если A является подмножеством B и A ̸= B, т. е. A ⊂ B ⇔ ((A ⊆ B) & (A ̸= B)). Определение 4 (Объединение множеств). Множество A называют объединением мно­ жеств B и C, и пишут A = B ∪ C или A = B + C, если оно содержит в себе все те и только те элементы, которые содержатся хотя бы в одном из этих множеств, т. е. A = B ∪ C = B + C ⇔ A = {x | (x ∈ B) ∨ (x ∈ C)}. Определение 5 (Пересечение множеств). Множество A называют пересечением мно­ жеств B и C, и пишут A = B ∩ C, если оно содержит все те и только те элементы, которые содержатся как в B, так и в C, т. е. A = B ∩ C ⇔ A = {x | (x ∈ B) & (x ∈ C)}. Определение 6 (Разность множеств). Множество A называют разностью множеств B и C, и пишут A = B∖C или A = B − C, если оно содержит все те и только те элементы B, которые не содержатся в C, т. е. A = B∖C = B − C ⇔ A = {x | (x ∈ B) & (x ∈ / C)}. Определение 7 (Пустое множество). Множество, которому не принадлежит ни один элемент, называют пустым множеством и обозначают ∅. Считают, что пустое множество является подмножеством любого множества. Множество всех подмножеств множества A обозначают P(A). P(A) = {B | B ⊆ A}. Определение 8 (Конечное множество). Множество A называют конечным, если оно состоит из конечного числа элементов n ∈ N. Число n называют мощностью множе­ ства A и пишут n = #A Мощность P(A) равна 2#A. 11 Определение 9 (Декартово произведение множеств). Декартовым произведением мно­ жеств A и B называют множество всех упорядоченных пар (x, y) таких, что x ∈ A и y ∈ B, т. е. A × B = {(x, y) | (x ∈ A) & (y ∈ B)} Пример 1. Пусть A = {0, 1, 2, {3, 4}}, B = {1, 2, 3, 4}. Тогда справедливы следующие соотношения. ∈ A {3, 4} ∈ A {3, 4} ∈ / B {3, 4} ⊆ B {3, 4} ⊂ B {1, 2, 3, 4} ⊆ B ∅ ⊆ B ∅ ⊂ B A+ B = {0, 1, 2, 3, 4, {3, 4}} A∩ B = {1, 2} B−A = {3, 4} P(B) = {∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, . . .} #A = 4 #B = 4 A× B = {(0, 1), (0, 2), (0, 3), (0, 4), (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), ({3, 4}, 1), ({3, 4}, 2), ({3, 4}, 3), ({3, 4}, 4)} B×B = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)} 1.2. Отношения на множествах Определение 10 (Бинарное отношение двух множеств). Бинарным отношением двух множеств называется любое подмножество их декартова произведения. Если R — бинарное отношение множеств A и B, то R ⊆ A× B. В таком случае мно­ жество A называют областью определения отношения R, а множество B — областью значений отношения R. 12 Если (x, y) ∈ R, то говорят, что x и y связаны отношением R и пишут xRy или y ∈ R(x). Определение 11 (Бинарное отношение на множестве). Если R ∈ A× A, то R называют бинарным отношением на множестве A. Пример 2. Рассмотрим множество A = {2, 3, 4, 5, 6, 7, 8, 9}. Рассмотрим отношение | на множестве A, заданное следующим образом: элементы x и y из множества A находятся в отношении |, если x является делителем y (т. е. 2|4, 3|6 и т. д.). Тогда |= {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)}. Пример 3. Рассмотрим множество A = {2, 3, 4, 5, 6, 7, 8, 9}. Рассмотрим отношение ≡3 на множестве A, заданное следующим образом: элементы x и y из множества A нахо­ дятся в отношении ≡3 , если остаток от деления x mod 3 равен остатку от деления y mod 3 (т. е. 2 ≡3 5, 3 ≡3 6 и т. д.). Тогда ≡3 = {(2, 2), (2, 5), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 7), (5, 2), (5, 5), (5, 8), (6, 3), (6, 6), (6, 9), (7, 4), (7, 7), (8, 2), (8, 5), (8, 8), (9, 3), (9, 6), (9, 9)}. Определение 12 (Степень отношения). Степень отношения R на множестве A опреде­ ляют следующим образом: 1) R0 = {(x, x) | ∀x ∈ A}; 2) R1 = R; 3) Rk = {(x, y) | ∃z ∈ A, xRz, zRk−1 y}. Пример 4. Рассмотрим множество A = {2, 3, 4, 5, 6}. Рассмотрим на этом множестве отношение R = {(2, 3), (3, 4), (4, 5), (5, 6)}. Тогда R0 = {(2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}; R1 = {(2, 3), (3, 4), (4, 5), (5, 6)}; R2 = {(2, 4), (3, 5), (4, 6)}; R3 = {(2, 5), (3, 6)}; R4 = {(2, 6)}; R5 = ∅. 13 Определение 13 (Рефлексивное отношение). Отношение R, заданное на множестве A, называют рефлексивным, если для каждого x ∈ A имеет место xRx. Определение 14 (Антирефлексивное отношение). Отношение R, заданное на множе­ стве A, называют антирефлексивным, если для каждого x ∈ A выполняется (x, x) ∈ / R. Определение 15 (Транзитивное отношение). Отношение R, заданное на множестве A, называют транзитивным, если для любых x, y, z ∈ A из выполнения соотношений xRy и yRz следует выполнение xRz. Определение 16 (Симметричное отношение). Отношение R, заданное на множестве A, называют симметричным, если для любых x, y ∈ A из выполнения соотношения xRy следует выполнение yRx. Определение 17 (Антисимметричное отношение). Отношение R, заданное на мно­ жестве A, называют антисимметричным, если для любых x, y ∈ A из выполнения соотношений xRy и yRx следует x = y. Определение 18 (Отношение эквивалентности). Отношение R, заданное на множе­ стве A, называют отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично. Пример 5. Отношение ≡3 из примера 3 является отношением эквивалентности, так как оно рефлексивно, транзитивно и симметрично. Отношение | из примера 2 не явля­ ется отношением эквивалентности: оно рефлексивно, транзитивно, но не симметрично. Определение 19 (Класс эквивалентности). Пусть R — отношение эквивалентности на множестве A. Классом эквивалентности, порожденным элементом a ∈ A называют def множество [a]R = {x ∈ A | xRa}. Совокупность всех классов эквивалентности отношения R на множестве A обозна­ чают [A]R . Пример 6. Для отношения ≡3 в примере 3 можно выделить три класса эквивалент­ ности: [1]≡3 = {4, 7}, [2]≡3 = {2, 5, 8}, [3]≡3 = {3, 6, 9}. Определение 20 (Замыкание отношения). Отношение RC называют замыканием отно­ шения R относительно заданного свойства если 14 1) RC обладает заданным свойством; 2) R ⊆ RC ; 3) для любого отношения T , для которого выполняются свойства 1 и 2, выпол­ няется соотношение #RC 6 #T . Часто рассматривают транзитивные и рефлексивные-транзитивные замыкания от­ ношений, т. е. замыкания отношений относительно соответственно свойства транзи­ тивности, и свойств рефлексивности и транзитивности. Лемма 1 (О транзитивном замыкании отношения). Транзитивным замыканием от­ ношения R на множестве A является отношение R+ = ∞ ⋃︁ Rk . k=1 Лемма 2 (О рефлексивном транзитивном замыкании отношения). Рефлексивным­ транзитивным замыканием отношения R на множестве A является отношение R* = ∞ ⋃︁ Rk . k=0 Пример 7. Рассмотрим отношение R = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)} на множе­ стве A = {2, 3, 4, 5, 6}. Степени Rk для k < 6, были приведены в примере 4. Для k > 6 Rk = ∅. Следовательно R+ = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (1, 3), (2, 4), (3, 5), (4, 6), R* = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (1, 4), (2, 5), (3, 6), (1, 5), (2, 6), (1, 6)}; (1, 3), (2, 4), (3, 5), (4, 6), (1, 4), (2, 5), (3, 6), (1, 5), (2, 6), (1, 6)}. Определение 21 (Отношение частичного порядка). Отношение R на множестве A называют отношением частичного порядка на A или порядком на A, если оно тран­ зитивно и антисимметрично. Определение 22 (Отношение рефлексивного порядка). Отношение порядка R на мно­ жестве A называют отношением рефлексивного порядка на A или нестрогим по­ рядком на A, если оно рефлексивно. Определение 23 (Отношение строгого порядка). Отношение порядка R на множестве A называют отношением строгого порядка на A или строгим порядком на A, если оно антирефлексивно. 15 Определение 24 (Отношение линейного порядка). Отношение порядка R на множестве A называют линейным порядком, если для любой пары различных элементов x, y ∈ A выполняется xRy или yRx. Пример 8. Отношение | в примере 2 является нестрогим частичным порядком на множестве A. Отношение ≡3 из примера 3 не является отношением порядка, так как отношение симметрично. Отношения < и 6 на множестве Z являются соответственно отношениями строгого и нестрогого линейного порядка на множестве Z. 2. Языки и операции над ними 2.1. Алфавит и цепочки Понятие символа интуитивно ясно. Строгого математического определения давать ему не будем. Под символом будем понимать букву, спецсимвол или токен, в зависи­ мости от обстоятельств. Определение 25 (Алфавит). Алфавитом называют конечное непустое множество сим­ волов. Определение 26 (Цепочка). Словом или цепочкой называют последовательность сим­ волов некоторого алфавита. Пример 9. Цепочка 011101 — цепочка в бинарном алфавите {0, 1}. Цепочка abacdadba — цепочка в алфавите {a, b, c, d}. Определение 27 (Пустая цепочка). Пустая цепочка — цепочка, не содержащая ни од­ ного символа. Эту цепочку можно рассматривать как цепочку в любом алфавите. Пустую цепочку будем обозначать ε. Определение 28 (Длина цепочки). Длиной цепочки называют число позиций в ней. Длину некоторой цепочки w обозначают |w|. Пример 10. Длина цепочки 011101 — |011101| = 6 . Длина цепочки abacdadba — |abacdadba| = 9. Длина цепочки ε — |ε| = 0. Определение 29 (Конкатенация). Пусть α и β — цепочки. Тогда αβ обозначает их кон­ катенацию (соединение), т. е. цепочку, в которой последовательно записаны сначала цепочки α, а затем символы цепочки β. Пример 11. Пусть α = 01101 и β = 110. Тогда αβ = 01101110, βα = 11001101. Для любой цепочки γ справедливы равенства εγ = γε = γ. Определение 30 (Подцепочка). Пусть α — цепочка, представимая в виде α = βγϕ, где β, γ, ϕ — некоторые цепочки. Тогда цепочки β, γ и ϕ называют подцепочками цепочки α. Подцепочку β называют префиксом цепочки α, а ϕ называют суффиксом цепочки α. Если β ̸= α, то β называют собственным префиксом. Если ϕ ̸= α, то ϕ называют собственным суффиксом. 17 Определение 31 (Степень алфавита). Пусть Σ — некоторый алфавит. Определим Σk как множество всевозможных цепочек длины k, состоящих из символов алфавита Σ. Пример 12. Заметим, что Σ0 = {ε} независимо от алфавита Σ, т. к. ε — единственная цепочка нулевой длины. Если Σ = {0, 1}, то Σ1 = Σ2 = Σ3 = {0, 1}, {00, 01, 10, 11}, {000, 001, 010, 011, 100, 101, 110, 111} ··· Множество всех слов над алфавитом Σ обозначают Σ* . Это множество можно определить как объединение всевозможных степеней алфа­ вита Σ: Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪ Σ3 ∪ . . . = ∞ ⋃︁ Σk . k=0 Множество всех непустых цепочек над алфавитом Σ обозначают Σ+ . По аналогии с Σ* множество всех непустых цепочек можно определить как Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪ . . . = ∞ ⋃︁ Σk . k=1 Определение 32 (Зеркальное отражение цепочки). Цепочку, в которой символы цепоч­ ки α выписаны в обратном порядке называют зеркальным отражением (инверсией) цепочки α . Результат зеркального отражения цепочки α обозначают αR . Пример 13. (011101)R = 101110; εR = ε; 1R = 1; (0123456789)R = 9876543210 2.2. Понятие языка Определение 33 (Язык). Множество L цепочек над фиксированным алфавитом Σ называют языком над этим алфавитом. Заметим, что язык над алфавитом Σ не обязательно должен содержать цепочки, в которые входят все символы алфавита Σ. Поэтому, если известно, что L — язык над Σ, то можно утверждать, что L — язык над любым алфавитом, содержащим все элементы Σ. 18 Пример 14. Рассмотрим несколько языков. 1. L = {ε, 01, 0011, 000111, 00001111, . . .} — язык над алфавитом {0, 1}, в каждом слове которого k единиц следуют за k нулями, для любого k > 0. 2. L = ∅ — пустой язык в любом алфавите. 3. L = {ε} — язык в любом алфавите, состоящий лишь из одного — пустого слова. 4. L = {ε, 01, 10, 0011, 1100, 1001, 0110, 0101, . . .} — язык над алфавитом {0, 1}, в словах которого равное количество единиц и нулей. Определение 34 (Конечный язык). Язык L называют конечным, если он содержит конечное число слов. В противном случае язык бесконечный. Единственное ограничение для множеств, которые могут быть языками, состоит в том, что все алфавиты конечны. Таким образом, хотя языки и могут содержать бесконечное число цепочек, но эти цепочки должны состоять из символов некоторого алфавита. 2.3. Операции над языками Так как языки представляют собой множества, то все операции над множествами можно перенести и на языки. Здесь приведем только дополнительные специфические операции. Определение 35 (Разность языков). Разностью двух языков L1 и L2 называют третий язык L3 , определенный следующим образом: L3 = {α | α ∈ L1 , α ∈ / L2 }. Пишут L3 = L1 − L2 . Определение 36 (Дополнение языка). Дополнением языка L над алфавитом Σ назы­ вают язык L′ , определенный следующим образом: L′ = Σ* − L. Пишут L′ =∼ L. Определение 37 (Конкатенация языков). Конкатенацией двух языков L1 и L2 назы­ вают третий язык L3 , определенный следующим образом: L3 = {αβ | α ∈ L1 , β ∈ L2 }. Пишут L3 = L1 L2 . 19 Пример 15. Пусть L1 = {01, 001}, L2 = {ε, 1, 00}. Тогда L1 L2 = {01, 011, 0100, 001, 0011, 00100}; L2 L1 = {01, 001, 101, 1001, 0001, 00001}. Определение 38 (Левое частное). Левым частным языков L1 и L2 называют третий язык L3 , определенный следующим образом: L3 = {β | αβ ∈ L1 , α ∈ L2 }. Пишут L3 = L2 ∖L1 . Стоит обратить внимание, что запись G∖H обозначает операцию левого частного в случае, если G и H — языки. Если G и H произвольные множества, то такая запись по определению 6 обозначает разность этих множеств. Для операции разности языков G и H используется только обозначение, данное в определении 35, т. е. G − H . Определение 39 (Правое частное). Правым частным языков L1 и L2 называют третий язык L3 , определенный следующим образом: L3 = {α | αβ ∈ L1 , β ∈ L2 }. Пишут L3 = L1 /L2 . Пример 16. Пусть L1 = {01, 001, 1001, 100}, L2 = {1, 00, 01}. Тогда L2 ∖L1 = {ε, 1, 001, 00}; L1 /L2 = {ε, 0, 00, 10, 100, 1}. Определение 40 (Степень языка). Понятие степени некоторого языка L определяют следующим образом: 1) L0 = {ε}; 2) L1 = L; 3) Lk+1 = Lk L. Пример 17. Если L = {01, 001}, то L0 ={ε}; L1 ={01, 001}; L2 ={0101, 01001, 00101, 001001}; L3 ={010101, 0101001, 0100101, 01001001, 0010101, 00101001, 00100101, 001001001}. 20 Определение 41 (Итерация языка). Итерацией языка L назовают множество L* все­ возможных слов, составленных из слов языка L. Другими словами L* = ∞ ⋃︁ Lk . k=0 Определение 42 (Регулярные операции). Операции объединения, конкатенации и ите­ рации называют регулярными операциями. Определение 43 (Положительная итерация языка). Положительной итерацией языка L назовают множество L+ всех слов, составленных из одного или более слов языка L. Другими словами L+ = ∞ ⋃︁ Lk . k=1 Положительную итерацию языка L можно определить формулой: L+ = LL* . Определение 44 (Зеркальное отражение языка). Зеркальным отражением (инверсией) языкa L назовают множество LR , составленное из инверсий слов языка L: LR = {a | aR ∈ L}. Определение 45 (Подстановка). Пусть L — язык над алфавитом Σ. Пусть для каждого символа a из Σ определен σ(a) — язык над некоторым алфавитом Σa . Доопределим σ(ε) = ε, σ(XY ) = σ(X)σ(Y ), X, Y ∈ Σ* . Такое отображение σ из Σ* в множество слов над алфавитом Σ′ , где ⋃︁ Σ′ = Σa , a∈Σ называют подстановкой. Для языка L результатом операции подстановки является язык L′ : L′ = {w | w ∈ σ(v), v ∈ L}. Пишут L′ = σ(L). Пример 18. Пусть над алфавитом {0, 1, 2} задан язык L = {00, 010, 1210}. Пусть для языка L задана подстановка σ: σ(0) = {0, 1}; σ(1) = {2}; σ(2) = {3, ε}. 21 Тогда σ(00) = σ(0)σ(0) = {0, 1}{0, 1} = {00, 01, 10, 11}; σ(010) = σ(0)σ(1)σ(0) = {0, 1}{2}{0, 1} = {020, 021, 120, 121}; σ(1210) = σ(1)σ(2)σ(1)σ(0) = {2}{3, ε}{2}{0, 1} = {2320, 2321, 220, 221}. Объединяя результаты подстановки в слова получим результат подстановки σ в язык L. σ(L) = {00, 01, 10, 11, 020, 021, 120, 121, 220, 221, 2320, 2321}. Пример 19. Пусть задан язык L = {00, 010, 1210, 210, 2220} над алфавитом {0, 1, 2}. Пусть для языка L задана подстановка σ: σ(0) = {1}; σ(1) = {ε}; σ(2) = {0}. Тогда σ(00) = σ(0)σ(0) = {1}{1} = {11}; σ(010) = σ(0)σ(1)σ(0) = {1}{ε}{1} = {11}; σ(1210) = σ(1)σ(2)σ(1)σ(0) = {ε}{0}{ε}{1} = {01}; σ(210) = σ(2)σ(1)σ(0) = {0}{ε}{1} = {01}; σ(2220) = σ(2)σ(2)σ(2)σ(0) = {0}{0}{0}{1} = {0001}. Объединяя результаты подстановки от всех слов исходного языка получим результат подстановки σ в язык L. σ(L) = {01, 11, 0001}. Определение 46 (Гомоморфизм). Подстановку, в которой #σ(a) = 1 для всex a ∈ Σ, называют гомоморфизмом. Очевидно, что подстановка в примере 19 является гомоморфизмом. 2.4. Способы задания языков Любой конечный язык можно задать перечислением всех его слов. Такая проце­ дура невозможна для бесконечных языков. Для таких языком необходима процедура, позволяющая определение языка конечными средствами. Существуют несколько способов задания языков. Все их можно разделить на три группы: спецификаторы свойств языка, конструкторы и распознаватели. Определение 47 (Спецификаторы свойств языка). Спецификаторы свойств языка — описания свойств, которым должно удовлетворять каждое слово языка. 22 К спецификаторам свойств языка можно отнести регулярные выражения, описание множеств слов с использованием предикатов. Определение 48 (Конструктор). Конструктор языка L — набор правил (абстрактное порождающее устройство), с помощью которого можно построить все и только все слова языка L. Т. о., с помощью конструктора языка L нельзя построить слово не принадлежащее языку L. К конструкторам языков относятся грамматики, синтаксические диаграммы, формы Бэкуса—Наура. Определение 49 (Распознаватель). Распознаватель языка L — абстрактное устройство (набор правил проверки), которое при получении на входе любого слова определяет принадлежность этого слова языку L. К распознавателям можно отнести конечные автоматы, линейно-ограниченные ав­ томаты, машины Тьюринга. Пример 20. Пусть L — язык над алфавитом {0, 1} определенный следующим образом: 1) ε ∈ L; 2) Если α ∈ L то 0α1 ∈ L; 3) Никакие другие слова не принадлежат L. Можно утверждать, что L = {0i 1i | i > 0}. (2.1) Действительно, из пункта 1 следует, что 00 10 ∈ L. Предполагая по индукции, что 0i 1i ∈ L, из 2 получаем 0i+1 1i+1 ∈ L. Следовательно множество в правой части равен­ ства (2.1) содержится в L. Предполагая, что 0i 1i единственное слово длины 2i в L, приходим к выводу, что 0i+1 1i+1 единственное слово длины 2(i + 1) в L. Т. к. L не содержит ни одного слова нечетной длины делаем заключение, что L содержится в правой части (2.1), т. е. равенство (2.1) имеет место. Заметим, что пункты 1-3 представляют собой описание порождающего устройства для языка L, а равенство (2.1) — спецификатор свойств языка. Пример 21. Пусть L1 — язык над алфавитом {0, 1} определенный следующим обра­ зом: 1) ε ∈ L1 ; 2) если α ∈ L то 0α1 ∈ L и 1α0 ∈ L1 ; 23 3) если α ∈ L1 и β ∈ L1 то αβ ∈ L1 ; 4) никакие другие слова не принадлежат L1 . Покажем, что L1 = {w ∈ {0, 1}* | N0 (w) = N1 (w)}. (2.2) Действительно, из пункта 1 следует, что ε, — слово в котором столько же нулей сколь­ ко и единиц, содержится в L1 . Рассуждая по индукции предположим, что L1 содер­ жит все слова длины 2i, в которых одинаковое количество нулей и единиц. Пусть w произвольное слово длины 2(i + 1) с таким же свойством. Без потери общности пред­ положим, что 1-й символ в w — символ 0. Если последний символ в w — 1, то тогда имеем w = 0w′ 1, где w′ — слово длины 2i с одинаковым числом нулей и единиц. Из 2 и предположения индукции следует, что w ∈ L1 . Если же последний символ в w — 0, то w = w′ w′′ , где w′ и w′′ — цепочки, длина которых не превышает 2i и в каждой из которых столько же нулей, сколько и единиц. Из 3 и предположения индукции следует, что w ∈ L1 . Отсюда следует, что (2.2) верно. Пример 22. Пусть L2 — язык над алфавитом {0, 1} состоящий из всевозможных слов, которые сворачиваются в ε последовательностью замен подцепочек 01 на ε. Ясно, что L2 является подмножеством языка L1 определенного в примере 21. Также очевидно, что L2 — собственное подмножество языка L1 , т. к. ни одно из слов 10, 0110 или 011001 не принадлежит L2 . Если в L2 заменить 0 и 1 соответственно на левую и правую скобки, то можно определить L2 как множество цепочек составленных из правильно сбалансированных скобок. Определение языка L2 может быть воспринято как описание распознавателя. 3. Системы текстовых замен Определение 50 (Система текстовых замен). Системой текстовых замен называется упорядоченная пара RW = (Ω, P) где 1) Ω — конечный алфавит; 2) P — конечное множество правил P ⊂ Ω* × Ω* , т. е. каждый элемент множества P — пара цепочек (α, β), где α и β — произ­ вольные цепочки над алфавитом Ω. Пару (α, β) ∈ P называют правилом замены или продукцией и обычно записывают в виде α → β. Определение 51 (Отношение непосредственной выводимости). Пусть α → β ∈ P — правило в системе текстовых замен RW = (Ω, P) , а γ, ϕ ∈ Ω* . Тогда говорят, что це­ почка γβϕ непосредственно выводится из γαϕ (или цепочка γαϕ непосредственно порождает цепочку γβϕ) по системе текстовых замен RW , и пишут γαϕ ⇒RW γβϕ. Отношение ⇒RW на множестве Ω* называют отношением непосредственной выводи­ мости в системе текстовых замен RW . Определение 52 (Отношение нетривиальной выводимости). Транзитивное замыкание отношения ⇒RW обозначают ⇒+ RW и называют отношением нетривиальной выводи­ мости в системе текстовых замен RW . Если α, β ∈ Ω* и α ⇒+ RW β, то говорят, что цепочка β выводится из α нетривиальным образом. Определение 53 (Отношение выводимости). Рефлексивное транзитивное замыкание отношения ⇒RW обозначают ⇒*RW и называют отношением выводимости в системе текстовых замен RW . Если α, β ∈ Ω* и α ⇒*RW β, то говорят, что цепочка β выводится из α. Определение 54 (Вывод цепочки). Если β выводится из α по системе текстовых замен RW , то последовательную запись α ⇒RW γ1 ⇒RW γ2 ⇒RW . . . ⇒RW γk ⇒RW β будем назвать выводом цепочки β из цепочки α. 25 Часто, когда известно о какой системе текстовых замен идет речь, имя системы текстовых замен (в нашем случае RW ) в вышеперечисленных обозначениях отноше­ ний будем опускать. Пример 23. Рассмотрим систему текстовых замен RW = (Ω, P), в которой Ω = {0, 1, 2, 3}, P = {01 → 210, 03 → 33, 123 → 021, ε → 0, 221 → 3}. В такой системе текстовых замен возможны выводы: 123 ⇒ 021 ⇒ 0201 ⇒ 02210 ⇒ 030 ⇒ 330; 3 ⇒ 03 ⇒ 33 ⇒ 033 ⇒ 333 ⇒ 0333 ⇒ 3333; 1232323 ⇒ 0212323 ⇒ 0202123 ⇒ 0202021 ⇒ ⇒ 02020201 ⇒ 020202210 ⇒ 0202030. Имея ввиду вышеприведенные выводы цепочек, можем написать 123 ⇒* 330; 3 ⇒* 3333; 1232323 ⇒* 0202030. Система текстовых замен может рассматриваться как конструктор языка и как распознаватель. Следующие определения демонстрируют это. Определение 55 (Язык, порожденный системой текстовых замен). Пусть задана си­ стема текстовых замен RW = (Ω, P) и определено некоторое множество AX ⊂ Ω* . Множество слов Lg (RW, AX) = {β | α ⇒* β, α ∈ AX}. называют языком порожденным системой текстовых замен RW с помощью множества аксиом AX. Определение 56 (Язык, допускаемый системой текстовых замен). Пусть задана си­ стема текстовых замен RW = (Ω, P) и определено некоторое множество AX ⊂ Ω* . Множество слов La (RW, AX) = {α | α ⇒* β, β ∈ AX} называют языком допускаемым системой текстовых замен RW с помощью множества аксиом AX. 26 Пример 24. Рассмотрим язык из примера 22. Этот язык может распознаваться си­ стемой текстовых замен RW = ({0, 1}, {01 → ε}) и может быть представлен в виде La (RW, {ε}). Пример 25. Рассмотрим язык из примера 20. Этот язык может быть определен с помощью системы текстовых замен RW = ({0, 1, S}, {S → ε, S → 0S1}) и может быть представлен в виде Lg (RW, {S}) ∩ {0, 1}* . (3.1) В данном случае система тестовых замен рассматривается как порождающее устрой­ ство. Пересечение в (3.1) означает, что из всех порождаемых системой текстовых за­ мен цепочек рассматриваются только те, что составлены из символов алфавита {0, 1} (отсекаются слова содержащие дополнительный символ S). Пример 26. Рассмотрим язык из примера 21. Этот язык может быть определен с помощью системы текстовых замен RW = ({0, 1, S}, {S → ε, S → 0S1, S → 1S0, S → SS}) и может быть представлен в виде Lg (RW, {S}) ∩ {0, 1}* . (3.2) В данном случае система тестовых замен рассматривается как порождающее устрой­ ство. Так же как и в предыдущем примере пересечение в (3.2) означает, что из всех порождаемых системой текстовых замен цепочек рассматриваются только те, в кото­ рых отсутствует символ S. 4. Грамматики 4.1. Формальное определение грамматики Определение 57 (Порождающая грамматика). Порождающей грамматикой называ­ ют четверку G = (N , Σ, P, S), где 1) N — алфавит нетерминальных символов; 2) Σ — алфавит терминальных символов (токенов); 3) P — конечное множество правил P ⊂ (N + Σ)* N (N + Σ)* × (N + Σ)* , т.е. каждый элемент множества P — пара цепочек (α, β), где α — произволь­ ная цепочка из терминальных и нетерминальных символов, содержащая в себе хотя бы один нетерминальный символ, а β — произвольная цепочка из терминальных и нетерминальных символов. Пару (α, β) обычно принято записывать в виде α → β. 4) S — нетерминальный символ из N , начальный символ грамматики. В последнем определении терминалы (элементы множества терминальных сим­ волов) представляют собой символы, из которых строятся цепочки языка. В свою очередь нетерминалы (элементы множества нетерминальных символов) играют роль переменных в грамматике. Начальный символ грамматики задает язык, определяемый грамматикой. Остальные нетерминалы играют роль вспомогательных переменных. Порождающая грамматика соответствует системе текстовых замен RW = (N ∪ Σ, P). Согласно этому соответствию можно определить отношения непо­ средственной выводимости и выводимости по грамматике как соответствующие отно­ шения по системе текстовых замен. Тогда язык, определенный порождающей грамма­ тикой G определяется как L(G) = Lg (RW, {S}) ∩ Σ* . Но можно провести независимое определение языка порожденного грамматикой. Определение 58 (Язык, порожденный грамматикой). Языком L(G), порожденным (опре­ деляемым) грамматикой G = (N , Σ, P, S), называют множество всех терминальных 28 цепочек (цепочек, состоящих только из терминальных символов), выводимых из на­ чального символа грамматики: L(G) = {γ ∈ Σ* | S ⇒G* γ}. Определение 59 (Эквивалентные грамматики). Две грамматики называются эквива­ лентными, если они определяют один и тот же язык. Пример 27. Рассмотрим грамматику G = (N , Σ, P, S), где N = {S}, Σ = {0, 1}, P = {S → 0S1, S → 01}. В этой грамматике всего лишь два правила и один нетерминальный символ. Цепочка 01 выводится из S, а следовательно эта цепочка принадлежит языку L(G). S ⇒ 0S1 ⇒ 00S11 ⇒ 000111, а следовательно S ⇒* 000111, а значит 000111 также принадлежит языку L(G). Можно показать что язык L(G) состоит из всех непустых цепочек, где последова­ тельность единиц стоит за последовательностью из такого же количества нулей. L(G) = {0k 1k | k > 0} Пример 28. Рассмотрим грамматику G = (N , Σ, P, A), где N = {A, B, C}, Σ = {a, b, c}, множество P состоит из правил: A → aABC A → abC CB → BC bB → bb bC → bc cC → cc Язык L(G) содержит цепочки вида an bn cn для каждого n > 1, т.к. мы можем ис­ пользовать первое правило n − 1 раз, чтобы получить A ⇒* an−1 A(BC)n−1 . Затем мы используем второе правило, чтобы получить A ⇒* an bC(BC)n−1 . Третье правило дает нам возможность расположить B и C так, чтобы все B предшествовали всем C. Таким образом A ⇒* an bBn−1C n . Затем, используя четвертое правило n − 1 раз, получаем A ⇒* an bnC n . Применим один раз пятое правило, получая A ⇒* an bn cC n−1 . Нако­ нец, применив n − 1 раз шестое правило, окончательно получаем A ⇒* an bn cn . Легко показать, что в общем случае возможен только такой порядок применения правил, т.е. L(G) = {an bn cn | n > 1}. 29 Пример 29. Рассмотрим грамматику G = (N , Σ, P, S), где N = {S, A, B}, Σ = {a, b}, а P задается правилами S → aB S → bA A→a A → aS A → bAA B→b B → bS B → aBB Можно показать, что эта грамматика определяет язык состоящий из цепочек, в которых одинаковое количество символов a и b. Замечание 3. Часто, для краткости, правила грамматики, имеющие одинаковую ле­ вую часть, будем объединять при записи в «одно» правило, у которого левая часть — левая часть исходных правил, а в правой части все правые части исходных правил, разделенные символом «|». Таким образом грамматика из примера 29 запишется сле­ дующим образом: S → aB | bA A → a | aS | bAA B → b | bS | aBB Пример 30. Рассмотрим грамматику G = (N , Σ, P, S), где N = {S, A, B, C, D}, Σ = {a, b}, а P задается правилами S → CD AD → aD Aa → aA Ab → bA BD → bD Ba → aB Bb → bB C → aCA | bCB | ε D→ε Можно показать, что эта грамматика определяет язык L(G) = {ww | w ∈ {a, b}* } Пример 31. Рассмотрим грамматику G = (N , Σ, P, S), где N = {S}, Σ = {a, b}, P = {S → aS, S → bS, S → a, S → b}. Эта грамматика определяет язык, состоящий из всех непустых цепочек над алфавитом {a, b}, т.е. L(G) = {a, b}+ . 30 Определение 60 (Аналитическая грамматика). Аналитической (распознающей) грам­ матикой называют четверку G = (N , Σ, P, S), где 1) N — алфавит нетерминальных символов; 2) Σ — алфавит терминальных символов (токенов); 3) P — конечное множество продукций P ⊂ (N + Σ)* × (N + Σ)* N (N + Σ)* ; 4) S — нетерминальный символ из N , заключительный (целевой, финальный, завершающий) символ грамматики. Аналитическая грамматика G соответствует системе текстовых замен RW = (N ∪ Σ, P) с языком L(G) = La (RW, {S}) ∩ Σ* . Можно определить язык, допускаемый аналитической грамматикой следующим обра­ зом. Определение 61 (Язык, допускаемый грамматикой). Языком L(G), определенным (до­ пускаемым) аналитической грамматикой G = (N , Σ, P, S), называют множество всех терминальных цепочек (цепочек, состоящих только из терминальных символов), из которых можно вывести заключительный символ грамматики: L(G) = {w ∈ Σ* | w ⇒* S}. Определение 62 (Двойственная грамматика). Пусть G = (N , Σ, P, S) — порождающая (аналитическая) грамматика. Пусть P ′ состоит из всех правил вида α → β, таких что β → α ∈ P. Тогда аналитическая (порождающая) грамматика G1 = (N , Σ, P ′ , S) называется двойственной для грамматики G Теорема 1 (О двойственной грамматике). Пусть для порождающей (аналитиче­ ской) грамматики G = (N , Σ, P, S) построена двойственная аналитическая (по­ рождающая) грамматика G1 = (N , Σ, P ′ , S). Тогда верно, что L(G) = L(G1 ). Доказательство. Пусть G — порождающая грамматика. Утверждаем, что для любого слова w ∈ (N + Σ)* S ⇒G* w ⇔ w ⇒G*1 S. (4.1) 31 Действительно, можно показать, что S ⇒G w1 ⇒G w2 ⇒G · · · ⇒G wk (4.2) wk ⇒G1 · · · ⇒G1 w2 ⇒G1 w1 ⇒G1 S. (4.3) тогда и только тогда, когда По определению P ′ это имеет место для k = 1. Рассуждая по индукции предположим, что утверждение истинно для некоторого k > 1, т. е. (4.2) имеет место тогда и только тогда, когда выполнено (4.3). Но wk ⇒G wk+1 тогда и только тогда, когда wk+1 ⇒G1 wk . Собирая последнее воедино, получим, что (4.1) верно, а следовательно верно и утверждение теоремы. Таким образом, сформулированные для порождающих грамматик утверждения справедливы для аналитических грамматик и наоборот. В дальнейшем, если особо не оговаривается, под термином «грамматика» будем понимать порождающие грамматики. 4.2. Классификация грамматик по Хомскому Существует классификация грамматик по четырем видам. Введем классификацию для порождающих грамматик. Двойственные им аналитические грамматики будут иметь вид исходных порождающих грамматик. Определение 57 описывает грамматику общего вида, или, другими словами, грамматику типа 0. Определение 63 (Грамматика типа 1). Грамматику G = (N , Σ, P, S) называют кон­ текстно-зависимой грамматикой (КЗ-грамматикой) или грамматикой типа 1, ес­ ли любое правило в ней имеет вид γ1 Aγ2 → γ1 αγ2 , где γ1 , γ2 ∈ (N + Σ)* , A ∈ N , α ∈ (N + Σ)+ . Также возможно присутствие правила S→ε при условии, что S не встречается в правых частях остальных правил. 32 Определение 64 (Грамматика типа 2). Грамматику G = (N , Σ, P, S) называют кон­ текстно-свободной грамматикой (КС-грамматикой) или грамматикой типа 2, ес­ ли любое ее правило имеет вид A → α, A ∈ N , α ∈ (N + Σ)* . Т. е. грамматика является грамматикой типа 2, если в любом ее правиле в левой части точно один символ — нетерминальный. КС-грамматики приведены в примерах 27, 29 и 31. Определение 65 (Грамматика типа 3). Грамматику G = (N , Σ, P, S) называют лево­ линейной грамматикой или грамматикой типа 3, если любое ее правило имеет вид A → Bα, или A → α, A, B ∈ N , α ∈ Σ* . Наряду с приведенной классификацией существует несколько определений до­ полнительных классов грамматик. С некоторыми из них мы познакомимся в рамках данного курса. Один из таких классов — неукорачивающие грамматики. Определение 66 (Неукорачивающие грамматики). Грамматику G = (N , Σ, P, S) назы­ вают неукорачивающей грамматикой, если для любого правила α → β ∈ P выпол­ няется |α| 6 |β|. Также возможно присутствие правила S→ε при условии, что S не встречается в правых частях остальных правил. Грамматика из примера 28 является неукорачивающей. Язык, определенный грамматикой, называют языком того же типа, что и грамма­ тика. Т. о. язык, определенный грамматикой типа 3, называют языком типа 3, а язык, определенный грамматикой типа 2, называют языком типа 2, или контекстно-свобод­ ным языком (КС-языком). Будем обозначать Li — класс языков типа i. 4.3. Свойства языков и грамматик Теорема 2 (О существовании эквивалентной грамматики с ограничением на наличие терминальных символов). Для любой грамматики G = (N , Σ, P, S) можно постро­ ить эквивалентную грамматику G′ = (N ′ , Σ, P ′ , S) такую, что каждое правило в 33 ′ ′ P , содержащее символы из Σ имеет вид A → a, где A ∈ N , a ∈ Σ. Более того, если G — грамматика типа 0, 1, 2 или неукорачивающая, то G′ также — грамматика типа 0, 1, 2 или неукорачивающая соответственно. Доказательство. Для каждого a ∈ Σ создадим новый нетерминал Aa и сформируем новое множество нетерминалов N ′ = N ∪ {Aa | a ∈ Σ} P ′ получается из P заменой во всех правилах терминалов a на соответствующие Aa , а также добавлением всевозможных правил Aa → a, a ∈ Σ. (4.4) Покажем, что для полученной грамматики G′ = (N ′ , Σ, P ′ , S) L(G) ⊆ L(G′ ). (4.5) Пусть непустое слово w = w1 w2 . . . wn ∈ L(G). Тогда можем вывести по грамматике ′ G сначала слово Aw1 Aw2 . . . Awn , a затем, используя (4.4) слово w. Если ε ∈ L(G), то вывод этого слова можно произвести в G′ . Значит (4.5) верно. Покажем, что L(G′ ) ⊆ L(G). (4.6) Определим гомоморфизм h из (N ′ + Σ)* в (N + Σ)* h(Aa ) = h(X) = a, X, a ∈ Σ, X ∈ N ∪ Σ. Пусть α ⇒G′ β. Если такой вывод был произведен с помощью правила Aa → a, то h(α) = h(β). Иначе, h(α) ⇒G h(β). В любом случае h(α) ⇒G* h(β). Отсюда, если w ∈ L(G′ ), то S = h(S) ⇒G* h(w) = w, откуда w ∈ L(G), что доказывает (4.6). Преобразования, проведенные для получения грамматики G′ не выводят грамма­ тику из того класса, к которому относилась грамматика G. Т. е. G′ — грамматика типа 0, 1, 2 или неукорачивающая, если грамматика G является таковой. Т. о. утверждение теоремы. доказано. 34 Пример 32. Рассмотрим грамматику G = (N , Σ, P, A), где N = {A, B, C}, Σ = {a, b, c}, множество P состоит из правил: A → aABC A → abc CB → BC bB → bb bC → bc cC → cc Построим новую грамматику так, как это определено в доказательстве теоремы 2. Для каждого терминального символа введем соответствующий ему новый нетер­ минальный символ с дополнительным новым правилом. D→a E→b F → c. (4.7) Подставим новые символы в исходные правила вместо соответствующих терминаль­ ных. Получим A → DABC A → DEF CB → BC EB → EE EC → EF FC → F F (4.8) Получим новую грамматику G′ = (N ′ , Σ, P ′ , A), где N ′ = {A, B, C, D, E, F }, P ′ состоит из всех правил перечисленных в (4.7) и (4.8). Теорема 3 (О неукорачиваемости контекстно-зависимых языков). Классы языков L1 и неукорачивающих эквивалентны. Доказательство. Так как по определению любая грамматика типа 1 является неуко­ рачивающей, для доказательства теоремы достаточно показать, что для любой неуко­ рачивающей грамматики найдется эквивалентная грамматика типа 1. Пусть дана произвольная неукорачивающая грамматика G = (N , Σ, P, S). По тео­ реме 2 можем предположить, что терминальные символы не встречаются в левых частях правил грамматики. Пусть #P = n 35 ′ ′ Построим новую грамматику G с множеством правил P , определенным следую­ щим образом. 1. Если S → ε ∈ P, то S → ε ∈ P ′ . 2. Если γ1 Aγ2 → γ1 αγ2 ∈ P, где γ1 , γ2 ∈ (N + Σ)* , A ∈ N , α ∈ (N + Σ)+ , то γ1 Aγ2 → γ1 αγ2 ∈ P ′ . 3. Если i-e правило в P не подходит под определение правила в пункте 2 и имеет вид X1 X2 . . . Xk−1 Xk → Y1Y2 . . . Yl−1Yl , ′ то в P включаем набор правил X1 X2 X3 . . . Xk−1 Xk → Zi1 X2 X3 . . . Xk−1 Xk , Zi1 X2 X3 . . . Xk−1 Xk → Zi1 Zi2 X3 . . . Xk−1 Xk , Zi1 Zi2 X3 . . . Xk−1 Xk → Zi1 Zi2 Zi3 . . . Xk−1 Xk , ··· Zi1 Zi2 Zi2 . . . Zi k−1 Xk → Zi1 Zi2 Zi3 . . . Zi k−1 Zik , Zi1 Zi2 Zi3 . . . Zi k−1 Zik → Y1 Zi2 Zi3 . . . Zi k−1 Zik , Y1 Zi2 Zi3 . . . Zi k−1 Zik → Y1Y1 Zi3 . . . Zi k−1 Zik , Y1Y2 Zi3 . . . Zi k−1 Zik → Y1Y1Y3 . . . Zi k−1 Zik , ··· Y1Y2 Zi3 . . . Yk−1 Zik → Y1Y1Y3 . . . Yk−1Yk . . . Yl , где Zij — новые нетерминалы. Пусть NZ — множество, составленное из всех символов Zij , введенных на шаге 3. Тогда грамматика G′ = (N ′ , Σ, P ′ , S), где N ′ = N ′ ∪ NZ , будет определять тот же язык, что и исходная неукорачивающая грамматика. Более того, по определению, получившаяся грамматика является контекстно-зависимой. Пример 33. Рассмотрим грамматику, полученную в предыдущем примере. Грамматика G′ = (N ′ , Σ, P ′ , A), где N ′ = {A, B, C, D, E, F }, Σ = {a, b, c}, P ′ состоит из правил: A → DABC A → DEF CB → BC EB → EE EC → EF FC → F F D→a E→b F → c. 36 Данная грамматика является неукорачивающей, но не является грамматикой типа 1 из-за наличия в ней правила CB → BC. В соответствии с алгоритмом преобразования, предложенным в доказательстве последней теоремы это правило в новой грамматике будет заменено на правила CB → Z31 B Z31 B → Z31 Z32 Z31 Z32 → BZ32 BZ32 → BC Так как все остальные правила удовлетворяют условиям, накладываемым на кон­ текстно-зависимые грамматики, то их можно оставить без изменения. Новая грамма­ тика G′′ = (N ′ ∪ {Z31 , Z32 }, Σ, P ′′ , A), где P ′′ состоит из правил A → DABC A → DEF CB → Z31 B Z31 B → Z31 Z32 Z31 Z32 → BZ32 BZ32 → BC EB → EE EC → EF FC → F F D→a E→b F → c, является контекстно-зависимой грамматикой и определяет тот же язык, что и грам­ матика G′ . Теорема 4 (Классификация конечных языков). Любой из классов языков Li , 0 6 i 6 3, содержит все конечные языки. Доказательство. Пусть w1 , w2 , . . . , wn набор слов над алфавитом Σ. Тогда граммати­ ка G1 = ({S}, Σ, {S → w1 , S → w2 , . . . , S → wn }, S) порождает язык L(G1 ) = {w1 , w2 , . . . , wn }. Грамматика G2 = ({S}, Σ, {S → S}, S) 37 порождает пустой язык L(G2 ) = ∅. Как грамматика G1 , так и грамматика G2 подходит под определение грамматики любого типа. Следовательно теорема доказана. Пример 34. Пусть дан конечный язык L = {ε, a, ab, abaa}. Пользуясь методом, представленным в доказательстве теоремы 4 для него можно определить грамматику G = (N , Σ, P, S), где N = {S}, Σ = {a, b} и множество P представлено правилами S → ε | a | ab | abaa. Полученная грамматика удовлетворяет ограничениям, накладываемым на любой из типов грамматик, а значит данный язык можно отнести классу языков любого типа. Теорема 5 (О замкнутости класса L3 относительно регулярных операций). Класс языков L3 замкнут относительно регулярных операций. Доказательство. Пусть L и L′ определены с помощью грамматик G = (N , Σ, P, S), G′ = (N ′ , Σ′ , P ′ , S′ ), соответственно. Пусть N ∩ N ′ = ∅ (в противном случае можем переименовать нетерминалы одного из множеств). Тогда язык L ∪ L′ определяется грамматикой G1 = (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → S, S0 → S′ }, S0 ). Действительно, любое слово языка L выводится из S. Следовательно его можно вывести и из S0 . Аналогично, любое слово языка L′ можно вывести из S0 . Т. е. любое слово объединения L ∪ L′ можно вывести из S0 . С другой стороны, так как в грамма­ тиках G и G′ нет одинаковых нетерминалов, при выводе слова из S по грамматике G1 невозможно получить цепочку, содержащую нетерминальные символы из N ′ , т. е. при 38 таком выводе нельзя применить ни одного правила из P ′ . Аналогично, при выводе це­ почки из нетерминала S′ по грамматике G1 невозможно применить ни одного правила из P. Следовательно из нетерминала S0 можно вывести только слова из L(G1 ) ∪ L(G2 ). Заменим в P ′ каждое правило вида A → α, A ∈ N ′ , α ∈ Σ′* (4.9) на правило A → Sα. Обозначим полученное множество правил через P1 . Тогда грам­ матика типа 3 G2 = (N + N ′ , Σ + Σ′ , P ∪ P1 , S′ ) порождает язык LL′ . В самом деле, если β ∈ L′ , то существует вывод S′ ⇒G′ β. Вследствие произве­ денной замены правил вида (4.9), имеет место вывод по грамматике G2 S′ ⇒G2 Sw. Значит, для любого слова α ∈ L выполняется S′ ⇒G*2 Sβ ⇒G*2 αβ. Т. к. слово β взято произвольным, все слова конкатенации LL′ можно вывести по грамматике G2 из S′ . Более того, легко убедиться, что никакие другие слова не выводятся по грамматике G2 из S′ . Заменим в P ′ каждое правило вида (4.9) на правило вида A → S′ α и обозначим полученное множество правил через P2 . Тогда грамматика типа 3 G3 = (N ′ + {S0 }, Σ′ , P ′ ∪ P2 ∪ {S0 → ε, S0 → S′ }, S0 ) порождает язык L′* . По грамматике G3 возможны выводы S0 ⇒G3 ε; S0 ⇒G3 S′ ; S′ ⇒G*3 α, ′ ⇒G*3 ′ S S α, ∀α ∈ L′ ; ∀α ∈ L′ . Собирая все воедино получаем, что из S0 можно вывести любое слово, составленное из слов языка L′ , т. е. L(G3 ) = L′* . Пример 35. Рассмотрим две грамматики. 39 G1 = ({S, A, B}, {0, 1, 2}, P1 , S), с множеством продукций P1 : S → A11 | B0 A → S01 | 1 B → A0 | B2 G2 = ({E, C, D}, {0, 1, 2}, P2 , E), с множеством продукций P2 : E → C0 | ε C → C1 | D2 D → E0 | 2 В соответствии с доказательством последней теоремы объединение языков L(G1 ) ∪ L(G2 ) будет определять грамматика G3 = ({S0 , S, A, B, C, D, E}, {0, 1, 2}, P3 , S0 ), в которой P3 представлено продукциями: S0 → S | E S → A11 | B0 A → S01 | 1 B → A0 | B2 C → C1 | D2 D → E0 | 2 E → C0 | ε Для конкатенации языков L(G1 )L(G2 ) преобразуем правила грамматики G2 , не со­ держащие нетерминальных символов в правой части E→ε D→2 (4.10) E→S D → S2 (4.11) в правила Объединив правила грамматики G1 с модифицированным множеством правил грамма­ тики G2 , получим грамматику G4 = ({S, A, B, C, D, E}, {0, 1, 2}, P4 , E), где P4 — множе­ ство правил: S → A11 | B0 A → S01 | 1 B → A0 | B2 C → C1 | D2 D → E0 | S2 E → C0 | S 40 Преобразуя правила (4.10) так как сказано в последней части доказательства тео­ ремы 5 получим новые правила E→E D → E2 Внесём новый начальный нетерминальный символ и добавим два правила для него, после чего объединяем новые правила с правилами грамматики G2 . Получим множество правил P5 : S0 E C D →ε|E → C0 | E | ε → C1 | D2 → E0 | E2 | 2 Грамматика G5 = ({S0 , E, C, D}, {0, 1, 2}, P5 , S0 ) определяет итерацию L(G2 )* Аналогичным образом можно найти грамматику для итерации L(G1 )* : G6 = ({S0 , S, A, B}, {0, 1, 2}, P6 , S0 ), с множеством продукций P6 : S0 → ε | S S → A11 | B0 A → S01 | S1 | 1 B → A0 | B2 Теорема 6 (О замкнутости класса L2 относительно регулярных операций). Класс языков L2 замкнут относительно регулярных операций. Доказательство. Пусть L и L′ определены с помощью грамматик G = (N , Σ, P, S), G′ = (N ′ , Σ′ , P ′ , S′ ), соответственно. Пусть N ∩ N ′ = ∅ (в противном случае можем переименовать нетерминалы одного из множеств). Тогда язык L ∪ L′ определяется грамматикой (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → S, S0 → S′ }, S0 ). Язык LL′ определяется грамматикой типа 2 (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → SS′ }, S0 ). 41 * Язык L определяется грамматикой типа 2 (N + {S0 }, Σ, P ∪ {S0 → ε, S0 → S0 S}, S0 ). Методы построения грамматик для конкатенации и итерации языков типа 2 несколько проще, чем подобные методы для языков типа 3. Такое упрощение свя­ зано с тем, что грамматики типа 3 — это грамматики типа 2 с дополнительными ограничениями, и такие ограничения не выполняются при построении грамматик в доказательстве последней теоремы. Действительно, рассмотрим грамматики G1 и G2 из примера 35 и построим сначала грамматику для конкатенации L(G1 )L(G2 ) методом, предложенным в доказательстве теоремы 6. Для этого объединяем все правила исход­ ных грамматик и добавляем правило для нового начального нетерминала. Получим грамматику со следующим набором правил: S0 → SE S → A11 | B0 A → S01 | 1 B → A0 | B2 E → C0 | ε C → C1 | D2 D → E0 | 2, где S0 — новый начальный нетерминал. Так как исходные грамматики можно было отнести ко 2-му типу, полученная грамматика определяет конкатенацию определенных ими языков. Но из-за первого правила построенную грамматику нельзя отнести к типу 3. Поэтому такое построение не доказывает факта, что конкатенация языков типа 3 есть язык типа 3. Аналогичная ситуация имеет место при применении метода построения грамма­ тики для итерации языка, предложенного в доказательстве теоремы 6 к грамматике типа 3. Построим этим методом грамматику для (L(G1 ))* . Получим грамматику с набором правил: S0 → ε | S0 S S → A11 | B0 A → S01 | 1 B → A0 | B2, где S0 — новый начальный нетерминал. Как и в предыдущем случае из за правила S0 → S0 S данную грамматику нельзя отнести к типу 3. 42 Теорема 7 (О замкнутости класса L1 относительно регулярных операций). Класс языков L1 замкнут относительно регулярных операций. Доказательство. Пусть L и L′ определены с помощью грамматик G = (N , Σ, P, S), G′ = (N ′ , Σ′ , P ′ , S′ ), соответственно. По теореме 2 можем предположить, что терминальные символы не встречаются в левых частях правил грамматик. Кроме того, пусть N ∩ N ′ = ∅ (в противном случае можем переименовать нетерминалы одного из множеств). Тогда, если ε ∈ / L ∪ L′ , то язык L ∪ L′ определяется грамматикой (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → S, S0 → S′ }, S0 ). (4.12) Если ε ∈ L∪L′ , рассмотрим языки L−{ε} и L′ −{ε}. Для них определим граммати­ ку по (4.12), после чего добавляем новый начальный нетерминал S1 и дополнительные правила S1 → S0 и S1 → ε. Полученная грамматика определяет язык L ∪ L′ . Предположим, что ε ∈ / L ∪ L′ . Тогда грамматика типа 1 (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → SS′ }, S0 ) (4.13) порождает язык LL′ . Действительно, очевидно, что каждое слово в LL′ может быть выведено по (4.13). C другой стороны, если S0 ⇒ γ1 ⇒ γ2 · · · ⇒ γu вывод по (4.13), тогда любая из γj может быть представлена в форме γj = ϑj ϑ′j , где S ⇒G* ϑj и S′ ⇒G*′ ϑ′j . Это можно доказать по индукции. Ясно, что γ1 = SS′ находится в такой форме. Если же γk в данной форме, то γk+1 также в данной форме, т. к. левые части правил грамматик не содержат терминальных символов, а множества нетерминальных символов не пересекаются. Значит, только слова из LL′ порождаются грамматикой (4.13). Пусть ε ∈ L ∪ L′ . Обозначим L1 = L − {ε}, L′1 = L′ − {ε}. Очевидно, что LL′ это один из следующих языков L1 L′1 ∪ L1 , L1 L′1 ∪ L′1 , L1 L′1 ∪ L1 ∪ L′1 ∪ {ε}. 43 Т. к. класс L1 замкнут относительно объединения, а в конкатенации участвуют языки без пустого слова, то весь L1 замкнут относительно конкатенации. Т. к. (L ∪ {ε})* = L* , можем, не теряя общности предположить, что L не содержит ε. Действительно, если ε ∈ L(G), мы всегда можем построить грамматику G1 такую, что L(G1 ) = L(G) − {ε} (просто удаляем правило S → ε). В таком случае, грамматика (N + {S0 , S1 }, Σ, P∪{S0 → ε, S0 → S, S0 → S1 S} ∪{S1 a → S1 Sa | a ∈ Σ} (4.14) ∪{S1 a → Sa | a ∈ Σ}, S0 ) порождает язык L* . Действительно, легко видеть, что любое слово в L* порождается (4.14). C другой стороны, рассмотрим произвольный вывод S0 ⇒ γ1 ⇒ γ2 · · · ⇒ γu , u>1 согласно (4.14). Если γ1 = ε или γ1 = S, то в результате вывода можно получить только слова из L и, следовательно, γu ∈ L* . В противном случае, γ1 = S1 S и каждая цепочка γj находится в одной из следующих форм 1. S1 ϕ1 . . . ϕv , v > 1, где первый символ в цепочках ϕ2 , . . . , ϕv терминальный и S ⇒G* ϕν , ν = 1, . . . , v; 2. ϕ1 . . . ϕv , v > 1, где первый символ в цепочках ϕ2 , . . . , ϕv терминальный и S ⇒G* ϕν , ν = 0, . . . , v. Это можно показать по индукции. Пусть γj в форме 1 или 2. Из вида продукций в (4.14) и из того, что терминалы не встречаются в правых частях правил следует, что γj+1 также в форме 1 или 2. Отсюда следует, что только цепочки из L* могут быть выведены по (4.14). Пример 36. В доказательстве последней теоремы для построения грамматики для итерации языка типа 1 предлагается более сложный метод, чем был предложен в до­ казательстве теоремы 6 (для итерации языка типа 2). Связано это с тем, что при применении упомянутого метода к произвольной грамматике типа 1 может быть по­ лучена грамматика, определяющая не только слова из итерации языка. Например, рассмотрим грамматику G = (N , Σ, P, S), 44 где N = {S, A, B}, Σ = {a, b, c} и множество P представлено правилами S → ABcB AB → Aa Aa → aa AB → CB CB → CD CD → BD BD → BA BA → Bb Bb → bb B → c. Данная грамматика — грамматика типа 1. Легко проверить, что она определяет конеч­ ный язык L(G) = {aacc, bbcc}. (4.15) Если построить грамматику для итерации этого языка методом из доказательства теоремы 6, получим грамматику с правилами S0 → ε | S0 S S → ABcB AB → Aa Aa → aa AB → CB CB → CD CD → BD BD → BA BA → Bb Bb → bb B → c. Любое слово из (L(G))* определяется этой грамматикой. Действительно, С помощью правил для S0 можно получить цепочку из любого количества символов S, каждый из которых можно заменить по правилам исходной грамматики на слово языка L(G). Но для построенной грамматики также возможен вывод: S0 ⇒ S0 S ⇒ S0SS ⇒ SS ⇒ ABcBS ⇒ ABcBABcB ⇒ ABcBbBcB ⇒ ABcbbBcB ⇒ ABcbbccB ⇒ ABcbbccc ⇒ Aacbbccc ⇒ aacbbccc. (4.16) Если предположить, что построенная грамматика определяет итерацию языка L(G), то последний вывод показывает, что цепочка aacbbccc принадлежит итерации и сле­ 45 довательно должна представлять из себя конкатенацию слов языка L(G), но из (4.15) следует, что это не так. Применяя подобный метод, предложенный в теореме 7 получим грамматику с правилами: S0 → ε | S | S1 S S1 a→ S1 Sa | Sa S1 b → S1 Sb | Sb S1 c → S1 Sc | Sc S → ABcB AB → Aa Aa → aa AB → CB CB → CD CD → BD BD → BA BA → Bb Bb → bb B → c. Легко убедиться, что с помощью правил этой грамматики можно построить только слова из итерации языка L(G), и вывод подобный 4.16 — невозможен. Теорема 8 (О замкнутости класса L0 относительно регулярных операций). Класс языков L0 замкнут относительно регулярных операций. Доказательство. Пусть L и L′ определены с помощью грамматик G = (N , Σ, P, S), G′ = (N ′ , Σ′ , P ′ , S′ ), соответственно. По теореме 2 можем предположить, что терминальные символы не встречаются в левых частях правил грамматик. Кроме того, пусть N ∩ N ′ = ∅ (в противном случае можем переименовать нетерминалы одного из множеств). Тогда язык L ∪ L′ определяется грамматикой (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → S, S0 → S′ }, S0 ). Грамматика типа 0 (N + N ′ + {S0 }, Σ + Σ′ , P ∪ P ′ ∪ {S0 → SS′ }, S0 ) порождает язык LL′ . (4.17) 46 Действительно, очевидно, что каждое слово в LL′ может быть выведено по (4.17). C другой стороны, если S0 ⇒ γ1 ⇒ γ2 ⇒ · · · ⇒ γu вывод по (4.17), тогда любая из γj может быть представлена в форме γj = ϑj ϑ′j , где S ⇒G* ϑj и S′ ⇒G*′ ϑ′j . Это можно доказать по индукции. Ясно, что γ1 = SS′ находится в такой форме. Если же γk в данной форме, то γk+1 также в данной форме, т. к. левые части правил грамматик не содержат терминальных символов. А значит, только слова из LL′ порождаются грамматикой (4.17). Т. к. (L∪ {ε})* = L* , можем, не теряя общности, предположить, что L не содержит ε. Действительно, если ε ∈ L(G), мы всегда можем построить грамматику G1 такую, что L(G1 ) = L(G) − {ε} (заменим каждое правило α → ε на правила xα → x и αx → x, для всех x ∈ (N + Σ)). В таком случае, грамматика (N + {S0 , S1 }, Σ, P∪{S0 → ε, S0 → S, S0 → S1 S} ∪{S1 a → S1 Sa | a ∈ Σ} (4.18) ∪{S1 a → Sa | a ∈ Σ}, S0 ) порождает язык L* . Действительно, легко видеть, что любое слово в L* порождается (4.18). C другой стороны, рассмотрим произвольный вывод S0 ⇒ γ1 ⇒ γ2 · · · ⇒ γu , u>1 согласно (4.18). Если γ1 = ε или γ1 = S, то в результате вывода можно получить только слова из L и, следовательно, γu ∈ L* . В противном случае, γ1 = S1 S и каждая цепочка γj находится в одной из следующих форм 1) S1 ϕ1 . . . ϕv , v > 1, где первый символ в цепочках ϕ1 , . . . , ϕv терминальный и S ⇒G* ϕν , ν = 1, . . . , v; 2) ϕ1 . . . ϕv , v > 1, где первый символ в цепочках ϕ1 , . . . , ϕv терминальный и S ⇒G* ϕν , ν = 0, . . . , v. Это можно показать по индукции. Пусть γj в форме 1 или 2. Из вида продукций в (4.18) и из того, что терминалы не встречаются в правых частях правил следует, что γj+1 также в форме 1 или 2. Отсюда следует, что только цепочки из L* могут быть выведены по (4.18). 47 Теорема 9 (О замкнутости классов языков относительно положительной итерации). Любой из классов языков Li , 0 6 i 6 3, замкнут относительно операции положи­ тельной итерации. Утверждение теоремы напрямую следует из замкнутости классов языков относи­ тельно регулярных операций, т. к. L+ = LL* . Теорема 10 (О замкнутости классов языков относительно зеркального отражения). Любой из классов языков Li , 0 6 i 6 2, замкнут относительно операции зеркаль­ ного отражения. Доказательство следует из того факта, что если в грамматике типа i (0 6 i 6 2) поменять каждое правило α→β на правило αR → β R , то получим грамматику, определяющую зеркальное отражение исходного языка, от­ носящуюся к тому же классу, что и первоначальная. Теорема 11 (О замкнутости L0 и L2 относительно подстановки). Классы языков L0 и L2 замкнуты относительно подстановки. Доказательство. Рассмотрим класс L2 . Пусть L = L(G), где G = (N , Σ, P, S), Σ = {a1 , . . . , ar }. Пусть σ — подстановка такая, что σ(ai ), 1 6 i 6 r порождается грамматикой типа 2 Gi = (Ni , Σi , Pi , Si ). Предположим, что множества нетерминалов всех введенных грамматик попарно не пересекаются. Обозначим через P0 множество правил, полученное из P заменой ai на Si . Тогда грамматика (N ∪ N1 ∪ · · · ∪ Nr , Σ1 ∪ · · · ∪ Σr , P0 ∪ · · · ∪ Pr , S) — грамматика типа 2, порождающая язык σ(L). 48 Рассмотрим класс L0 . Пусть L = L(G), где G = (N , Σ, P, S), Σ = {a1 , . . . , ar }. Пусть σ — подстановка такая, что σ(ai ), 1 6 i 6 r порождается грамматикой типа Gi = (Ni , Σi , Pi , Si ). Предположим, что множества нетерминалов всех введенных грамматик попарно не пересекаются. Для каждого терминального символа ai ∈ Σ введем новый нетерминал Ai . Кроме этого введем два новых нетерминала X0 и X. Обозначим через P0 множество правил, полученное из P заменой всех терминаль­ ных символов ai на новый нетерминал Ai . Возьмем новый нетерминал X и обозначим P ′ = {XAi → XSi | 1 6 i 6 r} P ′′ = {Xa → aX | a ∈ Σ1 ∪ · · · ∪ Σr } Тогда грамматика (N ∪ N1 ∪ · · · ∪ Nr ∪ {X, X0 }, Σ1 ∪ · · · ∪ Σr , P0 ∪ · · · ∪ Pr ∪ P ′ ∪ P ′′ ∪ {X0 → XS, X → ε}, X0 ) — грамматика типа 0, порождающая язык σ(L). Следствие 11.1. Классы языков L0 и L2 замкнуты относительно гомоморфизма. Теорема 12 (О замкнутости класса L0 относительно пересечения). Класс языков L0 замкнут относительно пересечения. Доказательство. Пусть L = L(G) и L′ = L(G′ ), где G = (N , Σ, P, S), грамматики типа 0. G′ = (N ′ , Σ′ , P ′ , S′ ). 49 Рассмотрим грамматику G1 = (N ∪ N ′ ∪ N1 , Σ ∪ Σ′ , P ∪ P ′ ∪ P1 , X0 ), где N1 = {Aa | a ∈ Σ ∪ Σ′ } ∪ {X0 , X1 , X2 } — новые нетерминалы, a P1 состоит из правил X0 → X1 SX2 S′ X1 (4.19) ′ X2 a → Aa X2 a∈Σ∪Σ (4.20) bAa → Aa b a, b ∈ Σ ∪ Σ′ (4.21) a ∈ Σ ∪ Σ′ (4.22) X1 Aa a → aX1 X1 X2 X1 → ε (4.23) Используя (4.19) и продукции из P ∪ P ′ , все цепочки формы X1 wX2 w′ X1 , w ∈ L, w′ ∈ L′ (4.24) могут быть выведены из X0 . По (4.20)-(4.22), цепочка wX1 X2 X1 (4.25) выводится из (4.24) тогда и только тогда когда w = w′ . По (4.23) слово w выводится из (4.25). Т. к. только таким образом можно получить из X0 терминальную цепочку, делаем заключение, что L(G1 ) = L ∩ L′ . 5. Иерархия автоматов 5.1. Конечные автоматы 5.1.1. Конечные детерминированные автоматы Определение 67 (Конечный детерминированный автомат). Систему текстовых замен M = (Ω, P) называют конечным детерминированным автоматом (КДА) если 1) в алфавите Ω можно выделить два алфавита Q и Σ, называемые соответствен­ но множеством символов состояний (множеством состояний) и множеством входных сигналов (входным алфавитом), причем Q ∩ Σ = ∅, Q ∪ Σ = Ω; 2) в множестве Q выделяется элемент q0 , называемый начальным (стартовым) состоянием, и подмножество F — множество заключительных состояний; 3) любая продукция в P имеет вид qa → r, q, r ∈ Q, a ∈ Σ, (5.1) и более того, для любой пары (q, a), где q ∈ Q и a ∈ Σ в P присутствует точно одна продукция вида (5.1). Таким образом, для определения КДА достаточно определить пять компонент (Q, Σ, P, q0 , F ). По другому КДА можно определить как пятерку M = (Q, Σ, δ, q0 , F ), где Q, Σ, q0 , F обозначают те же объекты, что и в последнем определении, а эле­ мент δ, называемый функцией переходов, можно представить как отображение вида δ : Q × Σ → Q, что соответствует набору продукций из P. Отношение выводимости ⇒* для КДА имеет общий вид отношения выводимости в системах текстовых замен. Определение 68 (Язык допускаемый КДА). Язык определенный (допускаемый, рас­ познаваемый) КДА M = (Q, Σ, P, q0 , F ) есть множество слов L(M) = {w ∈ Σ* | q0 w ⇒* q, q ∈ F }. 5.1.2. Конечные недетерминированные автоматы Определение 69 (Конечный недетерминированный автомат). Система текстовых замен M = (Ω, P) называется конечным недетерминированным автоматом (НКА) если 1) в алфавите Ω можно выделить два алфавита Q и Σ, называемые соответствен­ но множеством символов состояний (множеством состояний) и множеством входных сигналов (входным алфавитом), причем Q ∩ Σ = ∅, Q ∪ Σ = Ω; 51 2) в множестве Q выделяется подмножество S называемое множеством началь­ ных (стартовых) состояний и подмножество F — множество заключительных состояний; 3) любая продукция в P имеет вид qa → r, q, r ∈ Q, a ∈ Σ. По аналогии с КДА можно определить НКА как пятерку M = (Q, Σ, P, S, F ) или пятерку M = (Q, Σ, δ, S, F ), в которой Q, Σ, S, F обозначают те же объекты, что и в определении НКА, а функцию переходов δ можно представить как отображение вида δ : Q × Σ → P(Q), что соответствует набору продукций из P. Отношение выводимости ⇒* для НКА имеет общий вид отношения выводимости в системах текстовых замен. Определение 70 (Язык допускаемый НКА). Язык определенный (допускаемый, рас­ познаваемый) НКА M = (Q, Σ, P, S, F ) есть множество слов L(M) = {w ∈ Σ* | q0 w ⇒* q, q0 ∈ S, q ∈ F } 5.1.3. Способы описания конечных автоматов Функцию переходов конечного автомата обычно представляют в виде таблицы, называемой таблицей переходов. Определение 71 (Таблица переходов). Для конечного автомата M = (Q, Σ, P, S, F ) таблица переходов автомата M имеет n = #Q строк, соответствующих всевозможным состояниям автомата, и k = #Σ столбцов, соответствующих всевозможным входным сигналам автомата. В клетке таблицы в строке, соответствующей состоянию q, и в столбце, соответствующем входному сигналу a перечисляются такие состояния r, для которых существует продукция qa → r. Если в такой таблице каким-то образом выделить начальные состояние и заклю­ чительные состояния, то она будет однозначно определять весь автомат. Условимся здесь каждое начальное состояние автомата обозначать стрелкой перед меткой стро­ ки таблицы, а заключительные состояния обозначать звездочкой перед меткой строки таблицы. Пример 37. Определим конечный автомат M1 для языка L = {α00β | α, β ∈ {0, 1}* } — множества всевозможных цепочек из нулей и единиц, в которых есть два подряд идущих нуля. 52 Пусть M1 = ({q0 , q1 , qf }, {0, 1}, P, q0 , {qf }), где P состоит из следующих продукций. q0 0 → q1 q0 1 → q0 q1 0 → qf q1 1 → q0 qf 0 → qf qf 1 → qf Множество P можно представить в виде таблицы: → q0 q1 *qf q1 qf qf 1 q0 q0 qf В этом автомате три состояния. Автомат находится в состоянии q0 до тех пор, пока на входе не будет получен символ 0. Если этот символ получен, то автомат считает его первым нулем из пары подряд идущих нулей и переходит в состояние q1 , где ожидает следующего символа, и если это будет 0, то переходит в заключительное состояние qf из которого уже не выйдет, но если это будет 1 — то пара нулей не состоялась, и автомат возвращается в состояние q0 . Например, цепочка 10110001 допускается этим автоматом, т.к. получив ее автомат поведет себя следующим образом q0 10110001 ⇒ q0 0110001 ⇒ q1 110001 ⇒ q0 10001 ⇒ q0 0001 ⇒ q1 001 ⇒ qf 01 ⇒ qf 1 ⇒ qf Так как qf — заключительное состояние, то последняя конфигурация в приведенной последовательности является заключительной. Цепочка 01110 не допускается автоматом, т.к. получив ее автомат сможет приме­ 53 нить продукции: q0 01110 ⇒ q0 01110 ⇒ q1 1110 ⇒ q0 110 ⇒ q0 10 ⇒ q0 0 ⇒ q1 . Прочитав всю цепочку автомат не оказался в заключительном состоянии, а значит цепочка не принадлежит языку, определяемому данным автоматом. Пример 38. Рассмотрим автомат M2 = ({q0 , q1 , q2 , q3 , qf }, {1, 2, 3}, P, {q0 }, {qf }), в ко­ тором множество P определено следующим образом: q0 1 → q1 1 → q1 2 → q2 2 → q2 1 → q3 1 → q3 2 → q1 ; q1 ; q2 ; q2 ; q2 ; q3 ; q2 ; q0 2 → q1 1 → q1 3 → q2 2 → q2 3 → q3 1 → q3 3 → q0 3 → q1 2 → q1 3 → q2 1 → q2 3 → q3 2 → q3 3 → q2 ; qf ; q1 ; qf ; q2 ; qf ; q1 ; q3 ; q1 ; q3 ; q1 ; q3 ; q3 ; q3 . Множество продукций автомата можно переписать в виде таблицы переходов: → q0 q1 q2 q3 *qf 1 q1 q1 , qf q2 , q1 q3 , q1 — 2 q2 q1 , q2 q2 , qf q3 , q2 — 3 q3 q1 , q3 q2 , q3 q3 , qf — Этот автомат допускает множество всевозможных цепочек, в которых последний символ присутствует в цепочке как минимум еще раз. Так, например, цепочка 1232 допускается автоматом. Здесь, среди различных пу­ тей вариантов работы автомата, можно выделить последовательность тактов q0 1232 допускающую входную цепочку. ⇒ q1 232 ⇒ q2 32 ⇒ q2 2 ⇒ qf , 54 Определение 72 (Диаграмма переходов). Диаграмма переходов для конечного авто­ мата M = (Q, Σ, P, S, F ) есть граф, определяемый следующим образом. 1. Всякому состоянию из Q соответствует некоторая вершина. 2. Пусть qa → p для некоторого состояния q ∈ Q и входного символа a ∈ Σ. Тогда диаграмма переходов должна содержать дугу из вершины q в вершину p помеченную a. Если существует несколько входных символов, переводя­ щих автомат из состояния q в состояние p, то диаграмма переходов может содержать одну дугу, отмеченную списком этих символов. 3. Диаграмма содержит стрелку, направленную в каждое начальное состояние, отмеченную как «Начало». 4. Вершины, не принадлежащие F изображаются одинарным кружком. Вер­ шины, соответствующие заключительным состояниям помечаются двойным кружком. Пример диаграммы переходов представлен на рис. 5.1. 0,1 1 1 Начало q0 q1 qf Рис. 5.1. Диаграмма переходов автомата из примера 37. Определение 73 (Полностью определенный конечный автомат). Конечный автомат M = (Q, Σ, P, S, F ) называют полностью определенным, если для каждого q ∈ Q и для каждого a ∈ Σ найдется r ∈ Q такое, что qa → r ∈ P. Любой конечный детерминированный автомат по определению является полностью определенным. Автомат M2 из примера 38 не является полностью определенным (нет реакции в заключительном состоянии). 5.1.4. Свойства автоматных языков Теорема 13 (Признаки непустоты и бесконечности автоматного языка). Язык, допус­ каемый конечным автоматом M с n состояниями 55 1) не пуст тогда и только тогда, когда M допускает цепочку длины, мень­ шей чем n; 2) бесконечный тогда и только тогда, когда он принимает цепочку длины l, n 6 l < 2n. Доказательство. Пусть M = (Q, Σ, P, q0 , F ) — конечный автомат, #Q = n. Достаточность условия 1 очевидна. Действительно, если M допускает цепочку длины, меньшей чем n, то язык L(M) уже не пуст. Необходимость условия 1 следует из следующих рассуждений от противного. Предположим, что L(M) — не пуст, но ни одной цепочки длины меньше n в этом языке не существует. Рассмотрим цепочку w ∈ L(M). Пусть w — одна из самых коротких таких цепочек. Пусть w = a1 a2 a3 . . . am , где m > n и каждый ai — входной символ. Пусть p0 = q0 , p1 , p2 , . . . , pm — последовательность состояний, через которую пере­ ходит автомат при допуске входной цепочки w. Т. е. p0 w ⇒ p1 a2 a3 . . . am ⇒ p2 a3 . . . am ⇒* pm . Причем pm ∈ F . Рассмотрим первые n + 1 состояний из последовательности pi для i = 0, 1, . . . , n. Поскольку автомат M имеет n различных состояний, то найдутся два целых числа i и j (0 6 i < j 6 n), при которых pi = pj . Разобьем цепочку w на xyz следующим образом 1) x = a1 a2 . . . ai ; 2) y = ai+1 ai+2 . . . aj ; 3) z = aj+1 aj+2 . . . am . Цепочка x приводит автомат в состояние pi , y — из pi обратно в pi (так как pi = pj ), а z — остаток цепочки w. Т. е. p0 xyz ⇒* pi yz ⇒+ pj z ⇒* pm . Причем цепочка x может быть пустой при i = 0, а z — при j = n = m. Однако цепочка y не может быть пустой, т. к. i строго меньше j. Если на вход автомата подать цепочку xz, автомат переходит из начального со­ стояния q0 в pi , прочитав x. Поскольку pi = pj , то z переводит M из состояния pi в допускающее состояние. Значит xz ∈ L(M). 56 В то же время |xz| < |xyz| = |w|, но это противоречит предположению, что w — одна из самых коротких цепочек, допускаемых M. Докажем теперь утверждение 2. Достаточность условия 2 следует из нижеследующих рассуждений. Пусть суще­ ствует w ∈ L(M), причем n 6 |w| < 2n. Как и в предыдущих рассуждениях мо­ жем утверждать, что существуют q ∈ Q и qf ∈ F , что w= xyz, где y ̸= ε, и q0 xyz ⇒* qyz ⇒+ qz ⇒* qf . Но тогда цепочки вида xyi z ∈ L(M) при любом i. Действительно, получая x автомат переходит из q0 в q, затем, читая yi цикличе­ ски проходит через q, и, наконец, по z переходит в заключительное состояние. Таким образом, для любого i цепочка xyi z также распознается автоматом M, а значит, при­ надлежит языку L(M). Очевидно, множество L(M) бесконечно. Необходимость условия 2 доказывается методом от противного. Пусть M при­ нимает бесконечное множество цепочек, причем ни одна из них не имеет длину l, n 6 l < 2n. Если бы существовали только цепочки длиной l < n, то язык L(M) был бы конечен, но это не так. Рассмотрим цепочки языка длины l > 2n. Пусть w — одна из самых коротких таких цепочек. Очевидно, существуют q ∈ Q и qf ∈ F , что мы можем написать w= xyz, где 0 < |y| 6 n, и q0 xyz ⇒* qyz ⇒+ qz ⇒* qf . Но тогда xz ∈ L(M), поскольку q0 xz ⇒* qz ⇒* qf . Из того, что |w| > 2n следует, что |xz| > n. Т. к. в языке L(M) нет слов длины n 6 l < 2n, |xz| > 2n. В то же время |xz| < |xyz| = |w|, но это противоречит предположению, что w — одна из самых коротких таких цепочек, допускаемых M. Что и требовалось доказать. Теорема 14 (Об автоматности языков типа 3). Для языка L следующие три условия эквивалентны: 1) L допускаем конечным детерминированным автоматом; 2) L допускаем конечным недетерминированным автоматом; 3) L язык типа 3. 57 Доказательство. Любой КДА (Q, Σ, P, q0 , F ) можно представить в виде НКА (Q, Σ, P, {q0 }, F ). Т. о. следствие 1→2 очевидно. Рассмотрим предположение 2→3 Пусть M = (Q, Σ, P, S, F ) — НКА. Тогда язык определенный этим автоматом можно представить как объединение языков L(M) = ⋃︁ {w ∈ Σ* | q0 w ⇒* q}. (5.2) q0 ∈S,q∈F Каждый язык в объединении в (5.2) распознается аналитической грамматикой типа 3, чье множество правил состоит из продукций исходного НКА и дополнительной про­ дукции ε → q0 и чей заключительный символ q. Т. к. по теореме 5 объединение языков типа 3 есть язык типа 3, делаем заключение, что язык L(M) — язык типа 3. Т. е. следствие 2→3 доказано. Рассмотрим предположение 3→2. Пусть задан язык L = L(G), где G = (N , Σ, P, S) — аналитическая грамматика типа 3. Сначала покажем, что для грамматики G можно построить эквивалентную грам­ матику G′ = (N ′ , Σ, P ′ , S), каждое правило в которой представлено в одной из следу­ ющих форм Ba → A, ε → A, a ∈ Σ, A, B ∈ N , (5.3) A ∈ N. (5.4) Кроме правил в форме (5.3) и (5.4) в G могут содержаться также правила вида Ba1 . . . ak → A, k > 2, ai ∈ Σ, A, B ∈ N (5.5) a1 . . . ak → A, k > 1, ai ∈ Σ, A, B ∈ N (5.6) A, B ∈ N (5.7) B → A, Таким образом нам необходимо избавиться в G от правил (5.5)-(5.7). Для каждого правила вида (5.5) введем новые нетерминалы X1 , X2 , . . . , Xk−1 и заменим (5.5) на набор продукций Ba1 → X1 , X1 a2 → X2 , . . . Xk−1 ak → A. 58 Для каждого правила вида (5.6) введем новые нетерминалы X0 , X1 , X2 , . . . , Xk−1 и заменим (5.6) на набор продукций ε → X0 , X0 a1 → X1 , X1 a2 → X2 , . . . , Xk−1 ak → A. Легко видеть, что язык, сгенерированный исходной грамматикой, не претерпит из­ менений в результате таких модификаций множества правил. Эту процедуру следует выполнять, пока в грамматике остаются правила вида (5.5) или (5.6). Пусть в резуль­ тате получена грамматика G′′ , содержащая только правила вида (5.3), (5.4) и (5.7) и для которой выполняется L(G′′ ) = L(G). Для того, чтобы избавиться от правил вида (5.7) сделаем следующее. Для каждого нетерминала C ∈ N определим множество U (C) = {X ∈ N | C ⇒* X}. После этого удалим все продукции вида (5.7) из грамматики. Добавим в множество правил для каждого правила вида α → A (правила в форме (5.3) или (5.4)) правила α → X для всех X ∈ U (A). Полученная грамматика G′ = (N ′ , Σ, P ′ , S) будет определять тот же язык, что и исходная грамматика G. Заменим построенную грамматику конечным недетерминированным автоматом M = ′ (N , Σ, P ′′ , N ′′ , {S}), где N ′′ множество нетерминалов из N ′ , для которых в P ′ есть правило вида (5.4), P ′′ — все продукции из P ′ вида (5.3). Покажем, что L(M) = L(G′ ). (5.8) Действительно, пусть w = a1 a2 . . . ar ∈ L(G′ ), где ai ∈ Σ, тогда существует вывод a1 a2 . . . ar ⇒ X0 a1 a2 . . . ar ⇒ X1 a2 . . . ar (5.9) * ⇒ Xr−1 ar ⇒ S по правилам грамматики G′ , а так же по определению автомата M, X0 a1 a2 . . . ar ⇒ X1 a2 . . . ar ⇒* Xr−1 ar ⇒ S. (5.10) С другой стороны, вывод (5.9) может быть получен из (5.10). Следовательно (5.8) имеет место, а значит верно следствие 3→2. Рассмотрим предположение 2→1. 59 ′ ′ ′ Пусть имеется НКА M = (Q, Σ, P, S, F ). Построим КДА M = (Q , Σ, P , q0 , F ′ ), допускающий тот же язык. Множество Q ′ символов состояний автомата M′ — множество всех подмножеств множества Q, т. е. Q ′ = P(Q). Определим q0 — начальное состояние автомата M′ как множество S — множество всех стартовых состояний исходного автомата. Множество F ′ заключительных состояний определим состоящим из подмножеств множества Q, содержащих хотя бы один элемент из F , т. е. F ′ = {q ∈ Q ′ | q ∩ F ̸= ∅}. Для каждой пары (q, a), q ∈ Q ′ , a ∈ Σ, добавим в множество продукций P ′ автомата M′ правило qa → r, где r = {p ∈ Q | sa → p ∈ P, s ∈ q}. (5.11) Теперь можно показать, что L(M) = L(M′ ). Пусть w = a1 a2 . . . ar ∈ L(M), где ai ∈ Σ. Тогда существует вывод s0 a1 a2 . . . ar ⇒ s1 a2 . . . ar ⇒* sr−1 ar ⇒ sf (5.12) согласно продукциям автомата M. По определению автомата M′ , q0 a1 a2 . . . ar ⇒ q1 a2 . . . ar ⇒* qr−1 ar ⇒ qf , (5.13) где si ∈ qi . qf содержит sf , а значит, является заключительным состоянием. С другой стороны, вывод (5.12) может быть получен из (5.13). Следовательно L(M) = L(M′ ), а значит верно следствие 2→1. Теорема доказана. Следствие 14.1. Класс языков L3 замкнут относительно дополнения и пересече­ ния. Доказательство. Пусть L — язык типа 3. Тогда существует конечный детерминиро­ ванный автомат M = (Q, Σ, P, q0 , F ) такой, что L = L(M). Построим автомат M′ = (Q, Σ, P, q0 , F ′ ) 60 в котором F′ = Q − F. Очевидно, что автомат M′ будет допускать только те цепочки, которые не допус­ каются автоматом M и наоборот, т. е. L(M′ ) =∼ L. Так как пересечение можно расписать через операции дополнения и объединения L1 ∩ L2 =∼ ((∼ L1 ) ∪ (∼ L2 )), по теореме 5 полученный в результате пересечения язык — язык типа 3. Следствие 14.2. Любой язык типа 3 может быть порожден грамматикой G = (N , Σ, P, S), где каждое правило из P имеет одну из двух следующих форм A A → Ba, → ε, a ∈ Σ, A, B ∈ N , A ∈ N. (5.14) Доказательство. Пусть L — язык типа 3. Тогда найдется G аналитическая грамма­ тика типа 3 его допускающая. По алгоритму, приведенному в доказательстве теоре­ мы 14, по грамматике G найдем грамматику G′ состоящую только из правил вида (5.3)-(5.4). В грамматике, двойственной к G′ правила будут иметь вид (5.14). Пример 39. Рассмотрим НКА из примера 38. → q0 q1 q2 q3 *qf 1 q1 q1 , qf q2 , q1 q3 , q1 — 2 q2 q1 , q2 q2 , qf q3 , q2 — 3 q3 q1 , q3 q2 , q3 q3 , qf — Найдем КДА определяющий тот же язык, что и данный автомат. В качестве состояний нового автомата возьмем множество всех подмножеств неде­ терминированного автомата. Для простоты, состояния нового автомата переименуем буквами (или парами букв) латинского алфавита, как показано в таблице переходов на рис. 5.2. 61 A →B C D E *F G H I *J K L *M N *O *P Q R *S T *U *V W *X *Y *Z AA *BB *CC *DD *EE *FF ∅ {q0 } {q1 } {q2 } {q3 } {qf } {q0 , q1 } {q0 , q2 } {q0 , q3 } {q0 , qf } {q1 , q2 } {q1 , q3 } {q1 , qf } {q2 , q3 } {q2 , qf } {q3 , qf } {q0 , q1 , q2 } {q0 , q1 , q3 } {q0 , q1 , qf } {q0 , q2 , q3 } {q0 , q2 , qf } {q0 , q3 , qf } {q1 , q2 , q3 } {q1 , q2 , qf } {q1 , q3 , qf } {q2 , q3 , qf } {q0 , q1 , q2 , q3 } {q0 , q1 , q2 , qf } {q0 , q1 , q3 , qf } {q0 , q2 , q3 , qf } {q1 , q2 , q3 , qf } {q0 , q1 , q2 , q3 , qf } 1 A C M K L A M K L C X Y M W K L X Y M W K L EE X Y W EE X Y W EE EE 2 A D K O N A K O N D X W K Z O N X W K Z O N EE X W Z EE X W Z EE EE 3 A E L N P A L N P E W Y L Z N P W Y L Z N P EE W Y Z EE W Y Z EE EE Рис. 5.2. Таблица переходов КДА, построенного для НКА из примера 38 Определим новое множество продукций так, как это предложено в (5.11). Напри­ мер, для определения правой части продукции H1 → x вычисляем x = {r | q1 → r ∈ P, q ∈ H}. Т. к. H = {q0 , q2 }, то множество x составят состояния из правых частей всех продук­ ций, имеющих в левой части q0 1 или q2 1. Таких продукций три. q0 1 → q1 q2 1 → q1 q2 1 → q2 Объединяя правые части правил получим x = {q1 , q2 }, или, в новых обозначениях, 62 x = K. Следовательно, искомая продукция H1 → K. Сделав подобные построения для каждой пары «состояние, входной сигнал» полу­ чим автомат с таблицей переходов, показанной на рис. 5.2. Полученный автомат является полностью определенным детерминированным ко­ нечным автоматом. В построенном детерминированном автомате есть лишние («бесполезные») состо­ яния. Например из начального состояния B автомат никогда не сможет перейти в состояние AA. Определение 74 (Недостижимое состояние). Состояние q конечного автомата M = (Q, Σ, P, S, F ) называется недостижимым, если не найдется начального состояния q0 ∈ S и цепочки α ∈ Σ* , приводящей автомат из начального состояния в состояние q. Другими словами @α ∈ Σ* : q0 α ⇒* q. Логично предположить, что недостижимые состояния — бесполезные состояния. Удаление из автомата недостижимых состояний не приведет к изменению языка, опре­ деляемого автоматом. Теорема 15 (О КДА без недостижимых состояний). Для любого конечного детерми­ нированного автомата M найдется эквивалентный конечный детерминированный автомат M′ без недостижимых состояний. Доказательство. Пусть M = (Q, Σ, P, q0 , F ) — заданный КДА. Возьмем Q ′ = {q0 }. Добавим в Q ′ всевозможные состояния r ∈ Q для которых найдется продукция q0 a → r ∈ P для некоторого входного сигнала a ∈ Σ. Если в P найдется продукция qa → r, такая, что q ∈ Q ′ и r ∈ / Q ′ , то добавим r в Q′ . Будем повторять последний шаг, пока он приводит к пополнению множества Q ′ . Очевидно, что в множество Q ′ попадут все достижимые состояния автомата M. Тогда автомат M′ = (Q ′ , Σ, P ′ , q0 , F ′ ), 63 где P ′ = P ∩ (Q ′ Σ × Q ′ ), F ′ = F ∩ Q ′ , будет допускать тот же язык, что и исходный автомат. Пример 40. Рассмотрим автомат, полученный в примере 39. Выполняя алгоритм, из­ ложенный в доказательстве последней теоремы на начальном шаге получим: Q ′ = {B}. Добавим в Q ′ все состояния, достижимые из B: Q ′ = {B, C, D, E}. Последовательно пополняя множество Q ′ получим: Q ′ = {B,C, D, E, достижимые из состояния C: M, K, L достижимые из состояния D: O, N, достижимые из состояния E: P, достижимые из состояния K: X, W, достижимые из состояния L: Y, достижимые из состояния N: Z, достижимые из состояния W: EE} Остальные 17 состояний, неперечисленные в Q ′ , оказались недостижимыми. Удалив их получим автомат с таблицей переходов, представленной на рис. 5.3. →B C D E K L *M N *O *P W *X *Y *Z *EE {q0 } {q1 } {q2 } {q3 } {q1 , q2 } {q1 , q3 } {q1 , qf } {q2 , q3 } {q2 , qf } {q3 , qf } {q1 , q2 , q3 } {q1 , q2 , qf } {q1 , q3 , qf } {q2 , q3 , qf } {q1 , q2 , q3 , qf } 1 C M K L X Y M W K L EE X Y W EE 2 D K O N X W K Z O N EE X W Z EE 3 E L N P W Y L Z N P EE W Y Z EE Рис. 5.3. Таблица переходов КДА из примера 39 без «бесполезных» продукций 64 Пример 41. Рассмотрим грамматику G = ({S, A, B}, {0, 1, 2}, P, S), в которой множе­ ство P представлено продукциями S → A0 | B1 | ε A → S0 | B1 | 2 B → S1 | A1 Сначала получим двойственную грамматику для данной. A0 → S B1 → S ε→S S0 → A B1 → A 2→A S1 → B A1 → B Избавимся от правила 2 → A, заменив его на ε→C C2 → A. По полученному множеству продукций построим конечный недетерминированный автомат M = ({S, A, B, C}, {0, 1, 2}, P ′ , {C, S}, {S}), в котором P ′ — множество продук­ ций A0 → S B1 → S S0 → A B1 → A C2 → A S1 → B A1 → B Если представить построенный автомат в виде таблицы, получим → *S A B →C A S — — 1 B B S, A — 2 — — — A 65 Из последнего автомата можно получить конечный детерминированный автомат. Если оставить в таком автомате только достижимые состояния, то получим автомат, определенный следующей таблицей переходов (во втором столбце таблицы переходов приведена расшифровка новых обозначений состояний). → *q0 q1 q2 *q3 q4 *q5 q1 q3 q4 q1 q4 q5 {S, C} {A} {B} {S} ∅ {S, A} 1 q2 q2 q5 q2 q4 q2 2 q1 q4 q4 q4 q4 q4 Определение 75 (Различение состояний автомата). Пусть M = (Q, Σ, P, S, F ) — конеч­ ный автомат. q1 и q2 — два состояния этого автомата. Говорят, что цепочка α различает состояния q1 и q2 если q1 α ⇒* r1 , q2 α * r2 , ⇒ где r1 , r2 ∈ Q, причем одно из состояний r1 или r2 является заключительным, а второе нет. Определение 76 (k-неразличимые состояния). Два состояния q1 и q2 конечного ав­ томата M = (Q, Σ, P, S, F ) называют k-неразличимыми, и пишут q1 ≡k q2 , когда не найдется цепочки α ∈ Σ* , |α| 6 k, различающей эти состояния. Определение 77 (Эквивалентные состояния). Два состояния q1 и q2 конечного автома­ та M = (Q, Σ, P, S, F ) называют неразличимыми (эквивалентными), и пишут q1 ≡ q2 , если они k-неразличимы для любого k > 0. Теорема 16 (Критерий неразличимости состояний автомата). Для того, чтобы два состояния q1 и q2 конечного детерминированного автомата M = (Q, Σ, P, q0 , F ) были неразличимы необходимо и достаточно, чтобы два этих состояния были n − 2-неразличимы, где n — число состояний автомата M. Доказательство. Необходимость. Тривиально. Если два состояния неразличимы, то они k-неразличимы для любого k > 0 (по определению неразличимости), в том числе и для k = n − 2. 66 Достаточность. Отношение k-неразличимости является отношением эквивалент­ ности на множестве состояний автомата M. Два состояния r1 , r2 ∈ Q, принадлежащие разным классам эквивалентности при отношении k-неразличимости, не могут принад­ лежать одному классу эквивалентности при отношении l-неразличимости, l > k, по определению k-неразличимости. Кроме того, из определения k-неразличимости имеем следующие соотношения. 1. r1 ≡0 r2 тогда и только тогда, когда r1 ∈ F и r2 ∈ F или r1 ∈ / F и r2 ∈ / F; 2. r1 ≡k+1 r2 тогда и только тогда, когда r1 ≡k r2 и для любого a ∈ Σ, при наличии в P продукций r1 a → s1 и r2 a → s2 выполняется s1 ≡k s2 . Из этих соотношений следует, что если найдется такое k, что ≡k =≡k+1 , то ≡k =≡l , ∀l > k и ≡k =≡. Действительно, пусть ≡k =≡k+1 . Тогда из соотношения 2 следу­ ет r1 ≡k+1 r2 тогда и только тогда, когда r1 ≡k+2 r2 . Так как r1 и r2 — любые со­ стояния, принадлежащие одному классу эквивалентности при k-неразличимости, то ≡k =≡k+1 =≡k+2 . Применяя свойство 2 многократно, получим ≡k =≡. Предположим, что в автомате есть различимые состояния, а значит F ̸= ∅, F ̸= Q. Тогда #F 6 n − 1 и #(Q∖F ) 6 n − 1. Т.е. в каждом из классов эквивалентности при отношении 0–неразличимости менее n состояний. Можно производить деление этих классов на новые не более n − 2 раз. Достаточность доказана. На основе последней теоремы существует метод нахождения всех пар эквивалент­ ных состояний КДА, который называется методом заполнения таблицы. Пусть M = (Q, Σ, P, q0 , F ) — КДА, в котором n = #Q. Создадим n × n-таблицу T в которой строки и столбцы соответствуют состояниям данного автомата. Изначально все ячейки таблицы пусты. В дальнейшем будем по­ мещать в клетку таблицы T (q, r) знак ×, если состояния q и r различимы. Таблица будет симметрична относительно главной диагонали, а следовательно когда будем за­ полнять ячейку таблицы T (q, r), то будем заполнять и ячейку T (r, q). В дальнейшем при заполнении одной ячейки таблицы не будем дополнительно упоминать о заполне­ нии другой. Если q — заключительное состояние, а r — нет, то q и r — различимые состояния. Помещаем знак × в ячейку T (q, r). Пусть q и r — состояния, для которых существует входной сигнал a ∈ Σ, такой что qa → p ∈ P, ra → s ∈ P и T (p, s) = ×. Тогда (q, r) — пара различимых состояний. 67 Помещаем знак × в ячейку T (q, r). Повторяем последний шаг пока он приводит к добавлению в таблицу знака ×. Из теоремы 16 следует, что достаточно n − 2 раза просмотреть по порядку все пустые клетки таблицы (выше или ниже главной диагонали) чтобы отметить все пары различимых состояний. Пример 42. Рассмотрим автомат, представленный на рис. 5.4. 1 Начало A 1 B 1 E C 1 F D 1 1 1 G 1 H Рис. 5.4. Конечный автомат имеющий неразличимые состояния. Найдем в нем все пары неразличимых состояний, используя метод заполнения таблицы. В качестве T возюмем 8 × 8-таблицу, строки и столбцы которой помечены состояниями данного автомата. Так как в представленном автомате только лишь одно состояние C заключительное, то помечаем в таблице T все ячейки в строке, соответ­ ствующей состоянию C, и в столбце, соответствующем состоянию C, за исключением ячейки T (C, C). Получим таблицу: A B C D E F G H A B × × C × × D E F G H × × × × × × × × × × Так как T (C, H ) = ×, а автомат из состояний E и F по сигналу 0 переходит в состояния H и C, то значит пара {E, F } —различимые состояния, помечаем T (E, F ) = T (F , E) = ×. Аналогично, по сигналу 1 автомат переходит из состояния A в F , и из G в E. Но T (E, F ) = ×, а следовательно помечаем T (A, G) = T (G, A) = ×. Продолжаем 68 такие рассуждения, пока это возможно (т. е. пока возможно обнаружить новые пары различимых состояний). Окончательный вариант таблицы T : A A B C D E F G H × × × × × × B × × × × × × C × × × × × × × D × × × E × × × × × × F × × × × × × × × × G × × × × × × H × × × × × × × Итак, согласно полученной таблице только следующие пары состояний неразличи­ мы: {A, E}, {B, H }, {D, F }. Понятие неразличимости (эквивалентности) можно распространить на состояния различных автоматов следующим образом. Пусть M1 = (Q1 , Σ, P1 , q1 , F1 ) и M2 = (Q2 , Σ, P2 , q2 , F2 ) два КДА. Тогда неразличимость состояний r1 ∈ Q1 и r2 ∈ Q2 опреде­ ляется соотношениями: 1. r1 ≡0 r2 тогда и только тогда, когда r1 ∈ F1 и r2 ∈ F2 или r1 ∈ / F1 и r2 ∈ / F2 ; 2. r1 ≡k+1 r2 тогда и только тогда, когда r1 ≡k r2 и для любого a ∈ Σ, при наличии в P1 продукции r1 a → s1 и в P2 продукции r2 a → s2 выполняется s1 ≡k s2 . 3. (r1 ≡ r2 ) ⇔ (∀k > 0, r1 ≡k r2 ). Определение 78 (Эквивалентные автоматы). Два КДА M1 = (Q1 , Σ, P1 , q1 , F1 ) и M2 = (Q2 , Σ, P2 , q2 , F2 ) называют эквивалентными, если состояние q1 эквивалентно q2 . Если автоматы M1 и M2 не являются эквивалентными, то они различимы. По конечному автомату часто можно построить автомат с минимальным возмож­ ным числом состояний, эквивалентный исходному. Соответствующий процесс называ­ ется минимизацией конечного автомата. Минимизация заключается в удалении всех недостижимых состояний и исключении парных неразличимых состояний. Теорема 17 (О минимальном автомате). Для любого КДА M = (Q, Σ, P, q0 , F ) най­ дется эквивалентный автомат M′ = (Q ′ , Σ, P ′ , q0′ , F ′ ) без неразличимых состоя­ ний, допускающий тот же язык. Причем, если M — автомат без недостижимых состояний, то не существует КДА, допускающего L(M) и имеющего меньше со­ стояний, чем #Q ′ . 69 Доказательство. Разобьем множество состояний Q на классы эквивалентности, со­ ответствующие отношению неразличимости ≡ (используя выкладки из доказательства теоремы 16 или метод заполнения таблицы) и пусть [Q]≡ — совокупность полученных классов эквивалентности. Определим автомат M′ = (Q ′ , Σ, P ′ , q0′ , F ′ ), где 1. Q ′ = [Q]≡ ; 2. q0′ = [q0 ]≡ ; {︀ }︀ 3. F ′ = [q]≡ ∈ [Q]≡ | q ∈ F ; 4. P ′ = {[q]≡ a → [r]≡ | где qa → r ∈ P}. Легко видеть, что построенный автомат допускает тот же язык, что и исходный автомат. Пусть в M отсутствуют недостижимые состояния. Покажем, что построенный ав­ томат имеет минимально-возможное число состояний. Предположим, что существует КДА M′′ = (Q ′′ , Σ, P ′′ , q0′′ , F ′′ ), такой, что L(M′′ ) = L(M) и в котором #Q ′′ < #Q ′ . Тогда существуют цепочки γ1 и γ2 , такие, что эти цепочки переводят автомат M′ в разные состояния q0′ γ1 ⇒M′ q1′ , q0′ γ2 ⇒M′ q2′ , но при этом переводят автомат M′′ в одно и то же состояние q0′′ γ1 ⇒M′′ q1′′ , q0′′ γ2 ⇒M′′ q1′′ . Так как в автомате M′ нет эквивалентных и недостижимых состояний, найдется цепочка ϑ, что q1′ ϑ ⇒M′ q3′ , q2′ ϑ ⇒M′ q4′ , где точно одно из состояний q3′ , q4′ является заклю­ чительным. Очевидно, что точно одна из цепочек γ1 ϑ, γ2 ϑ допускается автоматом M′ , и, следовательно, принадлежит языку L(M). Но в автомате M′′ , цепочки γ1 ϑ, γ2 ϑ пе­ реводят автомат в одно и то же состояние. Следовательно, эти цепочки одновременно принадлежат или не принадлежат языку L(M). Получили противоречие. Теорема доказана. Пример 43. Снова рассмотрим автомат, представленный на рис. 5.4. В этом автома­ те нет недостижимых состояний. Всевозможные пары неразличимых состояний этого автомата найдены в примере 42, а следовательно можно определить совокупность классов эквивалентности отношения неразличимости на множестве состояний авто­ мата {︀ }︀ [Q1 ]≡ = {A, E}, {B, H }, {C}, {D, F } . Построим новый автомат, состояниями которого будут классы эквивалентности из [Q1 ]≡ . Начальным состоянием нового автомата будет {A, E}, т.к. A — начальное со­ 70 стояние исходного автомата. Заключительным состоянием будет {C}. Переход из со­ стояния {A, E} по сигналу 0 будет в B, H , т.к. в исходном автомате по сигналу 0 был переход из A в B. Переход из состояния {A, E} по сигналу 1 будет в D, F , т.к. в исходном автомате по сигналу 1 был переход из A в F . И т.д. На рис. 5.5 оконча­ тельный вариант автомата, полученного минимизацией автомата представленного на рис. 5.4. 1 G 1 D 1 Начало A, E B, H 1 C 1 Рис. 5.5. Автомат полученный в результате минимизации автомата, представленного на рис. 5.4. 5.2. Автоматы с магазинной памятью Определение 79 (Автомат с магазинной памятью). Система текстовых замен M = (Ω, P) называется автоматом с магазинной памятью (МП-автоматом) если 1) в алфавите Ω можно выделить три алфавита Q, Σ и Γ, называемые соот­ ветственно множеством символов состояний (множеством состояний), мно­ жеством входных сигналов (входным алфавитом) и множеством символов магазинной памяти, причем Q ∪ Σ ∪ Γ = Ω; 2) в множестве Q выделяется элемент q0 называемый начальным (стартовым) состоянием и подмножество F — множество заключительных состояний; 3) в множестве Γ выделяется элемент Γ0 называемый начальным (стартовым) символом магазинной памяти; 71 4) любая продукция в P имеет одну из следующих форм: Zq → γr, Zqa → γr, q, r ∈ Q, γ ∈ Γ* , Z ∈ Γ, (5.15) q, r ∈ Q, γ ∈ Γ* , Z ∈ Γ, a ∈ Σ. (5.16) Таким образом, для определения МП-автомата необходимо определить семь ком­ понент (Q, Σ, Γ, P, q0 , Γ0 , F ). Отношение выводимости ⇒* для МП-автоматов имеет общий вид отношения вы­ водимости в системах текстовых замен. Определение 80 (Язык, допускаемый МП-автоматом). Язык определенный (допуска­ емый, распознаваемый) МП-автоматом M = (Q, Σ, Γ, P, q0 , Γ0 , F ) есть множество слов L(M) = {w ∈ Σ* | Γ0 q0 w ⇒* γq, q ∈ F , γ ∈ Γ* }. Пример 44. Рассмотрим МП-автомат для языка, L = {wwR | w ∈ (a + b)* }. P = ({q0 , q1 , g2 }, {a, b}, {a, b, Γ0 }, P, q0 , Γ0 , {q0 }), где множество продукций P определяется следующим образом: Γ0 q0 a → Γ0 aq1 ; (5.17) Γ0 q0 b → Γ0 bq1 ; (5.18) aq1 a → aaq1 ; (5.19) bq1 a → baq1 ; (5.20) aq1 b → abq1 ; (5.21) bq1 b → bbq1 ; (5.22) aq1 a → q2 ; (5.23) bq1 b → q2 ; (5.24) aq2 a → q2 ; (5.25) bq2 b → q2 ; (5.26) Γ0 q2 → q0 . (5.27) Данный автомат переносит в магазин очередной символ (продукции (5.17)- (5.22)) до тех пор, пока не решит, что поместил туда всю первую половину слова. После этого на каждом шаге верхний символ магазина автомат сравнивает с очередным входным символом и, если сравнение прошло успешно, удаляет его (продукции (5.23)-(5.26)). Перебрав все такие пары автомат должен опустошить магазин вплоть до символа, 72 отмечающего его дно, после чего переходит в заключительное состояние (продукция (5.27)). Например этот автомат может допустить цепочку abbaabba с помощью следующе­ го вывода: Γ0 q0 abbaabba ⇒ Γ0 aq1 bbaabba ⇒ Γ0 abq1 baabba ⇒ Γ0 abbq1 aabba ⇒ ⇒ Γ0 abbaq1 abba ⇒ Γ0 abbq2 bba ⇒ Γ0 abq2 ba ⇒ Γ0 aq2 a ⇒ Γ0 q2 ⇒ q0 Утверждение 1. Язык допускается автоматом с магазинной памятью тогда и только тогда, когда он контекстно-свободный. Определение 81 (Детерминированный МП-автомат). Автомат с магазинной памятью M = (Q, Σ, Γ, P, q0 , Γ0 , F ) называется детерминированным если: 1) для каждых q ∈ Q и Z ∈ Γ в множестве P содержится точно одна продукция вида (5.15) и нет продукций вида (5.16), или нет продукций вида (5.15) и точно одна продукция вида (5.16) для каждого a ∈ Σ; 2) если Z = Γ0 в (5.15) или (5.16), то Γ0 является первым символом в γ. В последнем определении пункт 1 является необходимым для детерминированного поведения автомата, тогда как пункт 2 следит за тем, чтобы магазин автомата никогда не оказался пустым. Определение 82 (Детерминированный язык типа 2). Язык типа 2 называют детерми­ нированным, если он допускается детерминированным МП-автоматом. 5.3. Линейные ограниченные автоматы Определение 83 (Линейный ограниченный автомат). Система текстовых замен M = (Ω, P) называется линейным ограниченным автоматом (ЛО-автоматом) если 1) в алфавите Ω можно выделить два алфавита Q, и Σ, называемые соответ­ ственно множеством символов состояний (множеством состояний) и множе­ ством символов ленты (входным алфавитом), причем Q ∪ Σ = Ω; 2) в множестве Q выделяется элемент q0 называемый начальным (стартовым) состоянием и подмножество F — множество заключительных состояний; 73 3) любая продукция в P имеет одну из следующих форм qa → rb, q, r ∈ Q, a, b ∈ Σ, (5.28) qa → ar, q, r ∈ Q, a ∈ Σ, (5.29) q, r ∈ Q, a, c ∈ Σ. (5.30) cqa → rca, Более того, для каждых q, a и r множество P не содержит ни одного правила вида (5.30) или содержит (5.30) для всех c ∈ Σ. Таким образом ЛО-автомат можно представить как набор M = (Q, Σ, P, q0 , F ). Определение 84 (Язык, допускаемый ЛО-автоматом). Язык определенный (допускае­ мый, распознаваемый) ЛО-автоматом M = (Q, Σ, P, q0 , F ) есть множество слов L(M) = {w ∈ Σ* | q0 w ⇒* αq, q ∈ F , α ∈ Σ* }. Утверждение 2. Язык допускается ЛО-автоматом тогда и только тогда, когда он контекстно-зависимый. Определение 85 (Детерминированный ЛО-автомат). ЛО-автомат называется детерми­ нированным если для каждых q и a выполнено только одно из следующих условий. 1. В P есть точно одна продукция вида (5.28). 2. В P есть точно одна продукция вида (5.29). 3. В P есть точно один набор продукций вида (5.30), в котором c пробегает все значения из Σ. 5.4. Машины Тьюринга Определение 86 (Машина Тьюринга). Система текстовых замен M = (Ω, P) называ­ ется машиной Тьюринга если 1) в алфавите Ω можно выделить два алфавита Q, и Γ, называемые соответ­ ственно множеством символов состояний (множеством состояний) и мно­ жеством символов ленты, а также дополнительный символ #, называемый маркером границы строки, не принадлежащий этим двум алфавитам, причем Q ∪ Γ ∪ {#} = Ω; 2) в множестве Q выделяется элемент q0 , называемый начальным (стартовым) состоянием, и подмножество F — множество заключительных состояний; 74 3) в множестве Γ выделяется подмножество Σ называемое множеством входных сигналов, а также вспомогательный символ o; 4) любая продукция в P имеет одну из следующих форм qa → rb qac → arc qa# → aro# cqa → rca #qa → #roa (перезапись), (5.31) (сдвиг вправо), (5.32) (сдвиг вправо с расширением), (5.33) (сдвиг влево), (5.34) (сдвиг влево с расширением), (5.35) где q, r ∈ Q, a, b, c ∈ Γ. Более того, для каждых q, a и r множество P не содержит ни одного правила вида (5.32) и (5.33) (соотв. (5.34) и (5.35)) или содержит и (5.32) и (5.33) (соотв. (5.34) и (5.35)) для всех c ∈ Γ. Ни для каких q и a цепочка qa не является подцепочкой левой части двух разных продукций из семейства продукций вида (5.31), (5.33) и (5.35). Таким образом машину Тьюринга можно представить как набор M = (Q, Σ, Γ, P, #, o, q0 , F ). Определение 87 (Финализирующая цепочка). Для заданной машины Тьюринга M = (Q, Σ, Γ, P, #, o, q0 , F ) цепочка qaα, q ∈ Q, a ∈ Γ ∪ {#}, α ∈ Γ* ∪ {#}, называется финализирующей, если qa не является подцепочкой левой части ни одной продукции в P. Определение 88 (Язык, допускаемый машиной Тьюринга). Язык определенный (до­ пускаемый, распознаваемый) машиной Тьюринга M = (Q, Σ, Γ, P, #, o, q0 , F ) есть множество слов L(M) = {w ∈ Σ* | #q0 w# ⇒* #αqβ#, q ∈ F , α, β ∈ Γ* , qβ# — финализирующая}. Теорема 18 (О классе языков, допускаемых машиной Тьюринга). Если язык допус­ кается машиной Тьюринга, то это язык типа 0. Доказательство. Пусть L — язык, допускаемый машиной Тьюринга M = (Q, Σ, Γ, P, #, o, q0 , F ). 75 ′ Определим G = (N , Σ, P ∪ P , X0 ) — аналитическую грамматику типа 0, распозна­ ющую язык L. В качестве множества нетерминалов возьмем множество N = Q ∪ (Γ − Σ) ∪ {#} ∪ {X0 , X1 , X2 }. Множество продукций P ′ составим из правил: ε → #q0 , X1 # → X2 , ε → #, q# → X2 , qa → X1 , bX2 → X2 , X1 b → X1 , #X2 → X0 , где b — пробегает все символы из Γ, q и a — такие значения, что q ∈ F и цепочка qa является финализирующей. Покажем, что L(G) = L(M). Действительно, если w ∈ L(M), то по правилам построенной грамматики возможен вывод w⇒ #q0 w⇒ #q0 w#⇒* #αqaβ#⇒* #αX1 β#⇒* #αX2 ⇒* X0 , или, в случае w = ε w⇒ #q0 ⇒ #q0 #⇒ #X2 ⇒ X0 . Следовательно w ∈ L(G). В обратную сторону, пусть w ∈ L(G). Если w = ε, то существует вывод по грам­ матике G из #q0 # в X0 . Это подразумевает, что q0 ∈ F , а следовательно ε ∈ L(M). Если же w ̸= ε, то по грамматике G существует вывод w ⇒* #αqaβ# ⇒* X0 , где q ∈ F , a ∈ Γ, α, β ∈ Γ* , qa — финализирующая цепочка. Это означает, что w ∈ L(M). Утверждение 3. Любой язык типа 0 допускается машиной Тьюринга. 6. Регулярные и контекстно-свободные языки 6.1. Регулярные множества Определение 89 (Регулярное множество). Пусть задан некоторый алфавит Σ. Тогда регулярное множество можно определить следующим образом. 1. ∅ — регулярное множество. 2. {ε} — регулярное множество. 3. Если a ∈ Σ, то {a} — регулярное множество. 4. Если L1 и L2 — регулярные множества, то L1 ∪ L2 , L1 L2 и L*1 — регулярные множества. Пример 45. Рассмотрим множество L1 = {ab, ba}. Его можно представить в виде L1 = (AB) ∪ (BA), где A = {a}, а B = {b}. A и B — регулярные множества, следовательно регулярны и множества AB и BA, а значит регулярно и L. Пример 46. Рассмотрим множество L2 = {01k | k > 0}. Это множество можно пред­ ∞ ⋃︀ ставить в виде L2 = AB, где A = {0}, а B = {1}k = {1}* . Т.к. A - регулярное k=0 множество, и B — итерация регулярного множества — регулярное множество, то L2 — регулярное множество. Определение 90 (Регулярный язык). Язык, являющийся регулярным множеством на­ зывают регулярным. 6.2. Регулярные выражения Для записи регулярных множеств используют так называемые регулярные выра­ жения. Определение 91 (Регулярное выражение). Регулярные выражения определяются сле­ дующим образом. 1. ∅ — регулярное выражение для пустого множества. 2. ε — регулярное выражение для множества {ε}. 3. Если a ∈ Σ, то a — регулярное выражение для множества {a}. 4. Если α — регулярное выражение для регулярного множества A и β — регу­ лярное выражение для регулярного множества B, то α + β, (α)(β), (α)* и (α)+ — регулярные выражения для регулярных множеств A ∪ B, AB, A* , A+ соответственно. 77 В регулярных выражениях для операций приняты следующие приоритеты: самый высокий приоритет у операций итерации и положительной итерации, более низкий приоритет у операции конкатенации, и самый низкий приоритет у операции объеди­ нения. Круглые скобки в регулярных выражениях можно опускать в случаях, если это не приведет к нарушению порядка выполнения операций. Таким образом множество L1 из примера 45 можно задать с помощью регулярного выражения ab + ba, а множество L2 из примера 46 — с помощью выражения 01* . Для любого регулярного языка можно найти множество различных регулярных выражений определяющих его. Например легко проверить, что регулярные выраже­ ния 0 + 01+ , 0(ε + 1 + 1* )* так же будут определять язык L2 из примера 46. Регулярные выражения, определяющие одно и то-же регулярное множество, называют эквивалент­ ными. Принимая во внимание, что регулярные выражения представляют собой запись операций над множествами, можно определить ряд закономерностей для эквивалент­ ных преобразований регулярных выражений. Некоторые из них представлены в сле­ дующей лемме. Лемма 3 (Эквивалентные регулярные выражения). Если α, β и γ — регулярные вы­ ражения, то справедливы следующие соотношения. 1) 2) 3) 4) 5) 6) 7) α+β =β+α α + (β + γ) = (α + β) + γ α(β + γ) = αβ + αγ αε = εα = α α* = α + α* α+α=α α+ = αα* 8) ∅* = ε 9) α(βγ) = (αβ)γ 10) (α + β)γ = αγ + βγ 11) ∅α = α∅ = ∅ 12) (α* )* = α* 13) α + ∅ = α 14) α(βα)* = (αβ)* α Доказательство леммы напрямую следует из свойств операций над языками. Пример 47. Рассмотрим регулярное выражение γ = (0* + ε)* (1 + 1+ ). В силу определе­ ния операции итерации имеем γ = ((0+ +ε)+ε)* (1+1+ ). В силу соотношения 2 получим γ = (0+ +ε+ε)* (1+1+ ). Применяем соотношение 6, получая γ = (0+ +ε)* (1+1+ ). При­ меняем определение операции положительной итерации, получим γ = (0* )* (1 + 1+ ). По соотношению 12 γ = 0* (1 + 1+ ). Из 3 — γ = 0* 1(ε + 1* ). Применяя соотношения 2, 6 и определение операции итерации получим γ = 0* 11* . По определению операции положительной итерации γ = 0* 1+ . 78 Общее преобразование можно провести намного быстрее если помнить, что опе­ рации конкатенации и объединения — это операции над множествами. 6.3. Уравнения с регулярными коэффициентами Определение 92 (Уравнение с регулярными коэффициентами). Уравнением с регу­ лярными коэффициентами называется уравнение вида X = f (X), где f — регулярное выражение, а X — переменная. Решением уравнения с регулярными коэффициентами является множество слов, подставляя которое вместо имени переменной в левую и правую части уравнения получают тождество. Пример 48. Рассмотрим уравнение с регулярными коэффициентами X = 0X1 + ε. Решением данного уравнения является множество слов X = {0n 1n | n > 0}. Дей­ ствительно, если подставим это решение в правую часть уравнения, то получим 0X1 + ε = 0{0n 1n | n > 0}1 + ε = {0n+1 1n | n > 0}1 + ε = {0n+1 1n+1 | n > 0} + ε = {0k 1k | k > 1} + ε = {0k 1k | k > 0} = X. Нас будут интересовать уравнения с регулярными коэффициентами, решением которых являются регулярные множества, т. е. множества, которые можно задать с помощью регулярных выражений. Определение 93 (Леволинейное уравнение с регулярными коэффициентами). Леволи­ нейным уравнением с регулярными коэффициентами называется уравнение вида X = Xα + β, где X — переменная, а α, β — регулярные выражения без переменных. Лемма 4 (О решении леволинейного уравнения с регулярными коэффициентами). Решением леволинейного уравнения с регулярными коэффициентами X = Xα + β, (6.1) X = βα* . (6.2) является значение 79 Доказательство. Подставив решение (6.2) в обе части (6.1), получим βα* = βα* α + β. Преобразуем правую часть. βα* = β(α+ + ε) и далее βα* = βα* . Получили тождество. Замечание 4. В случае, если в (6.1) множество, определенное регулярным выраже­ нием α, содержит ε, то уравнение (6.1) имеет бесконечно много решений вида X = (β + γ)α* , для любого языка γ (не обязательно регулярного). В случае наличия множества решений одного уравнения рассматривают в качестве единственного решения так называемую минимальную неподвижную точку. Определение 94 (Минимальная неподвижная точка уравнения с регулярными коэф­ фициентами). Минимальной неподвижной точкой уравнения с регулярными коэффи­ циентами X = f (X) является такое X ′ , что при наличии любого другого решения X ′′ выполняется соотношение X ′ ⊆ X ′′ . Минимальной неподвижной точкой леволинейного уравнения с регулярными ко­ эффициентами является решение (6.2). Пример 49. Пусть задано уравнение X = X0 + X1(11 + 0)+ + X + 0 + 01. Вынесем X за скобку, получим X = X(0 + 1(11 + 0)+ + ε) + 0 + 01. Здесь α = 0+1(11+0)+ +ε, а β = 0+01. Минимальной неподвижной точкой уравнения будет X = (0 + 01)(0 + 1(11 + 0)+ + ε)* . 80 Замечание 5. Аналогичным образом можно ввести праволинейное уравнение с регу­ лярными коэффициентами — уравнение вида X = αX + β. Минимальной неподвижной точкой такого уравнения будет X = α* β. Определение 95 (Леволинейная система уравнений с регулярными коэффициентами). Стандартной леволинейной системой уравнений с регулярными коэффициентами на­ зывают систему вида X1 = X1 α11 + X2 α12 + X3 α13 + · · · Xn α1n + β1 X2 = X1 α21 + X2 α22 + X3 α23 + · · · Xn α2n + β2 ··· Xn = X1 αn1 + X2 αn2 + X3 αn3 + · · · Xn αnn + βn где Xi — переменные, а αij , βi — регулярные выражения (6.3) без переменных, 0 < i, j 6 n. Определение 96 (Минимальная неподвижная точка системы уравнений с регулярными коэффициентами). Минимальной неподвижной точкой системы уравнений с регуляр­ ными коэффициентами (6.3) является такое решение X1′ , X2′ , . . . , Xn′ , что при наличии любого другого решения X1′′ , X2′′ , . . . , Xn′′ выполняется соотношение Xi′ ⊆ Xi′′ для всех i, 1 6 i 6 n. Пользуясь выражением (6.2) для решения леволинейного уравнения с регуляр­ ными коэффициентами можно решать систему уравнений (6.3) методом исключения переменных. Т. е., например, из первого уравнения системы (6.3) можно получить X1 = (X2 α12 + X3 α13 + · · · Xn α1n + β1 )α*11 = X2 α12 α*11 + X3 α13 α*11 + · · · Xn α1n α*11 + β1 α*11 . Тем самым, можем исключить переменную X1 из остальных уравнений, подставив в них полученное выражение вместо X1 . Исключая последовательно все переменные получим для последней из них решение, не зависящее от других переменных. Про­ водя подстановки полученных решений в обратном порядке найдем решение для всей системы уравнений. Можно доказать, что такой метод исключения состояний выдает минимальную неподвижную точку леволинейной системы уравнений с регулярными коэффициента­ ми. Пример 50. Рассмотрим следующую систему уравнений. X1 = X2 0 + X1 1 + ε X2 = X3 0 + X2 1 X3 = X1 0 + X3 1 81 * Первое уравнение представим в виде X1 = (X2 0 + ε)1 , подставим во второе и третье уравнение и раскроем скобки. Получим новую систему X1 = X2 01* + 1* X2 = X3 0 + X2 1 X3 = X2 01* 0 + 1* 0 + X3 1 Второе уравнение представим в виде X2 = X3 01* , подставим в третье уравнение, получим X1 = X2 01* + 1* X2 = X3 01* X3 = X3 01* 01* 0 + 1* 0 + X3 1 Получим решение для X3 и подставим его в первое и второе уравнения. Получим X1 = X2 01* + 1* X2 = 1* 0(01* 01* 0 + 1)* 01* X3 = 1* 0(01* 01* 0 + 1)* Полученное решение для X2 подставим в X1 . X1 = 1* 0(01* 01* 0 + 1)* 01* 01* + 1* X2 = 1* 0(01* 01* 0 + 1)* 01* X3 = 1* 0(01* 01* 0 + 1)* Полученные регулярные выражения для Xi , i = 1, 2, 3, есть решение исходной систе­ мы. Теорема 19 (О регулярности языков типа 3). Язык определяется регулярным вы­ ражением тогда и только тогда, когда это язык типа 3. Доказательство. Пусть L определен регулярным выражением над алфавитом Σ = {a1 , . . . , ar }. Это означает, по определению, что L получен из конечных языков ∅, {a1 }, . . . , {ar } с помощью конечного числа регулярных операций. По теореме 5 следует, что L — язык типа 3. В обратную сторону. Пусть L — язык типа 3, определенный грамматикой G = (N , Σ, P, S). Представим каждое правило A → α ∈ P в виде уравнения A = α от­ носительно переменных — нетерминальных символов. Сложим правые части уравне­ ний, имеющих одинаковые левые части. Получим систему уравнений с регулярными коэффициентами относительно множества переменных N . Решая эту систему полу­ чим регулярное выражение для нетерминала S — регулярное выражение для языка, определенного грамматикой G. 82 Пример 51. Рассмотрим регулярное выражение (0 + 1)* 2. В этом регулярном вы­ ражении присутствуют операции объединения, итерации и конкатенации. Построим праволинейную грамматику определяющую тот же язык. Для языков {0}, {1} и {2} определим грамматики (по Теореме 4) G0 = ({S0 }, {0, 1, 2}, {S0 → 0}, S0 ), G1 = ({S1 }, {0, 1, 2}, {S1 → 1}, S1 ), G2 = ({S2 }, {0, 1, 2}, {S2 → 2}, S2 ) соответственно. Построим для регулярного выражения 0+1 грамматику G3 = ({S3 , S0 , S1 }, {0, 1, 2}, P3 , S3 ) по грамматикам G0 и G1 так как описано в Теореме 5. Здесь P3 будет опреде­ ляться следующим образом: S3 → S0 | S1 S0 → 0 S1 → 1 Согласно Теореме 5 для регулярного выражения (0 + 1)* по грамматике G3 по­ строим грамматику G4 = ({S4 , S3 , S0 , S1 }, {0, 1, 2}, P4 , S4 ), где P4 — это следующее множество правил. S4 S3 S0 S1 → ε | S3 → S0 | S1 → 0 | S3 0 → 1 | S3 1 Согласно Теореме 5 для регулярного выражения (0 + 1)* 2 по грамматикам G4 и G2 построим грамматику G5 = ({S4 , S3 , S0 , S1 , S2 }, {0, 1, 2}, P5 , S2 ), где P5 — это следующее множество правил. S2 S4 S3 S0 S1 → S4 2 → ε | S3 → S0 | S1 → 0 | S3 0 → 1 | S3 1 Полученная грамматика является леволинейной грамматикой, определяющей тот же язык, что и исходное регулярное выражение. Пример 52. Рассмотрим грамматику S → A0 | B1 | ε A → A0 | B1 | 2 B → B0 | A1 83 Заменим множество правил на систему уравнений с регулярными коэффициентами S = A0 + B1 + ε A = A0 + B1 + 2 B = B0 + A1 Выражаем B из последнего уравнения B = A10* и подставляем в первое во второе уравнения, получим S = A0 + A10* 1 + ε A = A0 + A10* 1 + 2 B = A10* Выражаем A из второго уравнения A = 2(0 + 10* 1)* и подставляем в первое уравнение. Получим S = 2(0 + 10* 1)* 0 + 2(0 + 10* 1)* 10* 1 + ε A = 2(0 + 10* 1)* B = A10* Можно преобразовать выражение для S к виду S = 2(0+10* 1)+ +ε. Это выражение и будет являться регулярным выражением определяющим тот же язык, что и исходная праволинейная грамматика. Теорема 20 (О замкнутости языков типа 3 относительно зеркального отражения и подстановки). Класс языков L3 замкнут относительно зеркального отражения, подстановки и произвольного гомоморфизма. Доказательство. Пусть L — язык типа 3 определенный регулярным выражением γ. Тогда LR определяется регулярным выражением γ′ , полученным из γ заменой (αβ) на (βα) для всевозможных α и β, т. е. заменой порядка умножения на противоположный во всех конкатенациях. Т. к. любой язык типа 3 можно определить регулярным выражением, операция подстановки заключается в подстановке одних регулярных выражений в другие. 6.4. Самовставленные языки Определение 97 (Линейная грамматика). Грамматика G = (N , Σ, P, S) называется ли­ нейной, если любая продукция в множестве P находится в одной из следующих форм A → αBβ, A → γ, (*) 84 где A, B ∈ N , α, β, γ ∈ Σ* . Если в линейной грамматике во всех правилах вида (*) α = ε, то грамматика называется леволинейной. Если в линейной грамматике во всех правилах вида (*) β = ε, то грамматика называется праволинейной. Теорема 21 (О праволинейности языков типа 3). Класс L3 совпадает с семейством языков, порожденных праволинейными грамматиками. Доказательство. Пусть G — порождающая грамматика типа 3. Обозначим через GR грамматику полученную из G заменой правой части на ее зеркальное отражение. Тогда GR — праволинейная грамматика. Более того, GR порождает язык (L(G))R . И в обратную сторону. Если G — праволинейная грамматика, то GR — грамматика типа 3, порождающая язык (L(G))R . Теорема 21 доказана на основании теоремы 20. Определение 98 (Самовставленная грамматика). Грамматика типа 2 G = (N , Σ, P, S) называется самовставленной (самовложенной) если A ⇒G* αAβ для некоторого A ∈ N и α, β ∈ Σ+ . Определение 99 (Самовставленный язык). Язык типа 2 называется самовставлен­ ным (самовложенным) языком, если все грамматики его определяющие — самовстав­ ленные. Теорема 22 (О несамовставленных языках типа 2). Язык является языком типа 3 если и только если он несамовставленный язык типа 2. Доказательство. Так как нет самовставленных грамматик типа 3, делаем заключе­ ние, что если язык самовставленный, он не является языком типа 3. В обратную сторону, пусть L порождается несамовставленной грамматикой типа 2 G = (N , Σ, P, S). Не теряя общности, предположим, что для любого A ∈ N есть вывод по правилам грамматики S ⇒* αAβ для некоторых α, β ∈ (N + Σ)* (т. к. иначе все продукции, включающие A могут быть удалены из множества правил P без изменения языка L). Рассмотрим 2 случая. 1. Пусть для каждого A ∈ N есть вывод из A ⇒* αSβ для некоторых α, β ∈ (N + Σ)* . Любая продукция в P, содержащая нетерминалы в правой части 85 имеет одну из форм A → αBβ, (6.4) A → αB, (6.5) A → Bβ, (6.6) A → B, (6.7) где A, B ∈ N , α, β ∈ (N + Σ)+ . Если P содержит продукцию вида (6.4), то у нас должен иметься вывод A ⇒ αBβ ⇒* αα1 Sβ1 β ⇒* αα1 α2 Aβ2 β1 β, для некоторых цепочек α1 , α2 , β1 , β2 ∈ (N + Σ)* . Т. к. α ̸= ε и β ̸= ε, то получили, что грамматика G самовставленная, что невозможно. Такое же противоречие получаем, когда грамматика G содержит правила вида (6.5) и (6.6) одновременно. Таким образом если P содержит правила в форме (6.5), то во всех правилах вида (6.5) цепочка α — терминальная. Это означает, что грамматика G — праволинейная. Аналогично, если P содержит правила в фор­ ме (6.6), то грамматика G — леволинейная. В любом случае G — грамматика типа 3 по Теореме 21. Очевидно, что L(G) — язык типа 3, если в P нет про­ дукций вида (6.4)-(6.6). 2. Пусть существует нетерминал A′ ∈ N такой, что не существует вывода A′ ⇒* αSβ ни для каких α, β ∈ (N + Σ)* . Доказательство того, что язык L(G) — язык типа 3 проведем по индукции по числу n нетерминалов в грамматике G. Если n = 1 случай 2 невозможен, т. к. S ⇒* S, а значит язык L(G) — язык типа 3, по случаю 1. Предположим, что для n = k предположение верно и L(G) — язык типа 3. Пусть в грамматике k + 1 нетерминал. Рассмотрим грамматику G1 = (N − {S}, Σ, P ′ , A′ ), полученную из G удалением всех продукций, содержащих S, а также рас­ смотрим грамматику G2 = (N − {A′ }, Σ + {A′ }, P ′′ , S), полученную из G удалением всех продукций, содержащих A′ в левой части. 86 Оба языка L(G1 ) и L(G2 ) являются языками типа 3 по предположению индук­ ции или по условию случая 1. Очевидно, что L(G) — результат подстановки L(G1 ) вместо A′ в L(G2 ). По теореме 20 язык L(G) — язык типа 3. Теорема 23 (Об эквивалентности представлений языков типа 3). Для языка L сле­ дующие условия эквивалентны. 1. L — язык типа 3. 2. L порожден праволинейной грамматикой. 3. L определяется регулярным выражением. 4. L допускаем конечным детерминированным автоматом. 5. L допускаем конечным недетерминированным автоматом. 6. L — несамовставленный язык типа 2. 6.5. Лемма о накачке для регулярных языков Теорема 24 (Лемма о накачке (о разрастании) регулярных языков). Пусть L — ре­ гулярный язык. Существует константа n, зависящая от L, для которой каждую цепочку w ∈ L, удовлетворяющую неравенству |w| > n, можно разбить на три цепочки w = xyz так, что выполняются следующие условия. 1. y ̸= ε. 2. |xy| 6 n. 3. Для любого k > 0 цепочка xyk z также принадлежит L. Доказательство. Пусть L — регулярный язык. Тогда L = L(M) для некоторого детер­ минированного конечного автомата M = (Q, Σ, P, q0 , F ). Пусть #Q = n. Рассмотрим произвольную цепочку w длиной не менее n, скажем w = a1 a2 a3 . . . am , где m > n и каждый ai — входной символ. Пусть p0 = q0 , p1 , p2 , . . . , pm — последовательность состо­ яний, через которую переходит автомат при приеме входной цепочки w. Т. е. p0 w ⇒ p1 a2 a3 . . . am ⇒ p2 a3 . . . am ⇒* pm . Рассмотрим первые n + 1 состояний из последовательности pi для i = 0, 1, . . . , n. Поскольку автомат M имеет n различных состояний, то найдутся два целых числа i и j (0 6 i < j 6 n), при которых pi = pj . Теперь разобьем цепочку w на xyz. 87 1. x = a1 a2 . . . ai . 2. y = ai+1 ai+2 . . . aj . 3. z = aj+1 aj+2 . . . am . Таким образом, x приводит автомат в состояние pi , y — из pi обратно в pi (так как pi = pj ), а z — остаток цепочки w. Т. е. p0 xyz ⇒* pi yz ⇒* pj z ⇒* pm . Причем цепочка x может быть пустой при i = 0, а z — при j = n = m. Однако цепочка y не может быть пустой, т. к. i строго меньше j. Когда на вход автомата поступает цепочка xyk z для k = 0 автомат переходит из начального состояния q0 в pi , прочитав x. Поскольку pi = pj , то z переводит M из состояния pi в допускающее состояние. Если же k > 0, то при x автомат переходит из q0 в pi , затем, читая yk циклически проходит через pi , и, наконец, по z переходит в заключительное состояние. Таким образом, для любого k > 0 цепочка xyk z также распознается автоматом M, а значит, принадлежит языку L. С помощью леммы о накачке можно доказать нерегулярность некоторого предла­ гаемого языка. Пример 53. Покажем, что язык L = {0n 1n | n > 0} нерегулярен. Предположим, что он регулярен. Тогда, согласно лемме о накачке регулярных языков, достаточно длинная цепочка w = 0m 1m этого языка может быть представлена в виде w = xyz, где y ̸= ε, и любая цепочка xyk z, k > 0, будет принадлежать языку L, а значит представима в виде 0r 1r для какого-то соответствующего r. Предположим, что так оно и есть. Пусть y = 0r 1s , где r и s положительные числа, одновременно не обращающие­ ся в 0. Значит w = 0m−r 0r 1s 1m−s . Цепочка xy2 z = 0m−r 0r 1s 0r 1s 1m−s также должна принадлежать языку L. Предположим r = 0, то получим, что xy2 z = 0m 1s 1s 1m−s = 0m 1m+s , но из предполо­ жения y ̸= ε следует s ̸= m+s, а значит цепочка xy2 z = 0m 1m+s не принадлежит языку L, а значит предположение r = 0 — неверно. Значит r ̸= 0. Аналогично показывается s ̸= 0. 88 Так как r ̸= 0 и s ̸= 0, то цепочка xy2 z = 0m−r 0r 1s 0r 1s 1m−s должна принадлежать L. Но это не так, из-за того, что в последней цепочке есть подцепочка 10, чего в цепочках языка L случаться не может. Мы перебрали все возможные случаи r и s и не нашли подходящей пары, а значит нет такого представления w = xyz, а значит язык L нерегулярен. Пример 54. Докажем нерегулярность языка Lpr , образованного всеми цепочками из единиц, длины которых — простые числа. Предположим, что Lpr — регулярен. Тогда должна существовать константа n, удовлетворяющая условиям леммы о накачке. Рас­ смотрим некоторое простое число p > n + 2. Такое число должно существовать, по­ скольку множество простых чисел бесконечно. Пусть w = 1p . Согласно лемме о накачке можно разбить цепочку w = xyz так, что y ̸= ε и |xy| 6 n. Пусть |y| = m. Тогда |xz| = p − m. Рассмотрим цепочку xyp−m z, которая по лемме о накачке должна принадлежать языку Lpr , если он действительно регулярен. Однако |xyp−m z| = |xz| + (p − m)|y| = p − m + (p − m)m = (m + 1)(p − m). Похоже, что число |xyp−m z| не простое, так как имеет два множителя m + 1 и p − m. Однако нужно еще убедиться, что ни один из этих множителей не равен 1, потому что тогда (m + 1)(p − m) может быть простым. Из неравенства y ̸= ε следует m > 1 и m + 1 > 1. Кроме того, m = |y| 6 n, а p > n + 2, поэтому p − m > 2. Пришли к противоречию. Таким образом язык Lpr нерегулярен. 6.6. Деревья вывода и однозначность грамматик типа 2 Рассмотрим наглядный метод описания любого вывода в грамматике типа 2. Определение 100 (Дерево вывода). Пусть G = (N , Σ, P, S) — грамматика типа 2. Упорядоченное дерево есть дерево вывода (дерево разбора) для G, если 1) каждый узел имеет метку — символ из N ∪ Σ ∪ {ε}; 2) метка корня — S; 3) если узел имеет по крайней мере одного потомка, то его метка должна быть нетерминалом; 4) если узлы n1 , n2 , . . . , nk — прямые потомки узла n, перечисленные слева на­ право, с метками A1 , A2 , . . . , Ak соответственно, а метка узла n есть A, то 89 правило A → A1 A2 . . . Ak ∈ P. Причем узел ni может быть помечен ε только в случае если ni — единственный потомок узла n, и правило A → ε ∈ P. Пример 55. Рассмотрим грамматику G = ({S, A}, {a, b}, P, S), где P = {S → aAS, S → a, A → SbA, A → ba, A → SS}. На рис. 6.1 вывод цепочки aabbaa в грамматике G представлен в виде дерева. S a A S b a S A b a a Рис. 6.1. Дерево вывода S ⇒ aAS ⇒ aSbAS ⇒ aSbAa ⇒ aabAa ⇒ aabbaa Определение 101 (Крона дерева вывода). Кроной дерева вывода называют цепочку, составленную из меток всех листьев этого дерева, перечисленных слева направо. В последнем примере цепочка aabbaa является кроной приведенного дерева выво­ да. Определение 102 (Сечение дерева вывода). Сечением дерева вывода называют набор узлов этого дерева такой, что: 1) никакие два узла в сечении не принадлежат одному и тому же пути от корня до листа; 2) нельзя добавить ни одного узла в сечение, чтобы не нарушилось правило 1. В любом дереве множество состоящее только из корня дерева является сечением этого дерева. Также, множество всех листьев дерева является сечением. В последнем примере сечениями являются наборы {S}, {a, a, b, b, a, a}, {a, A, S}, {a, A, a}. Определение 103 (Крона сечения). Кроной сечения дерева вывода называют цепочку, составленную из меток всех узлов в сечении, перечисленных слева направо. Перечисленным выше сечениям соответствуют кроны S, aAS, aAa, aabbaa. Имеет место следующее утверждение. 90 Утверждение 4. Пусть G = (N , Σ, P, S) — КС-грамматика. Для цепочки α ∈ (N + Σ)* существует вывод S ⇒G* α тогда и только тогда, когда существует дерево вывода в грамматике G с кроной сечения α. Определение 104 (Неоднозначная грамматика). КС-грамматику G = (N , Σ, P, S) назы­ вают неоднозначной, если найдется хотя бы одна выводимая цепочка α ∈ (N + Σ)* , для которой существуют два разных дерева вывода с кроной сечения α. В противном случае грамматику называют однозначной Пример 56. Рассмотрим грамматику, которая представляет арифметические выраже­ ния типичного языка программирования (в несколько упрощенном виде). Ограни­ чимся только операциями сложения и умножения, а в качестве аргументов возьмем только идентификаторы, составленные из букв a и b, цифр 0 и 1. Рассмотрим грамма­ тику G = ({E, I }, {+, *, (, ), a, b, 0, 1}, P, E), в которой множество правил P составляют следующие правила → I | E + E | E * E | (E) → a | b | Ia | Ib | I0 | I1 E I (6.8) Рассмотрим выводимую цепочку E + E * E. Для этой цепочки существует два различных вывода в грамматике G: E ⇒E+E ⇒E+E*E (6.9) E ⇒E*E ⇒E+E*E (6.10) Здесь в первом выводе второе E заменяется на E * E, а во втором — первое E на E + E. На рис. 6.2 показаны два действительно различных дерева разбора. E E E + ∗ E (а) ∗ E E E E + E E (б) Рис. 6.2. Два дерева вывода с одной и той же кроной Разница между этими двумя выводами значительна. Когда рассматривается струк­ тура выражений, первый вывод говорит, что второе и третье выражения перемножают­ ся, и результат складывается с первым. Вместе с тем, второй вывод задает сложение 91 первых двух выражений и умножение результата на третье. Более конкретно, первый вывод задает, что 1 + 2 * 3 группируется как 1 + (2 * 3) = 7, а второй — что группирова­ ние имеет вид (1+2)*3 = 9. Очевидно, что первое из них (но не второе) соответствует нашему понятию о правильном группировании арифметических выражений. Поскольку грамматика (6.8) дает две различные структуры любой цепочке тер­ миналов, порождаемой заменой трех выражений в E + E * E идентификаторами, для обеспечения уникальности структуры она не подходит. В частности, хотя она может давать цепочкам как арифметическим выражениям правильное группирование, она также дает им неправильное. Для того, чтобы использовать эту грамматику выра­ жений в компиляторе, мы должны изменить ее, обеспечив правильное группирова­ ние. С другой стороны, само по себе существование различных выводов одной и той-же цепочки еще не означает неоднозначности грамматик. Пример 57. Для грамматики (6.8) рассмотрим два вывода для цепочки a + b E ⇒E+E ⇒I +E ⇒a+E ⇒a+I ⇒a+b E ⇒E+E ⇒E+I ⇒I +I ⇒I +b ⇒a+b Заметим, что настоящей разницы между структурами, заданными этими двумя выво­ дами, нет. В действительности, оба этих вывода приводят к одному и тому же дереву вывода. Не существует алгоритма, способного различить, является ли КС-грамматика неод­ нозначной. На практике, для многих конструкций, возникающих в обычных языках програм­ мирования, существует техника устранения неоднозначности. Так проблема с грамма­ тикой (6.8) типична, и мы исследуем устранение ее неоднозначности. Есть следующие две причины неоднозначности в грамматике (6.8). 1. Не учитываются приоритеты операторов, описываемых грамматикой. Необхо­ димо обеспечить, чтобы в однозначной грамматике была допустимой только структура, показанная на рис. 6.2, а. 2. Последовательность одинаковых операторов может группироваться как слева, так и справа. Поскольку операторы + и * ассоциативны, не имеет значения, группируем мы их слева или справа, но для исключения неоднозначности нам нужно выбрать что-то одно. 92 E E + T T T ∗ F F I I I a a a F Рис. 6.3. Дерево вывода для цепочки a + a * a и грамматики (6.11) Решение проблемы установления приоритетов состоит в том, что вводится несколь­ ко разных нетерминалов, каждый из которых представляет выражение, имеющее один и тот же уровень <связывающей мощности>. В частности, для грамматики (6.8) это решение может иметь следующий вид. 1. Сомножитель, или фактор, — это выражение, которое не может быть раз­ делено на части никаким примыкающим оператором, ни * ни +. Сомножите­ лями в нашем языке выражений являются только следующие выражения: a) идентификаторы. Буквы идентификатора невозможно разделить путем присоединения оператора; б) выражения в скобках, независимо от того, что находится между ними. 2. Слагаемое или терм, — это выражение, которое не может быть разорва­ но оператором +. В нашем примере терм представляет собой произведение одного или нескольких сомножителей. 3. Выражение будет обозначать любое возможное выражение. Следующая грамматика представляет собой тот же язык, что и грамматика (6.8), но является однозначной. E T F I → T | E +T →F |T *F → I | (E) → a | b | Ia | Ib | I0 | I1 (6.11) Так, например, для цепочки a + a * a в этой грамматике существует только одно дерево разбора, показанное на рисунке 6.3. 93 Определение 105 (Существенно неоднозначный язык). КС-язык L называется суще­ ственно неоднозначным, если все его грамматики неоднозначны. Если хотя бы одна грамматика языка L является однозначной, то L является однозначным языком. Теорема 25 (Об однозначности языков типа 3). Все языки типа 3 однозначны. Доказательство. Пусть L - язык типа 3, над терминальным алфавитом Σ. По теоре­ ме 23 L = L(M), для некоторого КДА M = (Q, Σ, P, q0 , F ). Отсюда, язык L порождается грамматикой G = (Q, Σ, P1 , q0 ), где P1 = {q → ar | q, r ∈ Q, a ∈ Σ, qa → r ∈ P} ∪ {q → ε | q ∈ F }. Грамматика G, очевидно, является однозначной. 6.7. Преобразования КС-грамматик Определение 106 (ε-правило). В грамматике типа 2 ε-правилом называют любое пра­ вило вида A → ε, где A — нетерминальный символ. Определение 107 (A-правило). В грамматике типа 2 A-правилом называют любое правило вида A → α, где A — нетерминальный символ, α — произвольная цепочка. Определение 108 (Цепное правило). В грамматике типа 2 цепным правилом называют любое правило вида A → B, где A и B — нетерминальные символы. Определение 109 (Грамматика без ε-правил). КС-грамматику G = (N , Σ, P, S) называ­ ют грамматикой без ε правил, если в ней отсутствуют ε-правила, или присутствует правило S → ε, при условии, что S не встречается в правых частях правил. Теорема 26 (О грамматиках без ε-правил). Для любого языка типа 2 найдется его определяющая грамматика без ε-правил. Доказательство. Пусть L — язык типа 2, а G = (N , Σ, P, S) — КС-грамматика его определяющая. Найдем множество U = {A ∈ N | A ⇒* ε}. (6.12) 94 Для этого определим U1 = {A | A → ε ∈ P}, Ui+1 = Ui ∪ {A | A → α ∈ P, α ∈ Ui* }, i > 1. Т. к. Ui представляют собой монотонно увеличивающиеся подмножества множества N , найдется число k такое, что Uk = Uk+v , v = 1, 2, . . . . Положим U = Uk . Таким образом, ε ∈ L(G) тогда и только тогда, когда S ∈ U . Построим грамматику G′ = (N , Σ, P ′ , S), в которой продукция A → α принадлежит множеству P ′ тогда и только тогда, когда α ̸= ε и найдется продукция A → β ∈ P такая, что α получается из β удалением 0 или более символов из U . Справедливо, что L(G′ ) = L(G)−{ε}. Действительно, включение L(G′ ) ⊆ L(G)−{ε} очевидно из (6.12). Обратное включение устанавливается при рассмотрении грамма­ тики G1 = (N , Σ, P ∪ P ′ , S). Ясно, что L(G) ⊆ L(G1 ). Если w ∈ L(G) и w ̸= ε, то w ∈ L(G′ ), т. к. все применения продукций A → ε могут быть заменены некоторыми применениями продукций из P ′ . Если ε ∈ L(G), построим грамматику G′′ : G′′ = (N ∪ {S′ }, Σ, P ′ ∪ {S′ → ε, S′ → S}, S′ ). По построению L(G′′ ) = L(G′ ) ∪ {ε}. Как грамматика G′ , так и грамматика G′′ — грамматики без ε-правил. Следствие 26.1. Любой язык типа 2 является языком типа 1. Пример 58. Рассмотрим грамматику S → AB A → aAA | ε B → bBB | ε Применим к ней метод, предложенный в доказательстве последней теоремы. Сначала, определим, что U = {A, B, S}. Правило S → AB влечет за собой включение в новое множество правил P ′ правил S → AB | A | B. Из-за правила A → aAA включаем в P ′ правила A → aAA | 95 aA | a. Процесс посторяем для всех правил исходной грамматики, не являющихся ε-правилами. В итоге получим множество P ′ в следующем виде. S → AB | A | B A → aAA | aA | a B → bBB | bB | b Так как S ∈ U , то включаем новый начальный нетерминал S′ в множество нетер­ миналов и добавляем два правила S′ → S | ε. Окончательная грамматика S′ → S | ε S → AB | A | B A → aAA | aA | a B → bBB | bB | b Теорема 27 (О грамматиках без цепных правил). Для любого языка типа 2 най­ дется грамматика без цепных правил его определяющая. Доказательство. Пусть L — язык типа 2, а G = (N , Σ, P, S) — КС-грамматика его определяющая. Согласно теореме 26 можно предположить, что G — грамматика без ε-правил. Для каждого X ∈ N найдем U (X) = {B ∈ N | B ⇒* X}. (6.13) Для этого определим U1 (X) = {X}, Ui+1 (X) = Ui ∪ {A | A → B ∈ P, B ∈ Ui (X)* }, i > 1. Т. к. Ui (X) представляют собой монотонно увеличивающиеся подмножества множе­ ства N , найдется число k такое, что Uk = Uk+v , v = 1, 2, . . . . Положим U (X) = Uk (X). Построим грамматику G′ = (N , Σ, P ′ , S), в которой продукция A → β принадле­ жит множеству P ′ тогда и только тогда, когда это не цепное правило и найдется нетерминал B такой, что существует правило B → β ∈ P и A ∈ U (B). Покажем, что L(G) ⊆ L(G′ ). Действительно, рассмотрим цепочку w ∈ L(G). По­ строим дерево вывода для этой цепочки по грамматике G. Заметим, что по принципу 96 построения грамматики G′ все нецепные правила грамматики G включаются в P ′ . Применение цепного правила A → B при выводе цепочки w выльется в появление в дереве вывода узла с меткой A, имеющего единственного потомка с меткой B. A B Наличие в дереве вывода цепи A0 A1 .. . Ak для k > 1 соответствовует последовательности применений цепных правил A0 → A1 , . . . , Ak−1 → Ak . Пусть A0 — начальный, а Ak — конечный узел такой цепи, т. е. узел A0 появился не в результате применения цепного правила; к нетерминалу Ak применяется не цепное правило. Допустим, что к нетерминалу Ak применяется правило Ak → α, α ∈ (N + Σ)* . Согласно 6.13 A0 ∈ U (Ak ). Принимая это во внимание и в связи с тем, что Ak → α ∈ P, можем сделать вывод, что правило A0 → α должно содержаться в P ′ . Заменим поддерево A0 -· · · -Ak -α на A0 -α. Такая замена будет соответствовать применению правила грамматики G′ . Крона дерева от такой замены не изменится. По­ вторим этот процесс для каждой цепи меток-нетерминалов в нашем дереве. Получим дерево, построенное по правилам грамматики G′ с той же кроной. Т. к. кроной дерева является цепочка w, делаем вывод, что любое слово языка L(G) содержится в L(G′ ). В обратную сторону. Рассмотрим вывод цепочки w ∈ L(G′ ). Пусть шаг вывода αi ⇒G′ αi+1 происходит в результате применения правила A → β ∈ P ′ . Но наличие такого правила в P ′ предполагает, что A ∈ U (B) для некоторого нетерминального символа B (возможно B = A) и в грамматике G присутствует правило B → β. Факт A ∈ U (B) означает, что A ⇒G B. Следовательно αi ⇒G* αi+1 . Так как шаг вывода был выбран произвольно, S ⇒G* w. В силу произвольного выбора цепочки w L(G′ ) ⊆ L(G). Таким образом L(G′ ) = L(G). 97 Определение 110 (Нормальная форма Хомского). КС-грамматика G = (N , Σ, P, S) на­ зывается грамматикой в нормальной форме Хомского, если в ней нет ε-правил и любое правило, отличное от S → ε имеет вид: 1. A → BC, где B, C ∈ N , 2. A → a, где a ∈ Σ. Теорема 28 (О грамматиках в нормальной форме Хомского). Для любого языка типа 2 найдется грамматика в нормальной форме Хомского. Доказательство. Пусть L — язык типа 2, а G = (N , Σ, P, S) — КС-грамматика его определяющая. Согласно теореме 26 и теореме 27 можно, не теряя общности предпо­ ложить, что G — грамматика без ε-правил и без цепных правил. Тогда P может состоять из продукций вида S → ε, A → a, (6.14) a ∈ Σ, A → X1 X2 , (6.15) X1 , X2 ∈ (N + Σ), A → X1 X2 . . . Xk , k > 2, X1 , . . . , Xk ∈ (N + Σ). (6.16) (6.17) Построим грамматику G′ = (N ′ , Σ, P ′ , S), в которой в множество P ′ включены 1) все правила из P вида (6.14) и (6.15); 2) для каждого правила из P вида (6.16) правила вида A → X1′ X2′ , где Xi′ = Xi , если Xi ∈ N и Xi′ — новый нетерминал в противном случае; 3) для каждого правила из P вида (6.17) правила вида A → X1′Y1 , Y1 → X2′Y2 , ... ′ Yk−2 → Xk−1 Xk′ , где Xi′ = Xi , если Xi ∈ N и Xi′ — новый нетерминал в противном случае, и все Yi — новые нетерминалы; 4) правила Xi′ → Xi , для всех новых нетерминалов Xi′ , введенных в пунктах 2-3. Легко проверить, что L(G′ ) = L(G). 98 6.8. Лемма о накачке для КС-языков Лемма 5 (О длине выводимой цепочки). Пусть дано дерево разбора для граммати­ ки G = (N , Σ, P, S) в нормальной форме Хомского. Пусть кроной дерева является цепочка α ∈ Σ+ (Рис. 6.4). Если n — наибольшая длина пути от корня к листьям, то |α| 6 2n−1 . S α Рис. 6.4. Дерево вывода цепочки α по грамматике G Доказательство. По индукции: Пусть n = 1. Длина пути есть число ребер, т.е. на 1 меньше числа узлов, участвующих в этом пути. Т. о., дерево с максимальной длиной пути состоит из корня и листа, отмеченного терминалом (Рис. 6.5). Цепочка α является этим терминалом, и |α| = 1. Т.к. 2n−1 = 20 = 1, то предположение леммы для n = 1 верно. S α Рис. 6.5. Шаг индукции n = 1 S A B α1 α2 Рис. 6.6. Шаг индукции n > 1 Пусть n > 1. Корень дерева использует правило, которое должно иметь вид S → AB (Рис. 6.6), т.к. n > 1 (т.е. нельзя начать дерево, использовав продукцию с терминалом). Ни один из путей в поддеревьях с корнями в A и B не может иметь 99 длину больше, чем n − 1. По предположению индукции эти два поддерева имеют кро­ ны длины не более 2n−2 . Крона всего дерева представляет собой конкатенацию этих двух крон, а следовательно имеет длину не превышающую 2n−2 + 2n−2 = 2n−1 . Теорема 29 (Лемма о накачке (о разрастании) для КС-языков). Пусть L - КС-язык. Тогда существует такая константа n, что если z — произвольная цепочка из L, длина которой не меньше n, то можно записать z = uvwxy, причем выполняются следующий условия. 1. |vwx| 6 n (средняя часть не слишком длинная); 2. vx ̸= ε (хотя бы одна из цепочек v и x не пуста); 3. uvi wxi y ∈ L, ∀i > 0. Доказательство. Для L найдем грамматику G = (N , Σ, P, S) в нормальной форме Хомского. Пусть #N = m. Возьмем n = 2m . Предположим, что z ∈ L, |z| > n. По лемме 5 любое дерево разбора с кроной z имеет путь длинной не менее m + 1. Пусть самый длинный путь имеет длину k + 1, k > m. Тогда на этом пути встре­ чается k + 1 нетерминал A0 , A1 , A2 , . . . , Ak . Но N содержит всего m нетерминалов, поэтому хотя бы два из m + 1-го нетерминала на пути должны совпадать. Пусть Ai = Aj = A, где k − m 6 i 6 j 6 k. A0 S D  DS  D S  D S  S D  S D  S D Ai = Aj D  S CS  S S  S  C S C S  S  C S  S   S  Aj CC S  S  S S  S  S  S  S  S S   S  S S   S  S S   S  S S  u v w x y Рис. 6.7. Дерево разбора для исходной цепочки 100 A0 S D  DS  D S  D S  S D  S D  S D Ai = Aj D  S  SS S   S S   S S   S S   S S   S S w   S S   S S   S S   S S   S S y u Рис. 6.8. Накачивание цепочек v и x 0 раз A0 S D  DS  D S  D S  S D  S D  S Ai = Aj DD  S CS  S S   C S S C   S S C S   S   S Aj CC S   S S CS S   S S C S    S S C S    S S C S    S S  Aj CC S   S S S x  y u v S  S S   S S   S S   S S   S S  v w x Рис. 6.9. Накачивание цепочек v и x 2 раза Тогда дерево разбора можно разделить так, как показано на рис. 6.7. Цепочка w является кроной поддерева с корнем Aj . Цепочки v и x — это цепочки соответственно справа и слева от w в кроне большого поддерева с корнем Ai . Цепных правил в грамматике нет, а поэтому v и x не могут одновременно быть ε(хотя одна из них может). Наконец u и yобразуют части z, лежащие соответственно слева и справа от поддерева с корнем Ai . Если Ai = Aj = A, то по исходному дереву можно построить новое дерево разбора. Сначала можно заменить поддерево с корнем Aj , имеющее крону vwx, поддеревом с 101 корнем Aj , у которого крона w. Это допустимо, т.к. корни обоих поддеревьев отмечены одним и тем же нетерминалом A. Полученное дерево представлено на рис. 6.8. Оно соответствует случаю i = 0. Другая возможность представлена на рис. 6.9. Там поддерево с корнем Aj заменено поддеревом с корнем Ai . Это допустимо, т.к. корни поддеревьев совпадают. Кроной такого дерева является цепочка uv2 wx2 y. Можно далее продолжать процесс замены поддеревьев большими поддеревьями с целью получения кроны uvi wxi y для любого i. Итак в G существуют деревья разбора для всех таких цепочек. Мы выбирали Ai с условием k − i 6 m. Таким образом самый длинный путь в поддереве с корнем Ai имеет длину не более чем m + 1. По лемме 5 поддерево с корнем Ai имеет крону, длина которой не больше, чем 2m = n. Тем самым все утверждения теоремы доказаны.