Формальные языки

Определение 1.1.1. Будем называть натуральными числами

неотрицательные целые числа. Множество всех натуральных чисел {0, 1, 2, ...} обозначается N.

Определение 1.1.2. Алфавитом называется конечное непустое множество. Его элементы называются символами (буквами).

Определение 1.1.3.Словом (цепочкой, строкой, string) в алфавите

называется конечная последовательность элементов .

Пример 1.1.4. Рассмотрим алфавит = {a, b, c}. Тогда baaa является словом в алфавите .

Определение 1.1.5. Слово, не содержащее ни одного символа (то есть последовательность длины 0), называется пустым словом

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

Определение 1.1.6. Множество всех слов в алфавите

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

Замечание 1.1.7. Множество счетно. В самом деле, в алфавите

множество всех слов данной длины конечно, следовательно,

является объединением счетного числа конечных множеств.

Определение 1.1.8. Множество всех непустых слов в алфавите

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

Пример 1.1.9. Если = {a}, то = {a,aa,aaa,aaaa,...}.

Определение 1.1.10.

Если , то L называется языком

(или формальным языком) над алфавитом .

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

Пример 1.1.11. Множество {a, abb} является языком над алфавитом {a, b}.

Определение 1.1.12. Пусть . Тогда язык

называется дополнением языка L относительно алфавита . Когда из контекста ясно, о каком алфавите идет речь, говорят просто, что язык

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

Определение 1.1.13.

Если x и y - слова в алфавите , то слово xy (результат приписывания слова y в конец слова x) называется конкатенацией, (катенацией, сцеплением) слов x и y. Иногда конкатенацию слов x и y обозначают .

Определение 1.1.14.

Если x - слово и , то через xn

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

Пример 1.1.15. По принятым соглашениям ba3 = baaa и (ba)3 = bababa.

Пример 1.1.16.

Множество

является языком над алфавитом {a,b}. Этот язык содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa, baaaa и т. д.

Определение 1.1.17. Длина слова w, обозначаемая |w|, есть число символов в w, причем каждый символ считается столько раз, сколько раз он встречается в w.

Пример 1.1.18. Очевидно, что |baaa| = 4 и .

Определение 1.1.19. Через |w|a обозначается количество вхождений символа a в слово w.

Пример 1.1.20.

Если , то |baaa|a = 3, |baaa|b = 1 и |baaa|c = 0.

Упражнение 1.1.21. Перечислить слова языка , где

и .

Упражнение 1.1.22. Пусть . Равны ли языки

и ?

Упражнение 1.1.23. Пусть ,

и . Сколько слов содержит язык L1 - L2?

Упражнение 1.1.24. Пусть даны такие алфавиты и , что . В каком случае ?

Гомоморфизмы

Определение 1.3.1. Пусть и - алфавиты. Если отображение

удовлетворяет условию

для всех слов

и , то отображение h называется гомоморфизмом

(морфизмом).

Замечание 1.3.2.

Можно доказать, что если - гомоморфизм, то .

Замечание 1.3.3. Пусть

и . Тогда отображение , заданное равенством , является гомоморфизмом.

Замечание 1.3.4.

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

Замечание 1.3.5. Если - гомоморфизм и , то через h(L) обозначается язык .

Пример 1.3.6. Пусть

и гомоморфизм

задан равенствами h(a) = abba и . Тогда

Определение 1.3.7. Если - гомоморфизм и , то через h-1(L) обозначается язык .

Пример 1.3.8. Рассмотрим алфавит . Пусть гомоморфизм

задан равенствами h(a) = ab и h(b) = abb. Тогда

Упражнение 1.3.9. Пусть . Существует ли такой гомоморфизм , что h(abc) = bac и h(da) = ba?

Упражнение 1.3.10. Существуют ли такой язык

и такой гомоморфизм , что

и ?

Упражнение 1.3.11. Пусть . Существует ли такой гомоморфизм , что

и ?

Упражнение 1.3.12. Существуют ли такой язык

и такой гомоморфизм , что

и ?

Упражнение 1.3.13. Пусть - гомоморфизм, заданный соотношениями h(a) = a, h(b) = ba, h(c) = bb. Существуют ли такие слова u и v, что |u|<|v| и |h(u)|>|h(v)|?

Классы грамматик

Определение 1.5.1.

Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1, context-sensitive grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид , где , , , .

Пример 1.5.2. Грамматика

не является контекстной (последние три правила не имеют требуемого вида).

Определение 1.5.3.

Контекстно-свободной грамматикой (бесконтекстной грамматикой, КС-грамматикой, грамматикой типа 2, context-free grammar) называется порождающая грамматика, каждое правило которой имеет вид , где , .

Пример 1.5.4.

Грамматика

является контекстной, но не контекстно-свободной (последние пять правил не имеют требуемого вида).

Определение 1.5.5.

Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид

или , где , , , .

Грамматика

является контекстно-свободной, но не линейной (первые два правила не имеют требуемого вида).

Определение 1.5.7.

Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3, right-linear grammar) называется порождающая грамматика, каждое правило которой имеет вид

или , где , , .

Пример 1.5.8. Грамматика

является линейной, но не праволинейной (первое правило не имеет требуемого вида).

Пример 1.5.9. Грамматика

праволинейная. Она порождает язык .

Пример 1.5.10.

Грамматика

праволинейная.

Пример 1.5.11.

Грамматика

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

Определение 1.5.12.

Правила вида

называются -правилами или эпсилон-правилами.

Лемма 1.5.13.

Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без -правил является контекстной грамматикой.

Определение 1.5.14.

Классы грамматик типа 0, 1, 2 и 3 образуют иерархию Хомского (Chomsky hierarchy).

Определение 1.5.15. Язык называется языком типа 0 (контекстным языком, контекстно-свободным языком, линейным языком, праволинейным языком), если он порождается некоторой грамматикой типа 0 (соответственно контекстной грамматикой, контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

Пример 1.5.16.

Пусть дан произвольный алфавит

Тогда язык

является праволинейным, так как он порождается грамматикой

Упражнение 1.5.17. Какому классу принадлежит грамматика

Упражнение 1.5.18. Какому классу принадлежит грамматика

Упражнение 1.5.19. Найти праволинейную грамматику, порождающую язык .

Упражнение 1.5.20. Найти праволинейную грамматику, эквивалентную грамматике

Упражнение 1.5.21. Найти праволинейную грамматику, эквивалентную грамматике

Операции над языками

Определение 1.2.1.

Пусть . Тогда

Язык

называется конкатенацией

языков L1 и L2.

Пример 1.2.2. Если L1 = {a,abb} и L2 = {bbc,c}, то .

Упражнение 1.2.3. При каких положительных целых числах k, l, m, n существуют алфавит , язык

и язык , удовлетворяющие условиям , |L1| = l, |L2| = m,

Определение 1.2.4. Пусть . Тогда

Пример 1.2.5. Если L = {akbal | 0 < k < l}, то L2 = {akbalbam | 0 < k < l - 1, m > 1}.

Упражнение 1.2.6. Пусть

и L = {aa,ab}. Найти L3.

Определение 1.2.7. Итерацией языка (Kleene closure) языка L (обозначение L*) называется язык

Эта операция называется также звездочкой Клини

(Kleene star, star operation).

Пример 1.2.8.

Если

и L = \{aa,ab,ba,bb}, то

Упражнение 1.2.9. Пусть

и

Верно ли, что

Упражнение 1.2.10. Существует ли такой язык L, что выполняется неравенство

Определение 1.2.11. Обращением или зеркальным образом слова w (обозначается wR) называется слово, в котором символы, составляющие слово w, идут в обратном порядке.

Пример 1.2.12.

Если w = baaca, то wR = acaab.

Определение 1.2.13. Пусть . Тогда

Язык LR

называется обращением

языка L.

Упражнение 1.2.14. Существует ли такой язык L, что выполняется неравенство ?

Определение 1.2.15. Говорят, что слово x - префикс (Содержание) слова y (обозначение ), если y = xu для некоторого слова u.

Пример 1.2.16. Очевидно, что , ,

и .

Определение 1.2.17. Пусть . Тогда через Pref(L) обозначается множество, состоящее из всех префиксов слов языка L:

Множество Pref(L) называется множеством префиксов

языка L.

Определение 1.2.18 Говорят, что слово x - суффикс (конец) слова y (обозначение ), если y = ux для некоторого слова u.

Определение 1.2.19. Пусть . Тогда через Suf(L) обозначается множество, состоящее из всех суффиксов слов языка L:

Множество Suf(L) называется множеством суффиксов

языка L.

Определение 1.2.20. Говорят, что слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v.

Определение 1.2.21. Пусть . Тогда через Subw(L) обозначается множество, состоящее из всех подслов слов языка L.
Множество Subw(L) называется множеством подслов

языка L.

Определение 1.2.22. Слово a1a2...an

(длины ) называется подпоследовательностью (subsequence) слова y, если существуют такие слова u0, u1, ..., un, что u0a1u1a2...anun = y.

Замечание 1.2.23.

Все подслова слова y являются также подпоследовательностями слова y.

Определение 1.2.24. Пусть . Тогда через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством подпоследовательностей

языка L.

Пример 1.2.25. Рассмотрим язык L = {cba, c} над алфавитом {a, b, c}. Очевидно, что .

Определение 1.2.26. Функция

называется биекцией (bijection), если каждый элемент множества L является образом ровно одного элемента множества K (относительно функции f).

Определение 1.2.27. Множества K и L называются равномощными (of equal cardinality), если существует биекция из K в L.

Упражнение 1.2.28. Существуют ли такие языки L1 и L2, что языки

и неравномощны?

Упражнение 1.2.29. Существуют ли такие языки L1 и L2, что языки

и неравномощны?

Порождающие грамматики

Определение 1.4.1. Порождающей грамматикой (грамматикой типа 0, generative grammar, rewrite grammar) называется четверка , где N и - конечные алфавиты, , , P конечно и . Здесь - основной алфавит (терминальный алфавит), его элементы называются терминальными символами или терминалами (terminal), N - вспомогательный алфавит (нетерминальный алфавит), его элементы называются нетерминальными символами, нетерминалами, вспомогательными символами или переменными (nonterminal, variable), S - начальный символ (аксиома, start symbol). Пары

называются правилами подстановки, просто правилами или продукциями (rewriting rule, production) и записываются в виде .

Пример 1.4.2.

Пусть даны множества N = {S}, , . Тогда

является порождающей грамматикой.

Замечание 1.4.3.

Будем обозначать элементы множества

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

Замечание 1.4.4. Для обозначения n правил с одинаковыми левыми частями

часто используют сокращенную запись .

Определение 1.4.5. Пусть дана грамматика G. Пишем , если ,

и

для некоторых слов

в алфавите . Если , то говорят, что слово

непосредственно выводимо

из слова .

Замечание 1.4.6.

Когда из контекста ясно, о какой грамматике идет речь, вместо

можно писать просто .

Пример 1.4.7. Пусть

Тогда .

Определение 1.4.8. Если , где , то пишем

и говорим, что слово

выводимо

из слова . Другими словами, бинарное отношение

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

При этом последовательность слов

называется выводом (derivation) слова

из слова

в грамматике G. Число n называется длиной

(количеством шагов) этого вывода.

Замечание 1.4.9.

В частности, для всякого слова

имеет место

( так как возможен вывод длины 0).

Пример 1.4.10. Пусть . Тогда . Длина этого вывода - 3.

Определение 1.4.11. Язык, порождаемый грамматикой G, - это множество . Будем также говорить, что грамматика G порождает (generates) язык L(G).

Замечание 1.4.12. Существенно, что в определение порождающей грамматики включены два алфавита - и N. Это позволило нам в определении 1.4.11 "отсеять" часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту .

Пример 1.4.13. Если , то .

Определение 1.4.14. Две грамматики эквивалентны, если они порождают один и тот же язык.

Пример 1.4.15.

Грамматика

и грамматика

эквивалентны.

Упражнение 1.4.16. Описать язык, порождаемый грамматикой

Упражнение 1.4.17. Описать язык, порождаемый грамматикой

Упражнение 1.4.18. Описать язык, порождаемый грамматикой

Упражнение 1.4.19. Описать язык, порождаемый грамматикой

Упражнение 1.4.20. Описать язык, порождаемый грамматикой

Упражнение 1.4.21. Описать язык, порождаемый грамматикой

Упражнение 1.4.22. Эквивалентны ли грамматика

и грамматика

Упражнение 1.4.23. Эквивалентны ли грамматика

и грамматика

Слова, языки и грамматики

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

Используемые в приложениях формальные языки, как правило, являются бесконечными. Очевидно, нужен способ конечного описания формального языка. В данном курсе изучаются несколько классических средств: порождающие грамматики, автоматы, регулярные выражения. Определению понятий грамматики и порождаемого ею языка посвящен раздел 1.4. В конце первой лекции вводятся классы грамматик, образующие иерархию Хомского: грамматики типа 0 (все порождающие грамматики), грамматики типа 1 (контекстные грамматики), грамматики типа 2 (контекстно-свободные, или бесконтекстные, грамматики), грамматики типа 3 (праволинейные грамматики), а также менее важный класс линейных грамматик, промежуточный между классами грамматик типа 2 и 3.

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

Детерминированные конечные автоматы

Определение 2.6.1.

Конечный автомат

называется детерминированным (deterministic), если

множество I содержит ровно один элемент;для каждого перехода

выполняется равенство |x| = 1;для любого символа

и для любого состояния

существует не более одного состояния

со свойством .

Пример 2.6.2.

Конечный автомат из примера 2.1.14 является детерминированным.

Определение 2.6.3.

Детерминированный конечный автомат

называется полным (complete), если для каждого состояния

и для каждого символа

найдется такое состояние , что .

Пример 2.6.4. Конечный автомат из примера 2.1.14 эквивалентен полному детерминированному конечному автомату , где Q = {1,2,3}, , I = {1}, F = {1,2},

Замечание 2.6.5.

Некоторые авторы используют в определении полного детерминированного конечного автомата вместо отношения

функцию . От функции

можно перейти к отношению , положив

Упражнение 2.6.6. Является ли детерминированным следующий конечный автомат?

Упражнение 2.6.7. Является ли полным следующий детерминированный конечный автомат с алфавитом ?

Характеризация праволинейных языков

Теорема 2.4.1.

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

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

и I = {q0}. Положим N = Q, S = q0

и

Пример 2.4.2.

Язык, распознаваемый конечным автоматом из примера 2.1.2, порождается грамматикой

Теорема 2.4.3.

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

Доказательство. Без ограничения общности можно предположить, что исходный язык задан праволинейной грамматикой, не содержащей правил вида , где . Положим Q = N, I = {S},

и .

Пример 2.4.4.

Пусть . Рассмотрим грамматику

Она эквивалентна грамматике

Язык, порождаемый этими грамматиками, распознается конечным автоматом , где Q = {S,T,E}, I = {S}, F = {E} и

Упражнение 2.4.5. Найти праволинейную грамматику, порождающую язык

Упражнение 2.4.6. Существует ли такая праволинейная грамматика G, что язык L(G)R

не порождается ни одной праволинейной грамматикой, имеющей столько же правил, сколько грамматика G?

Упражнение 2.4.7. Существует ли такая праволинейная грамматика G, что язык L(G)R

не порождается ни одной праволинейной грамматикой с количеством правил n + 1, где n - количество правил в грамматике G?

Упражнение 2.4.8. Существует ли такая праволинейная грамматика G с тремя вспомогательными символами, что язык L(G)R

не порождается ни одной праволинейной грамматикой с тремя вспомогательными символами?

Конечные автоматы

Два наиболее распространенных способа конечного задания формального языка - это грамматики и автоматы. Автоматами в данном контексте называют математические модели некоторых вычислительных устройств. В этой лекции рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам. Более сильные вычислительные модели будут определены позже, в лекциях 10, 14 и 15. Термин "автоматный язык" закреплен за языками, распознаваемыми именно конечными автоматами, а не какими-либо более широкими семействами автоматов (например, автоматами с магазинной памятью или линейно ограниченными автоматами).

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

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

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

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

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

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

Конечные автоматы с однобуквенными переходами

Лемма 2.3.1.

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

Пример 2.3.2.

Рассмотрим язык, заданный конечным автоматом , где Q = {1,2}, , I = {1,2}, F = {1,2},

Тот же язык распознается конечным автоматом , где Q' = {0,1,2,3,4,5}, I' = {0}, F' = {5},

Здесь первые два перехода заменяют старый переход

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

и . Последние два перехода в

обеспечивают единственность заключительного состояния.

Лемма 2.3.3.

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

Доказательство. Согласно лемме 2.3.1 можно предположить, что исходный язык задан конечным автоматом , не содержащим переходов с метками длины больше единицы, причем |I| = 1. Построим искомый конечный автомат , положив Q' = Q, I' = I,

Пример 2.3.4.

Пусть , где Q = {1,2,3}, , I = {1}, F = {3},

Легко убедиться, что . Тот же язык распознается конечным автоматом , где F' = {2,3} и

Упражнение 2.3.5. Найти конечный автомат с однобуквенными переходами, распознающий язык

Упражнение 2.3.6. Найти конечный автомат с однобуквенными переходами, распознающий язык

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

Конфигурация конечного автомата

Определение 2.2.1.

Конфигурацией или мгновенным описанием (instantaneous description) конечного автомата

называется любая упорядоченная пара , где

и .

Замечание 2.2.2.

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

слово w есть та часть исходного слова, которая пока осталась во входном потоке (это некоторый суффикс исходного слова), а q - текущее состояние "управляющего устройства".

Определение 2.2.3.

Определим на множестве всех конфигураций конечного автомата M бинарное отношение

(такт работы (step)) следующим образом. Если

и , то . Иногда вместо

пишут .

Пример 2.2.4.

Рассмотрим конечный автомат

из примера 2.1.2. Тогда .

Определение 2.2.5.

Бинарное отношение

определяется как рефлексивное, транзитивное замыкание отношения .

Пример 2.2.6.

Для конечного автомата из примера 2.1.2 выполняется

и .

Лемма 2.2.7.

Пусть дан конечный автомат . Слово

принадлежит языку L(M) тогда и только тогда, когда для некоторых и

верно .

Лемма 2.2.8.

Если

и , то .

Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации

в конфигурацию .

Упражнение 2.2.9.

Рассмотрим конечный автомат.

Перечислить все конфигурации , удовлетворяющие условию .

Упражнение 2.2.10.

Существуют ли конечный автомат M, состояния q1, q2

и слова x, y, z, такие что

и ?

Упражнение 2.2.11. Как связаны |Q|, , , |w| и число достижимых из

(в смысле ) конфигураций?

Недетерминированные конечные автоматы

Определение 2.1.1.

Конечный автомат (finite automaton, finite-state machine) - это пятерка , где - конечный входной алфавит (или просто алфавит) данного конечного автомата, Q и - конечные множества,

, . Элементы Q называются состояниями (state), элементы I - начальными (initial) состояниями, элементы F - заключительными или допускающими (final, accepting) состояниями. Если , то

называется переходом (transition) из p в q, а слово x - меткой (label) этого перехода.

Пример 2.1.2.

Пусть Q = {1,2}, , I = {1}, F = {2},

Тогда - конечный автомат.

Замечание 2.1.3.

Конечные автоматы можно изображать в виде диаграмм состояний (state diagram) (иногда их называют диаграммами переходов (transition diagram)). На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Стрелка из p в q, помеченная словом x, показывает, что

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

Пример 2.1.4.

На диаграмме изображен конечный автомат из примера 2.1.2.

Замечание 2.1.5.

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

Пример 2.1.6.

На диаграмме снова изображен конечный автомат из примера 2.1.2.

Определение 2.1.7.

Путь (path) конечного автомата - это кортеж , где

и

для каждого i. При этом q0 - начало пути qn - конец пути n - длина пути w1...wn - метка пути.

Замечание 2.1.8.

Для любого состояния

существует путь . Его метка - , начало и конец совпадают.

Определение 2.1.9.

Путь называется успешным если его начало принадлежит I, а конец принадлежит F.

Пример 2.1.10.

Рассмотрим конечный автомат из примера 2.1.2. Путь

является успешным. Его метка - baaab. Длина этого пути - 4.

Определение 2.1.11.

Слово w допускается (is accepted, is recognized) конечным автоматом M, если оно является меткой некоторого успешного пути.

Определение 2.1.12.

Язык, распознаваемый конечным автоматом M, - это язык L(M), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат M распознает (recognizes, accepts) язык L(M).

Замечание 2.1.13.

Если , то язык, распознаваемый конечным автоматом , содержит .

Пример 2.1.14.

Пусть , где Q = {1,2}, , I = {1}, F = {1,2},

Тогда

Определение 2.1.15.

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

Определение 2.1.16.

Язык L называется автоматным (finite-state language), если существует конечный автомат, распознающий этот язык.

Замечание 2.1.17.

Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).

Пример 2.1.18.

Рассмотрим однобуквенный алфавит . При любых фиксированных

и

язык

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

Замечание 2.1.19.

Каждый конечный язык является автоматным.

Определение 2.1.20.

Состояние q достижимо (reachable) из состояния p, если существует путь, началом которого является p, а концом - q.

Лемма 2.1.21.

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

Пример 2.1.22.

Рассмотрим конечный автомат , где Q = {1,2,3,4}, , I = {1,2,4}, F = {1,3,4},

Удалим те состояния (и содержащие их переходы), которые не удовлетворяют требованиям леммы 2.1.21. Получается эквивалентный конечный автомат , где Q' = {1,4}, I' = {1,4}, F' = {1,4},

Замечание 2.1.23

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

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

Упражнение 2.1.24. Найти конечный автомат, распознающий язык

Упражнение 2.1.25. Найти конечный автомат, распознающий язык

Упражнение 2.1.26. Найти конечный автомат, распознающий язык

Упражнение 2.1.27. Найти конечный автомат, распознающий язык

Упражнение 2.1.28. Найти конечный автомат, распознающий язык

Упражнение 2.1.28. Найти конечный автомат, распознающий язык , где ,

и

для любого

Нормальная форма праволинейных грамматик

Определение 2.5.1.

Праволинейная грамматика в нормальной форме (автоматная грамматика, регулярная грамматика, finite-state grammar) - это праволинейная грамматика, в которой каждое правило имеет вид , , или , где , , .

Теорема 2.5.2.

Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.

Доказательство. Применим последовательно теорему 2.4.3, лемму 2.3.3 и воспользуемся конструкцией из доказательства теоремы 2.4.1.

Теорема 2.5.3.

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

Упражнение 2.5.4. Найти праволинейную грамматику, эквивалентную грамматике

Упражнение 2.5.5. Найти праволинейную грамматику в нормальной форме без -правил, порождающую язык

Упражнение 2.5.6. Найти праволинейную грамматику в нормальной форме без -правил, порождающую язык

Преобразование конечного автомата к детерминированному виду

Теорема 2.7.1

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

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

и

обозначим

Обозначим через

множество всех подмножеств множества Q. Построим искомый полный детерминированный конечный автомат , положив ,

и .

Пример 2.7.2.

Пусть . Рассмотрим конечный автомат , где

Если применить конструкцию из доказательства теоремы 2.7.1. и затем удалить состояния, не достижимые из начального состояния, то получится полный детерминированный конечный автомат

где

Упражнение 2.7.3. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображенному на диаграмме.

Упражнение 2.7.4. Найти детерминированный конечный автомат для языка, порождаемого грамматикой

Упражнение 2.7.5. Найти детерминированный конечный автомат, распознающий язык

Лемма о разрастании для автоматных языков

Лемма 3.3.1 (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос).

Пусть L автоматный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова

длины не меньше p можно подобрать слова , для которых верно xyz = w, ,

и

для всех .

Доказательство. Пусть язык L распознается конечным автоматом , содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути

и . Согласно принципу Дирихле найдутся такие индексы j и k, что

и qj = qk

(ведь множество индексов

содержит p+1 натуральных чисел, а значения qi

берутся из множества, содержащего всего p элементов). Выберем слова x, y и z так, что |x| = j, |y| = k - j и xyz = w.

Пример 3.3.2.

Пусть . Рассмотрим автоматный язык

Положим p = 3. Тогда для любого слова

длины не меньше p найдутся слова , соответствующие утверждению леммы 3.3.1. Действительно, если w = abu для некоторого слова u, то положим , y = ab, z = u; иначе w = aabu и можно положить x = a, y = ab, z = u.

Упражнение 3.3.3. Является ли автоматным язык

Упражнение 3.3.4. Является ли автоматным язык {an | существует такое число , что p простое и p + 2 простое}?

Упражнение 3.3.5. Является ли автоматным язык

Упражнение 3.3.6. Является ли автоматным язык

Упражнение 3.3.7. Является ли автоматным язык

Упражнение 3.3.8. Является ли автоматным язык

Упражнение 3.3.9. Является ли автоматным язык

Упражнение 3.3.10. Является ли автоматным язык, порождаемый грамматикой

Основные свойства автоматных языков

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

В первых двух разделах этой лекции доказываются свойства замкнутости класса всех автоматных языков (относительно итерации, конкатенации, объединения, дополнения, пересечения и т. д.). Эти свойства можно использовать как достаточные условия автоматности. Например, если нужно выяснить, является ли язык L автоматным, и удается представить L в виде , где языки L1 и L2

автоматные, то и язык L обязательно является автоматным.

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

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

Теорема 3.2.1.

Класс автоматных языков замкнут относительно дополнения и пересечения.

Доказательство. Если язык L распознается полным детерминированным конечным автоматом , то язык

распознается конечным автоматом .

Пересечение выражается через объединение и дополнение (закон де Моргана).

Замечание 3.2.2.

Автоматность пересечения двух автоматных языков можно легко доказать и без привлечения теоремы 2.7.1. Для этого достаточно построить по двум конечным автоматам с однобуквенными переходами

новый конечный автомат

где

Упражнение 3.2.3. Обозначим через L язык, порождаемый грамматикой

Найти праволинейную грамматику, порождающую язык .

Упражнение 3.2.4. Обозначим через L язык, порождаемый грамматикой

Найти праволинейную грамматику, порождающую язык .

Упражнение 3.2.5.

Обозначим через L язык, порождаемый грамматикой

Найти праволинейную грамматику, порождающую язык .

Упражнение 3.2.6.

Существуют ли такие детерминированные конечные автоматы M1 и M2, что язык

не порождается ни одним детерминированным конечным автоматом с количеством состояний n1n2+n1+n2, где n1 - количество состояний автомата M1

и n2 - количество состояний автомата M2?

Примеры неавтономных языков

Пример 3.4.1.

Рассмотрим язык

над алфавитом . Утверждение леммы 3.3.1 не выполняется ни для какого натурального числа p. Действительно, если w = abpap, то x = abk, y = bm, z = bp-k-map

для некоторых

и

или , y = abl, z = bp-lap

для некоторого . В обоих случаях . Таким образом, язык L не является автоматным.

Упражнение 3.4.2.

Пусть . При каких словах

и

язык

является автоматным?

Замечание 3.4.3.

Условие, сформулированное в лемме 3.3.1, является необходимым для автоматности, но не достаточным.

Пример 3.4.4.

Пусть . Рассмотрим язык L = {akbman | k=0 или m=n. Положим p = 1. Тогда для любого слова

длины не меньше p найдутся слова , соответствующие утверждению леммы 3.3.1. Тем не менее язык L не является автоматным, так как

Лемма 3.4.5*.

Пусть L - автоматный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова

можно подобрать слова , для которых верно xyz = w,

и

для всех . Здесь [m] означает целую часть числа m.

Доказательство. Пусть L распознается конечным автоматом , содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути . Обозначим l = [|w|/p]. Если l = 0, то положим

и . Пусть . Согласно принципу Дирихле найдутся такие натуральные числа j и k, что

и qjl = qkl. Выберем слова x, y и z так, что |x| = jl, |y| = kl - jl и xyz = w.

Упражнение 3.4.6. Является ли автоматным язык

Упражнение 3.4.7. Является ли автоматным язык

Упражнение 3.4.8. Является ли автоматным язык

множества

и

равномощны?

Упражнение 3.4.9. Является ли автоматным язык

множества

и

равномощны?

Упражнение 3.4.10. Является ли автоматным язык

Упражнение 3.4.11. Является ли автоматным язык, порождаемый грамматикой

Свойства замкнутости класса автоматных языков

Теорема 3.1.1. Класс автоматных языков замкнут относительно итерации, конкатенации и объединения.

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

Пример 3.1.2. Пусть . Рассмотрим конечный автомат

где

Тогда язык L(M1)*

распознается конечным автоматом

Пример 3.1.3.

Пусть . Рассмотрим конечный автомат M1

из примера 3.1.2 и конечный автомат

где

Тогда язык

распознается конечным автоматом

а язык

распознается конечным автоматом

Упражнение 3.1.4.

Существует ли такой автоматный язык L, что язык LR

не является автоматным?

Упражнение 3.1.5.

Существует ли такой автоматный язык , что язык Pref(L) не является автоматным?

Упражнение 3.1.6.

Существует ли такой автоматный язык , что язык Suf(L) не является автоматным?

Упражнение 3.1.7.

Существует ли такой автоматный язык , что язык Subw(L) не является автоматным?

Упражнение 3.1.8.

Существует ли такой автоматный язык , что язык Subseq(L) не является автоматным?

Упражнение 3.1.9.

Существует ли такой автоматный язык L, что язык

не является автоматным?

Упражнение 3.1.10. Существует ли такой автоматный язык L, что язык

не является автоматным?

Упражнение 3.1.11. Найти праволинейную грамматику, порождающую язык

Упражнение 3.1.12. Найти праволинейную грамматику, порождающую язык L*, если язык L порождается грамматикой

Длины слов в автоматных языках

Определение 4.3.1.

Пусть ,

и . Множество

называется заключительно периодическим (ultimately periodic) с периодом m, если выполнено условие

Лемма 4.3.2.

Пусть . Тогда равносильны следующие утверждения:

множество

является заключительно периодическим;найдутся такие положительное целое число m и конечные множества

и , что множество

является объединением конечного семейства арифметических прогрессий.

Теорема 4.3.3.

Язык L над однобуквенным алфавитом {a} является автоматным тогда и только тогда, когда множество

является заключительно периодическим.

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

Теорема 4.3.4.

Если язык L является автоматным, то множество

является заключительно периодическим.

Доказательство. Рассмотрим конечный автомат, распознающий язык L. Заменим все символы в метках переходов на символ a. Осталось применить теорему 4.3.3 к полученному автоматному языку над однобуквенным алфавитом {a}.

Упражнение 4.3.5.

Существует ли такой автоматный язык L над алфавитом {a}, что язык

не является автоматным?

Упражнение 4.3.6.

Существует ли такой автоматный язык L над алфавитом {a}, что язык

не является автоматным?

Упражнение 4.3.7.

Существует ли такой автоматный язык L1

над алфавитом , что язык

не является автоматным?

Упражнение 4.3.8.

Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?

Упражнение 4.3.9.

Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?

Дополнительные свойства автоматных языков

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

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

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

Гомоморфизмы и автоматные языки

Теорема 4.1.1.

Для любого гомоморфизма

и автоматного языка

язык h(L) является автоматным.

Доказательство. Пусть исходный язык L задан конечным автоматом . Положим

Тогда язык h(L) распознается конечным автоматом .

Теорема 4.1.2. Для любого гомоморфизма

и автоматного языка

язык h-1(L) является автоматным.

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

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

Язык h-1(L) распознается конечным автоматом .

Упражнение 4.1.3. Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?}

Упражнение 4.1.4. Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?}

Упражнение 4.1.5. Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?

Локальные языки

Определение 4.2.1. Гомоморфизм

называется побуквенным (length-preserving), если |h(a)| = 1 для каждого .

Замечание 4.2.2. Гомоморфизм

является побуквенным тогда и только тогда, когда |h(w)| = |w| для каждого слова .

Определение 4.2.3.

Язык

называется локальным, если существуют такие языки , , , что

языки L1 и L2

содержат только однобуквенные слова;язык L3

содержит только двухбуквенные слова;.

Лемма 4.2.4.

Каждый локальный язык является автоматным.

Очевидно, что языки L1, L2 и L3

в определении 4.2.3 являются конечными. Остается применить замечание 2.1.19 и теоремы 3.1.1 и 3.2.1 (напомним, что разность языков выражается через пересечение и дополнение).

Теорема 4.2.5.

Пусть L - язык над алфавитом

и L не содержит пустого слова. Язык L является автоматным тогда и только тогда, когда существуют такие алфавит , локальный язык

и побуквенный гомоморфизм , что L = h(L0).

Доказательство. Достаточность следует из леммы 4.2.4 и теоремы 4.1.1.

Для доказательства необходимости рассмотрим конечный автомат

с однобуквенными переходами, задающий язык L. В качестве алфавита

возьмем множество . Положим

и

для каждого .

Пример 4.2.6.

Пусть . Рассмотрим конечный автомат M2

из примера 3.1.3 и обозначим L = L(M2). Применим конструкцию из доказательства теоремы 4.2.5 к языку L. Для удобства заменим

на d,

на e и

на f. Получим алфавит

и локальный язык

Можно доказать, что

Побуквенный гомоморфизм h задается равенствами ,

и . Легко проверить, что действительно L = h(L0).

Упражнение 4.2.7. Пусть . Существует ли такой побуквенный гомоморфизм , что h(abc) = bac и h(da) = da?}

Упражнение 4.2.8. Является ли локальным язык

над алфавитом ?

Упражнение 4.2.9. Является ли локальным язык

над алфавитом ?

Упражнение 4.2.10. Является ли локальным язык

над алфавитом ?

Определение регулярного выражения

Определение 5.1.1.

Регулярное выражение над алфавитом

определяется рекурсивно следующим образом: 0 является регулярным выражением; 1 является регулярным выражением; если , то a является регулярным выражением; если e и f являются регулярными выражениями, то ,

и

тоже являются регулярными выражениями.

Для экономии скобок будем считать, что операция *

связывает сильнее (то есть имеет более высокий приоритет), чем умножение, а умножение связывает сильнее, чем сложение. Вместо

часто пишут просто .

Пример 5.1.2.

Пусть . Тогда

является регулярным выражением над алфавитом .

Определение 5.1.3.

Каждое регулярное выражение e над алфавитом

задает (denotes, represents) некоторый язык над алфавитом

(обозначение ), определяемое рекурсивно следующим образом:

Заметим, что в правой части последнего выражения символом * обозначена итерация языка (см. определение 1.2.7).

Вместо

часто пишут просто e.

Пример 5.1.4.

Пусть . Согласно определению

Определение 5.1.5.

Язык L называется регулярным если он задается некоторым регулярным выражением.

Определение 5.1.6.

Пусть e - регулярное выражение. Тогда .

Упражнение 5.1.7. Упростить регулярное выражение ((a+bc)*)*

Упражнение 5.1.8. Найти праволинейную грамматику для языка ab*a

Упражнение 5.1.9. Найти праволинейную грамматику для языка ((a+b)a)*.

Упражнение 5.1.10. Найти полный детерминированный конечный автомат для языка (a+b)*(aab+abaa+abb)(a+b)*.

Упражнение 5.1.11. Найти полный детерминированный конечный автомат для языка (a+b)*(a(b+1)abb+baa)(a+b)*.

Упражнение 5.1.12. Найти полный детерминированный конечный автомат для языка (b+c)((ab)*c+(ba)*)*.

Упражнение 5.1.13. Найти полный детерминированный конечный автомат для языка (abab)+(aba)*.

Упражнение 5.1.14. Найти полный детерминированный конечный автомат для языка (c+(a+b+c)(b+a(b+c)*a))*(a+b+c).

Регулярные выражения

До сих пор мы рассматривали два способа конечного описания формального языка: грамматики и автоматы. Третий способ, часто наиболее удобный и компактный, - регулярные выражения. В них используются символы, обозначающие итерацию, конкатенацию и объединение языков. Например, для обозначения итерации традиционно используется символ "звездочка".

Регулярные выражения находят практическое применение во многих компьютерных приложениях, таких как текстовые редакторы и интерпретаторы командной строки. В автоматических генераторах лексических анализаторов принято использовать именно регулярные выражения в качестве формализма, с помощью которого задаются классы однотипных лексем (например, класс идентификаторов, класс десятичных констант). В языках программирования Perl, Python и др. имеется встроенная поддержка регулярных выражений.

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

Свойства регулярных выражений

Лемма 5.2.1.

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

e+f = f+e;e+0 = e;;;p;;;;;.

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

Лемма 5.2.2.

Для любых регулярных выражений e и f выполняются следующие тождества:

e+e = e;(1+e+ee+...+en-1)(en)* = e*

для любого ;(e*f)*e* = (e+f)*;1+e(fe)*f = (ef)*.

Лемма 5.2.3.

Для любых регулярных выражений e, f и g, если e = ef+g и , то e = gf*.

Упражнение 5.2.4. Упростить регулярное выражение 0*.

Упражнение 5.2.5. Упростить регулярное выражение (a+b+ab)*.

Упражнение 5.2.6. Упростить регулярное выражение (a*b)*+(b*a)*.

Упражнение 5.2.7. Упростить регулярное выражение ((b+a)*b+1)b*.

Упражнение 5.2.8. Упростить регулярное выражение ((ab+aab)*a*)*.

Упражнение 5.2.9. Упростить регулярное выражение (abbaab+abbaaba)*.

Упражнение 5.2.10. Упростить регулярное выражение (a+b)*(a(a+b)*a+b(a+b)*b).

Упражнение 5.2.11. Упростить регулярное выражение (eb*(1+c(d+ab*c)*a)b*f)*eb*c(d+ab*c)*.

Теорема Клини

Определение 5.3.1.

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

Замечание 5.3.2.

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

Замечание 5.3.3.

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

Пример 5.3.4.

Пусть . Обобщенный конечный автомат , где Q = {1,2,3}, I = {1,2}, F = {3},

допускает все слова в алфавите , кроме слов, содержащих подслово aa.

Теорема 5.3.5 (теорема Клини).

Язык L является регулярным тогда и только тогда, когда он является автоматным.

Доказательство. Пусть e - регулярное выражение. Индукцией по построению e легко показать, что задаваемый им язык является автоматным (см. теорему 3.1.1).

Обратно, пусть язык L распознается некоторым (недетерминированным) конечным автоматом с одним начальным состоянием и одним заключительным состоянием. Существует эквивалентный ему обобщенный конечный автомат , где . Если есть несколько переходов с общим началом и общим концом (такие переходы называются параллельными), заменим их на один переход, используя операцию +.

Устраним по очереди все состояния, кроме q1

и q2. При устранении состояния q нужно для каждого перехода вида , где , и для каждого перехода вида , где , добавить переход , где регулярное выражение g - метка перехода из q в q (если нет перехода из q в q, то надо добавить переход ), и снова всюду заменить параллельные переходы на один переход, используя операцию +.

После устранения всех состояний, кроме q1 и q2, получится обобщенный конечный автомат , где

Очевидно, что .

Пример 5.3.6.

Рассмотрим язык, распознаваемый конечным автоматом

где

и

Тот же язык порождается обобщенным конечным автоматом

где

После устранения состояния q3

получается обобщенный конечный автомат

где

Можно упростить регулярные выражения и получить

После устранения состояния q4

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

где

Следовательно, язык L(M) задается регулярным выражением

Упростив это регулярное выражение, получим

Упражнение 5.3.7. Найти регулярное выражение для языка, порождаемого грамматикой

Упражнение 5.3.8. Найти регулярное выражение для языка

Упражнение 5.3.9. Найти регулярное выражение для языка , где L1 = (aaab+c+d)*, L2 = (a*ba*ba*bc+d)*, L3 = ((a+b)*c(a+b)*cd)*

Упражнение 5.3.10 Найти регулярное выражение для дополнения языка (a+b)*bbb(a+b)* в алфавите {a,b}.

Упражнение 5.3.11 Найти регулярное выражение для дополнения языка (ab+ba)*(1+a+b) в алфавите {a,b}.

Упражнение 5.3.12 Найти регулярное выражение для дополнения языка (a+b)*(aab+abaa+abb)(a+b)* в алфавите {a,b}.

Упражнение 5.3.13 Найти регулярное выражение для дополнения языка (aa(ab)*bb(ab)*)* в алфавите {a,b}.

Звездная высота

Определение 5.4.1.

Звездная высота (star-height) регулярного выражения (обозначение sh(e)) определяется рекурсивно следующим образом:

Пример 5.4.2. Пусть . Тогда

sh((a*+b*+ab)*+(ab*c)* = 2.

Определение 5.4.3. Звездной высотой регулярного языка L (обозначение sh(L)) называется минимум звездных высот регулярных выражений, задающих этот язык.

Замечание 5.4.4.

Регулярный язык L является конечным тогда и только тогда, когда sh(L) = 0.

Теорема 5.4.5.

Пусть . Тогда для любого

существует такой регулярный язык , что sh(L) = n.

Доказательство можно найти в книге Саломаа А. Жемчужины теории формальных языков. - М.: Мир, 1986 с.41-46.

Пример 5.4.6.

Пусть

и

Тогда sh(L) = 2. Действительно, язык L задается регулярным выражением (ab+ba+(aa+bb)(ab+ba)*(aa+bb))*

и не задается никаким регулярным выражением меньшей звездной высоты.

Замечание 5.4.7. Неизвестно, верен ли аналог теоремы 5.4.5 для обобщенных регулярных выражений, в которых, помимо итерации, конкатенации и объединения, разрешена операция дополнения.

Упражнение 5.4.8.Уменьшить звездную высоту регулярного выражения (a*+b*+ab)*.

Упражнение 5.4.9.Уменьшить звездную высоту регулярного выражения (c(a*b)*)*.

Упражнение 5.4.10.Уменьшить звездную высоту регулярного выражения (a(ab)*b)*.

Упражнение 5.4.11. Существует ли такой регулярный язык , что sh(L) = 2?

Классы эквивалентности слов

Лемма 6.4.1.

Пусть

и . Тогда

Определение 6.4.2.

Пусть

и . Обозначим через

язык . Обозначим через

язык .

Пример 6.4.3.

Пусть . Множества вида

образуют разбиение множества

на классы эквивалентности. Множества вида

образуют разбиение множества

на классы эквивалентности.

Пример 6.4.4.

Пусть

и . Тогда

Лемма 6.4.5.

Если язык

является автоматным, то для каждого слова

языки

и

являются автоматными.

Доказательство. Пусть язык L распознается конечным автоматом , не содержащим переходов с метками длины больше единицы. Будем использовать обозначение TrM

из доказательства теоремы 6.3.11. При любой фиксированной паре

язык

является автоматным (он распознается конечным автоматом ). Для каждого слова

язык

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

Каждый из языков [x]L

и

является объединением конечного семейства автоматных языков:

Замечание 6.4.6.

Из теоремы 6.1.8 вытекает, что если язык L автоматный, то существует лишь конечное число различных множеств . Аналогичное утверждение верно для множеств

(см. теорему 6.3.11).

Пример 6.4.7.

Рассмотрим язык

над алфавитом . Тогда

Упражнение 6.4.8.

Существуют ли такие языки

и , что язык L1

является автоматным, но язык

не является автоматным?

Упражнение 6.4.9.

Существуют ли такие языки

и , что язык L1

является автоматным, но язык

не является автоматным?

Упражнение 6.4.10.

Существует ли такой автоматный язык , что язык

не является автоматным?

Теорема 6.4.11.

Язык

является автоматным тогда и только тогда, когда существует такое отношение эквивалентности , что R разбивает

на конечное множество классов эквивалентности, L является объединением некоторых из этих классов эквивалентности и для любых , ,

из xRy следует xzRyz.

Замечание 6.4.12.

Теоремы 6.1.8 и 6.4.11 образуют теорему Майхилла-Нерода.

Минимизация детерминированных конечных автоматов

Определение 6.2.1.

Говорят, что слово w различает состояния p и q полного детерминированного конечного автомата , если одно из состояний ,

заключительное, а другое не является заключительным.

Определение 6.2.2.

Состояния p и q полного детерминированного конечного автомата

называются различимыми (distinguishable), если существует слово w, которое их различает.

Замечание 6.2.3.

Пусть полный детерминированный конечный автомат

задает язык L. Рассмотрим произвольные слова

и . Состояния

и

различимы тогда и только тогда, когда .

Теорема 6.2.4.

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

Доказательство. Без ограничения общности можно предположить, что дан полный детерминированный конечный автомат , все состояния которого достижимы из начального состояния (для обеспечения полноты достаточно добавить одно состояние). Для каждого натурального числа i определим на множестве Q отношение эквивалентности :

Легко видеть, что

тогда и только тогда, когда никакое слово длины не больше i не различает p и q. Обозначим n =|Q|. Легко проверить, что для любого

отношение

совпадает с отношением . Используя классы эквивалентности отношения

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

Пример 6.2.5.

Рассмотрим полный детерминированный конечный автомат , где

Он эквивалентен минимальному детерминированному конечному автомату , где

Замечание 6.2.6.

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

Упражнение 6.2.7. Найти минимальный полный детерминированный конечный автомат для языка, порождаемого грамматикой

Упражнение 6.2.8. Найти минимальный полный детерминированный конечный автомат для языка

(1+(a+b)*b)b(a+b)*.

Упражнение 6.2.9. Найти минимальный полный детерминированный конечный автомат для языка

(a+b)*(aaba+(aabb+bbaa)abbb)(a+b)*.

Упражнение 6.2.10. Равны ли регулярные выражения

(aa+b+ab)* и ((a+b)*b+1)(aa)*?

Упражнение 6.2.11. Равны ли регулярные выражения

(a+b)*aa(a+b)*bb(a+b)* и (ab+b)*aa(a+b)*bb(a+ba)*?

Упражнение 6.2.12. Равны ли регулярные выражения

((ba+bb)(aa+ab)*)*a и b(aa+ab+ba+bb)*(aa+ba)?

Упражнение 6.2.13. Равны ли регулярные выражения

(ca+cb+cc+(a+b+(a+c))+c)(a+b+c)*

и

c(a+b+bc)++(a+b+c)*(ac+cc)(a+b+bc)*?

Множества двусторонних контекстов

Определение 6.3.1.

Пусть

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

Пример 6.3.2.

Пусть

и . Тогда

Лемма 6.3.3.

Если , то .

Доказательство. Из определений следует, что

Лемма 6.3.4.

Если , то

и .

Доказательство. Пусть

и . Тогда . Следовательно, . Далее, получаем, что ,

и . Второе равенство доказывается аналогично.

Лемма 6.3.5.

Если

и , то .

Определение 6.3.6.

Пусть . Тогда множество

называется синтаксическим моноидом (syntactic monoid) языка L.

Определение 6.3.7*.

Полугруппой (semigroup)

называется непустое множество M с ассоциативной бинарной операцией .

Определение 6.3.8*.

Пусть - полугруппа. Элемент

называется единицей (unit), если

для каждого .

Определение 6.3.9*.

Моноид - это полугруппа

с единицей .

Теорема 6.3.10*.

Определим бинарную операцию на Synt(L) следующим образом:

Тогда

является моноидом.

Теорема 6.3.11.

Синтаксический моноид Synt(L) конечен тогда и только тогда, когда язык L является автоматным.

Доказательство Пусть множество Synt(L) конечно. Согласно лемме 6.3.3 множество

тоже конечно. В силу леммы 6.1.6 язык L является автоматным.

Обратно, пусть язык L распознается некоторым конечным автоматом , не содержащим переходов с метками длины больше единицы. Поставим в соответствие каждому слову y множество , определенное следующим образом:

Легко проверить, что если , то . Следовательно, , где n = |Q|.

Пример 6.3.12.

Рассмотрим конечный автомат M из примера 2.1.14. Тогда

;если , то ;если , то ;если , то ;если , то ;;.

Лемма 6.3.13.

Пусть ,

и для каждого слова

длины n найдется такое слово , что

и . Тогда

Доказательство. Индукцией по

можно доказать, что для каждого слова

длины k найдется такое слово , что

и . В шаге индукции используется лемма 6.3.5.

Упражнение 6.3.14. Сколько элементов в синтаксическом моноиде языка a+b над алфавитом {a,b}?

Упражнение 6.3.15. Сколько элементов в синтаксическом моноиде языка b+a+ над алфавитом {a,b}?

Упражнение 6.3.16. Сколько элементов в синтаксическом моноиде языка (aa+b)* над алфавитом {a,b}?

Упражнение 6.3.17. Сколько элементов в синтаксическом моноиде языка (ab)*(ba)*+a* над алфавитом {a,b}?

Упражнение 6.3.18. Сколько элементов в синтаксическом моноиде языка a(b+c)*a(a+b+c)*+b(a+c)*b(a+b+c)*+c(a+b)*c(a+b+c)* над алфавитом {a,b,c}?

Множества правых контекстов

Определение 6.1.1.

Пусть

и . Тогда множество правых контекстов слова y относительно языка L определяется следующим образом:

Пример 6.1.2.

Пусть

и . Тогда

если , то ;если , то ;если , то .

Определение 6.1.3.

Для любого состояния p полного детерминированного конечного автомата

и любого слова w обозначим через

такое состояние q, что существует путь из p в q с меткой w (в силу полноты и детерминированности такое состояние существует и единственно).

Лемма 6.1.4.

Если язык L распознается полным детерминированным конечным автоматом , то

Доказательство. Пусть I = {s}. Введем обозначение

Определим функцию , положив f(A) равным , где y - некоторое слово, для которого выполнено условие

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

Заметим, что для любых слов u и v, если , то . Следовательно, функция f является инъективной. Но тогда .

Пример 6.1.5.

Рассмотрим язык L, порождаемый полным детерминированным конечным автоматом

из примера 2.6.4. Тогда

Лемма 6.1.6.

Если

и множество

конечно, то язык L является автоматным.

Доказательство. Язык L распознается полным детерминированным конечным автоматом , где

Пример 6.1.7.

Пусть . Рассмотрим автоматный язык L = a+b*. Обозначим

Тогда . Язык L распознается полным детерминированным конечным автоматом , где , , ,

Теорема 6.1.8.

Язык

является автоматным тогда и только тогда, когда множество

конечно.

Доказательство. Необходимость доказана в лемме 6.1.4, достаточность - в лемме 6.1.6.

Замечание 6.1.9.

В силу леммы 6.1.4 полный детерминированный конечный автомат, построенный в доказательстве леммы 6.1.6, является минимальным (по количеству состояний) среди всех полных детерминированных конечных автоматов, распознающих заданный язык. Можно доказать, что любой минимальный полный детерминированный конечный автомат, распознающий заданный язык, изоморфен этому автомату.

Упражнение 6.1.10. Пусть

и

Сколько элементов содержит множество ?

Упражнение 6.1.11. Найти минимальный полный детерминированный конечный автомат для языка {ab,abb}*.

Упражнение 6.1.12. Найти минимальный полный детерминированный конечный автомат для языка

Упражнение 6.1.13. Найти минимальный полный детерминированный конечный автомат для языка

Упражнение 6.1.14. Найти минимальный полный детерминированный конечный автомат для языка

Синтаксические моноиды

Основная цель данной лекции - доказать еще один критерий автоматности формального языка. Этот критерий можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости (однако формальные определения будут даны без использования понятия класса эквивалентности). Слова x и y считаются взаимозаменяемыми (относительно языка L), если при замене в любом слове из языка L подслова, совпадающего с x, на y снова получится слово из языка L и наоборот. В разделе 6.3 фактически доказывается, что язык L является автоматным тогда и только тогда, когда соответствующее отношение взаимозаменяемости разбивает множество всех слов рассматриваемого алфавита на конечное число классов эквивалентности.

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

Деревья вывода

Определение 7.1.1.

Выводам в контекстно-свободной грамматике соответствуют так называемые деревья вывода (деревья разбора, derivation tree, parse tree) - некоторые упорядоченные деревья, вершины которых помечены символами алфавита . Корень дерева отвечает начальному символу. Каждому символу слова w1, на которое заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней проводится дуга из корня. Полученные таким образом непосредственные потомки корня упорядочены согласно порядку их меток в слове w1. Для тех из полученных вершин, которые помечены символами из множества N, делается аналогичное построение, и т. д.

Кроной (yield) дерева вывода называется слово, записанное в вершинах, помеченных символами из алфавита .

Пример 7.1.2.

Рассмотрим контекстно-свободную грамматику

Выводу

соответствует следующее дерево вывода.

Крона этого дерева вывода - ababab.

Упражнение 7.1.3. Перечислить все деревья вывода в грамматике

Упражнение 7.1.4. Существует ли праволинейная грамматика без -правил, в которой некоторое слово имеет бесконечно много выводов?

Языки Дика и Лукасевича

Определение 7.4.1.

Языком Дика (Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом {a1,b1,a2,b2,...,an,bn}, порождаемый грамматикой

Замечание 7.4.2.

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

Теорема 7.4.3.

Слово w над алфавитом {a,b} выводится в грамматике

тогда и только тогда, когда

и для всех слов

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

Теорема 7.4.4.

При любом положительном целом n грамматика из определения 7.4.1 является однозначной.

Определение 7.4.5.

Языком Лукасевича (Lukasiewicz language) над n + 1 буквами называется контекстно-свободный язык над алфавитом {a0,a1,...,an}, порождаемый грамматикой

Теорема 7.4.6.

Слово w над алфавитом {a0,a1,...,an} принадлежит языку Лукасевича над n + 1 буквами тогда и только тогда, когда

и для всех слов , кроме x = w, выполняется неравенство

Теорема 7.4.7.

При любом

грамматика из определения 7.4.5 является однозначной.

Упражнение 7.4.8. Принадлежит ли слово aababb языку, порождаемому грамматикой

Упражнение 7.4.9. Принадлежит ли слово cacbcbbacacccaaaacabcaa языку, порождаемому грамматикой

Упражнение 7.4.10. Эквивалентны ли грамматика

и грамматика

Упражнение 7.4.11. Описать язык, порождаемый грамматикой

Упражнение 7.4.12. Описать язык, порождаемый грамматикой

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

Неоднозначность в контекстно-свободных грамматиках

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

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

Из класса всех контекстно-свободных языков можно выделить подкласс тех языков, для которых существует хотя бы одна однозначная грамматика. В разделе 7.3* доказывается, что все праволинейные (то есть автоматные) языки принадлежат этому подклассу.

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

Однозначные контекстно-свободные грамматики

Определение 7.2.1.

Вывод в контекстно-свободной грамматике называется левосторонним (левым, leftmost derivation), если на каждом шаге вывода заменяется самое левое из всех вхождений вспомогательных символов (то есть каждый шаг вывода имеет вид , где ,

и ). Иногда в левосторонних выводах вместо

пишут . Правосторонний (правый) вывод определяется аналогично. В правосторонних выводах вместо

пишут .

Пример 7.2.2.

Вывод

из примера 7.2.1 не является левосторонним.

Лемма 7.2.3.

Для каждого слова, выводимого в контекстно-свободной грамматике, существует левосторонний вывод.

Лемма 7.2.4.

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

Пример 7.2.5.

Рассмотрим дерево вывода из примера 7.1.2. Ему соответствует левосторонний вывод

Определение 7.2.6.

Контекстно-свободная грамматика называется неоднозначной (ambiguous), если существует слово, которое имеет два или более левосторонних вывода (устаревший термин - неопределенная грамматика). В противном случае контекстно-свободная грамматика называется однозначной (unambiguous).

Пример 7.2.7.

Контекстно-свободная грамматика из примера 7.2.1 неоднозначна. Слово ababab имеет два левосторонних вывода:

и

Пример 7.2.8.

Пусть . Контекстно-свободная грамматика

порождает множество всех булевых формул, составленных из переменных p, p#, p##, ..., с помощью скобок и операторов ,

и . Эта грамматика является однозначной.

Определение 7.2.9.

Контекстно\df свободный язык называется существенно неоднозначным (inherently ambiguous), если каждая контекстно-свободная грамматика, порождающая этот язык, является неоднозначной.

Пример 7.2.10.

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

Пример 7.2.11.

Пусть . Контекстно-свободный язык {akbmcn | k = m или m = n} является существенно неоднозначным. Доказательство этого факта можно найти в [АхоУль, с. 234-236].

Упражнение 7.2.12. Однозначна ли контекстно-свободная грамматика

с алфавитом ?

Упражнение 7.2.13. Однозначна ли контекстно-свободная грамматика

с алфавитом ?

Упражнение 7.2.14. Однозначна ли контекстно-свободная грамматика

с алфавитом ?

Упражнение 7.2.15. Однозначна ли контекстно-свободная грамматика

Упражнение 7.2.16.Найти однозначную контекстно-свободную грамматику, эквивалентную грамматике

Упражнение 7.2.17.Найти однозначную контекстно-свободную грамматику, эквивалентную грамматике

Однозначные праволинейные грамматики

Теорема 7.3.1.

Каждый праволинейный язык порождается некоторой однозначной праволинейной грамматикой. Другими словами, ни один праволинейный язык не является существенно неоднозначным.

Доказательство. Согласно теоремам 2.4.3 и 2.7.1 исходный язык распознается некоторым детерминированным конечным автоматом. Применив к нему конструкцию из доказательства теоремы 2.4.1, получим однозначную праволинейную грамматику.

Замечание 7.3.2.

Этот факт можно получить также из более общей теоремы 12.2.6 с учетом теоремы 12.2.1.

Упражнение 7.3.3. Найти однозначную праволинейную грамматику, порождающую язык a*((a+b)(a+b))*b*.

Упражнение 7.3.4. Найти однозначную праволинейную грамматику, эквивалентную грамматике

Упражнение 7.3.5. Найти однозначную праволинейную грамматику, эквивалентную грамматике

Упражнение 7.3.6. Существует ли праволинейная грамматика в нормальной форме с n вспомогательными символами, не эквивалентная ни одной однозначной праволинейной грамматике с количеством вспомогательных символов 2n - 1?

Нормальная форма Грейбах

Определение 8.4.1.

Грамматика в нормальной форме Грейбах (grammar in Greibach normal form) - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих четырех видов: , , , , где , , , .

Пример 8.4.2.

Грамматика

является грамматикой в нормальной форме Грейбах.

Замечание 8.4.3.

Некоторые авторы разрешают в грамматиках в нормальной форме Грейбах использовать также правила вида , где , ,

(в определении 8.4.1 разрешены, только если ).

Теорема 8.4.4.

Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах.

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

или , где , , , .

Введем |N|2

новых вспомогательных символов, соответствующих упорядоченным парам из множества . Новый символ, соответствующий паре , будем обозначать (A\B). Построим грамматику "почти в нормальной форме Грейбах" , положив

и

Если в этой грамматике заменить

на

получим эквивалентную ей грамматику в нормальной форме Грейбах. Осталось лишь доказать, что .

Сначала проверим индукцией по длине слова , что если , то

для любого . Чтобы провести шаг индукции, допустим, что

и

где

и . По предположению индукции имеем

и . Подключая эти выводы к правилу

и используя , получаем искомый вывод .

Докажем теперь, что для любого

равносильны утверждения

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

и . По предположению индукции

и . Получаем искомый вывод

Теперь убедимся, что . Рассмотрим произвольное слово , где

и

для всех . Пусть

где

для всех . Тогда

Обратно, пусть

где

для всех . Тогда

Пример 8.4.5.

Грамматика

эквивалентна следующей грамматике в нормальной форме Грейбах:

Здесь C, D, E и F соответствуют символам (A\S), (A\T), (V\T) и (U\T) из доказательства теоремы 8.4.4 (удален 21 бесполезный символ).

Теорема 8.4.6.

Пусть язык L контекстно-свободный. Тогда язык

порождается некоторой грамматикой в нормальной форме Грейбах без -правил.

Пример 8.4.7.

Грамматика

эквивалентна следующей грамматике в нормальной форме Грейбах без -правил:

Упражнение 8.4.8. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Упражнение 8.4.9. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Упражнение 8.4.10. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Упражнение 8.4.11. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Нормальная форма Хомского

Определение 8.3.1.

Грамматика в нормальной форме Хомского (грамматика в бинарной нормальной форме, квадратичная грамматика, grammar in Chomsky normal form) - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих трех видов: , , , где , , , .

Пример 8.3.2.

Грамматика

является грамматикой в нормальной форме Хомского.

Теорема 8.3.3.

Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Хомского.

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

Если правая часть какого-нибудь правила содержит символ S, то заменим грамматику

на грамматику

где S0 - новый символ, не принадлежащий множеству .

Заменим во всех правилах каждый терминальный символ a на новый нетерминальный символ Ta

и добавим к множеству P правила

для всех .

Устраним правила вида , где , заменив каждое из них на ряд более коротких правил (при этом добавляются новые нетерминальные символы).

Теперь устраним все правила вида , где A не является начальным символом. Это можно сделать так же, как в доказательстве теоремы 8.2.1.

Если для каких-то ,

и

множество P содержит правила

и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно. После этого исключим из множества P все правила вида .

Пример 8.3.4.

Грамматика

эквивалентна следующей грамматике в нормальной форме Хомского:

Теорема 8.3.5.

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

Упражнение 8.3.6. Найти контекстно-свободную грамматику в нормальной форме Хомского, эквивалентную грамматике

Нормальные формы контекстно-свободных грамматик

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

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

Устранение бесполезных символов

Определение 8.1.1.

Пусть дана порождающая грамматика . Символ

называется полезным (useful), если существуют такие слова ,

и , что

и . Символ

называется бесполезным (useless), если он не является полезным. Символ

называется порождающим (generating), если существует такое слово , что . Символ

называется достижимым если существуют такие слова

и , что .

Лемма 8.1.2.

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

все символы из N' являются порождающими. \end{lemma}

Теорема 8.1.3.

Пусть дана контекстно-свободная грамматика

и . Тогда существуют такие множества

и , что в контекстно-свободной грамматике

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

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

Пример 8.1.4.

Рассмотрим контекстно-свободную грамматику G с правилами

Удалив четыре правила, содержащие непорождающий символ U, получим грамматику G1. В ней символ X является недостижимым. Удалив три правила, содержащие X, получим грамматику G2

с правилами

Очевидно, что L(G) = L(G2) и грамматика G2

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

Упражнение 8.1.5. Найти контекстно-свободную грамматику без бесполезных символов, эквивалентную грамматике

Устранение эпсилон-правил

Теорема 8.2.1.

Пусть язык

является контекстно-свободным. Тогда язык

порождается некоторой контекстно-свободной грамматикой без -правил.

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

Если для каких-то , ,

и

множество P содержит правила

и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно.

Теперь исключим из множества P все правила вида . Полученная грамматика порождает язык .

Пример 8.2.2.

Рассмотрим язык L, порождаемый грамматикой

Язык

порождается грамматикой

Упражнение 8.2.3. Найти контекстно-свободную грамматику без -правил, эквивалентную грамматике

Лемма о разрастании для контекстно-свободных языков

Лемма 9.1.1 (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос) Пусть L - контекстно-свободный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова

длины не меньше p можно подобрать слова , для которых верно uvxyz = w,

(то есть или ),

и

для всех .

Доказательство. Пусть язык

порождается грамматикой в нормальной форме Хомского . Индукцией по k легко доказать, что для любого дерева вывода в грамматике G длина кроны дерева не превышает 2k-2, где k - количество вершин в самом длинном пути, начинающемся в корне дерева и заканчивающемся в некоторой вершине, помеченной символом из .

Положим p = 2|N|. Пусть

и . Зафиксируем некоторое дерево вывода с кроной w в грамматике G. Рассмотрим самый длинный путь в этом дереве. Этот путь содержит не менее |N| + 2 вершин. Среди них найдутся две вершины с одинаковыми метками, причем их можно выбрать среди последних |N| + 2 вершин рассматриваемого пути. Выберем слова u, v, x, y и z так, что uvxyz = w, поддерево с корнем в одной из найденных вершин имеет крону x и поддерево с корнем в другой найденной вершине имеет крону vxy.

Из того что G - грамматика в нормальной форме Хомского, заключаем, что . Неравенство

следует из того, что самый длинный путь в соответствующем слову vxy поддереве содержит не более |N| + 2 вершин. Для каждого

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

Пример 9.1.2.

Рассмотрим язык

над алфавитом {a,b,c}. Утверждение леммы 9.1.1 не выполняется ни для какого натурального числа p. Действительно, если uvxyz = apbpcp, |vy| > 0 и , то |vy|a = 0 или |vy|c = 0. Следовательно, |uvvxyyz|a = p или |uvvxyyz|c = p. Так как |uvvxyyz| > 3p, то . Из этого можно заключить, что язык L не является контекстно-свободным.

Теорема 9.1.3.

Каждый контекстно-свободный язык над однобуквенным алфавитом является автоматным.

Доказательство. Пусть дан контекстно-свободный язык L над алфавитом {a}. Согласно лемме 9.1.1 найдется такое натуральное число p, что множество

является объединением некоторого семейства арифметических прогрессий, причем у каждой прогрессии первый член и шаг не больше числа p. Так как существует лишь конечное число прогрессий натуральных чисел с таким ограничением, рассматриваемое семейство конечно. Следовательно, язык L является автоматным (используем пример 2.1.18).

Упражнение 9.1.4. Является ли контекстно-свободным язык ?

Упражнение 9.1.5. Является ли контекстно-свободным язык ?

Упражнение 9.1.6. Является ли контекстно-свободным язык ?

Упражнение 9.1.7. Является ли контекстно-свободным язык {am | m простое}?

Упражнение 9.1.8. Является ли контекстно-свободным язык ?

Упражнение 9.1.9. Является ли контекстно-свободным язык ?

Упражнение 9.1.10. Является ли контекстно-свободным язык ?

Упражнение 9.1.11. Является ли контекстно-свободным язык ?

Упражнение 9.1.12. Является ли контекстно-свободным язык ?

Упражнение 9.1.13. Является ли контекстно-свободным язык {akbmcn | k < max(m,n)}?

Упражнение 9.1.14. Является ли контекстно-свободным язык {akbmcn | k > max(m,n)}?

Упражнение 9.1.15. Является ли контекстно-свободным язык

Упражнение 9.1.16. Какому классу принадлежит язык, порождаемый грамматикой

Упражнение 9.1.17. Существуют ли такие контекстно-свободные языки

и , что язык

не является контекстно-свободным?

Лемма о разрастании для линейных языков

Определение 9.2.1.

Линейная грамматика в нормальной форме - это такая линейная грамматика, в которой каждое правило имеет вид , ,

или , где , , .

Теорема 9.2.2.

Каждая линейная грамматика эквивалентна некоторой линейной грамматике в нормальной форме.

Теорема 9.2.3.

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

Теорема 9.2.4.

Язык L является линейным тогда и только тогда, когда язык

является линейным. \end{theorem}

Лемма 9.2.5.

Пусть L - линейный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова

длины не меньше p можно подобрать слова , для которых верно uvxyz = w,

(то есть или ),

и

для всех .

Доказательство. Пусть язык

порождается линейной грамматикой в нормальной форме

без -правил. Положим p = |N| + 1. Пусть

и . Зафиксируем некоторое дерево вывода слова w в грамматике G. Рассмотрим самый длинный путь в этом дереве (он начинается с корня и заканчивается некоторым листом, помеченным символом из ). Этот путь содержит не менее |N| + 1 вершин, помеченных элементами N. Среди первых |N| + 1 вершин рассматриваемого пути найдутся две вершины с одинаковыми метками. Выберем слова u, v, x, y и z так, что uvxyz = w, поддерево с корнем в одной из найденных вершин имеет крону x и поддерево с корнем в другой найденной вершине имеет крону vxy.

Пример 9.2.6.

Рассмотрим язык

над алфавитом {a,b}. Утверждение леммы 9.2.5 не выполняется ни для какого натурального числа p. Следовательно, язык L не является линейным.

Упражнение 9.2.7. Какому классу принадлежит язык

Упражнение 9.2.8. Какому классу принадлежит язык

Упражнение 9.2.9. Какому классу принадлежит язык

Основные свойства контекстно-свободных языков

В лекции 2 были доказаны лемма о разрастании и свойства замкнутости класса автоматных языков. Некоторые из этих теорем имеют аналоги для класса контекстно-свободных языков (разделы 9.1 и 9.4), но этот класс не замкнут относительно дополнения и пересечения (раздел 9.5).

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

В разделе 9.6 доказывается, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. В сочетании с леммой о разрастании этот факт дает удобное средство, позволяющее во многих задачах доказать, что заданный язык не является контекстно-свободным. Еще одно необходимое условие контекстной свободности сформулировано в разделе 9.7*.

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

Теорема 9.5.1.

Неверно, что для любых контекстно-свободных языков L1

и L2

язык

тоже контекстно-свободный.

Доказательство. Положим

и . В примере 9.2.1 было доказано, что язык

не является контекстно-свободным.

Теорема 9.5.2.

Неверно, что для любого контекстно-свободного языка

язык

тоже контекстно-свободный.

Доказательство. Положим , где . В примере 9.3.4 было доказано, что язык L является линейным (и следовательно, контекстно-свободным).

Упражнение 9.5.3. Является ли контекстно-свободным язык ?

Упражнение 9.5.4. Является ли контекстно-свободным язык ?

Упражнение 9.5.5. Существует ли такой линейный язык L над алфавитом {a,b}, что язык

не является контекстно-свободным?

Пересечение контекстно-свободного языка с автоматным языком

Теорема 9.6.1.

Если L1 - контекстно-свободный язык и L2 - автоматный язык, то язык

является контекстно-свободным.

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

и , где ,

и

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

выполняется равенство |x| = 1 (см. лемму 2.3.3).

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

где - новый символ (не принадлежащий множеству ).

Пример 9.6.2.

Пусть . Рассмотрим контекстно-свободный язык L1, порождаемый грамматикой

и автоматный язык L2, распознаваемый конечным автоматом , где Q = {1,2}, I = {1}, F = {2},

Тогда язык

порождается контекстно-свободной грамматикой

Здесь S11, S12, S21

и S22

соответствуют символам , ,

и

из доказательства теоремы 9.6.1.

Теорема 9.6.3*.

Если L1 - линейный язык и L2 - автоматный язык, то язык

является линейным.

Пример 9.6.4*.

Пусть . Рассмотрим линейный язык L1, порождаемый грамматикой

и автоматный язык L2, распознаваемый конечным автоматом , где Q = {1,2,3}, I = {1}, F = {3},

Тогда язык

порождается контекстно-свободной грамматикой

Эту грамматику можно упростить, заменив S11 и S33

на один символ.

Упражнение 9.6.5. Найти контекстно-свободную грамматику для языка , где L1

порождается грамматикой

а язык L2

порождается грамматикой

Упражнение 9.6.6. Найти контекстно-свободную грамматику для языка , где L1

порождается грамматикой

а язык L2

порождается грамматикой

Упражнение 9.6.7. Является ли контекстно-свободным язык

Упражнение 9.6.8. Является ли контекстно-свободным язык

Упражнение 9.6.9.

Существует ли над алфавитом {a,b} такой линейный язык L, что язык

не является контекстно-свободным?

Свойства замкнутости класса контекстно-свободных языков

Теорема 9.4.1.

Если L - контекстно-свободный язык, то L*

тоже контекстно-свободный язык.

Доказательство. Пусть язык L порождается контекстно-свободной грамматикой . Тогда язык L*

порождается грамматикой

где .

Теорема 9.4.2.

Если L1

и L2 - контекстно-свободные языки над алфавитом , то

тоже контекстно-свободный язык.

Доказательство. Пусть язык L1

порождается контекстно-свободной грамматикой

и L2

порождается контекстно-свободной грамматикой , где . Тогда

порождается грамматикой

где .

Теорема 9.4.3.

Если L1

и L2 - контекстно-свободные языки над алфавитом , то

тоже контекстно-свободный язык.

Доказательство. Пусть язык L1

порождается контекстно-свободной грамматикой

и L2

порождается контекстно-свободной грамматикой , где . Тогда

порождается грамматикой

где .

Теорема 9.4.4.

Если L - контекстно-свободный язык, то

тоже контекстно-свободный язык.

Упражнение 9.4.5. Является ли контекстно-свободным язык ?

Упражнение 9.4.6.

Найти контекстно-свободную грамматику для языка , где L1

порождается грамматикой

а язык L2

порождается грамматикой

Свойства замкнутости класса линейных языков

Пример 9.3.1.

Пусть . Язык

является линейным, так как он порождается грамматикой

Пример 9.3.2.

Рассмотрим алфавит . Язык

является линейным, так как он порождается грамматикой

Теорема 9.3.3.

Если L1

и L2 - линейные языки над алфавитом , то

тоже линейный язык.

Доказательство. Пусть язык L1

порождается линейной грамматикой

и L2

порождается линейной грамматикой , где . Тогда

порождается грамматикой

где .

Пример 9.3.4.

Рассмотрим алфавит . Язык

является линейным, поскольку

где языки

являются линейными, а язык

является автоматным, и можно применить теоремы 9.3.3, 3.2.1, 2.4.1 и лемму 1.5.13.

Упражнение 9.3.5.

Пусть . Является ли линейным язык ?

Упражнение 9.3.6.

Пусть . Является ли линейным язык ?

Упражнение 9.3.7. Найти линейную грамматику, порождающую язык , где L1

порождается грамматикой

Теорема Парика

Замечание 9.1.7.

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

Определение 9.7.2.

Через

будем обозначать функцию из

в , определенную следующим образом: . Аналогично, каждому языку

ставится в соответствие множество , определенное следующим образом:

Пример 9.7.3.

Пусть

и L = {a1,a1a2a2,a2a2a1}. Тогда .

Определение 9.7.4.

Пусть

и . Тогда через

обозначается множество

При этом множество B называется системой предпериодов множества L(B,P). Множество P называется системой периодов множества L(B,P).

Определение 9.7.5.

Множество

называется линейным (linear), если A = L(B,P) для некоторых конечных множеств B и P.

Определение 9.7.6.

Множество

называется полулинейным (semilinear), если оно является объединением конечного числа линейных множеств.

Теорема 9.7.7 (Теорема Парика).

Если язык

является контекстно-свободным, то множество

является полулинейным.

Доказательство можно найти в [Гин, с. 207-211].

Пример 9.7.8.

Пусть . Рассмотрим язык . Можно проверить, что множество

не является полулинейным. Следовательно, язык L не является контекстно-свободным.

Теорема 9.7.9.

Если множество

является полулинейным, то существует такой автоматный язык L, что .

Доказательство. Докажем это для произвольного линейного множества A = L(B,P) (на полулинейные множества утверждение распространяется по теореме 3.1.1). Рассмотрим конечный автомат , где Q = {1,2}, I = {1}, F = {2} и

Очевидно, что .

Замечание 9.7.10.

Теорема 9.3.1 является следствием теорем 9.7.7 и 9.7.9.

Упражнение 9.7.11. Является ли контекстно-свободным язык

Автоматы с магазинной памятью

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

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

Автоматы с магазинной памятью с однобуквенными переходами

Теорема 10.3.1.

Каждый МП-автомат эквивалентен некоторому МП-автомату , где |Q| = 2 и каждый переход

удовлетворяет требованиям |x| = 1,

и .

Доказательство. Пусть исходным МП-автоматом распознается контекстно-свободный язык . Согласно теореме 8.4.6 язык

порождается некоторой контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , ,

и . Аналогично тому, как было сделано при доказательстве теоремы 10.2.1, положим , Q = {1,2}, I = {1},

Теорема 10.3.2.

Каждый МП-автомат эквивалентен некоторому МП-автомату , в котором каждый переход

удовлетворяет требованиям |x| = 1,

и .

Доказательство. Пусть исходным МП-автоматом распознается контекстно-вободный язык . Согласно теореме 8.4.6 язык

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

Положим , где . Далее, положим ,

Упражнение 10.3.3. Найти для языка, порождаемого грамматикой

МП-автомат, в котором каждый переход

удовлетворяет требованиям |x| = 1,

и .

Упражнение 10.3.4. Найти для языка, порождаемого грамматикой

МП-автомат, в котором каждый переход

удовлетворяет требованиям ,

и .

Характеризация контекстно-свободных языков

Теорема 10.2.1.

Если язык L является контекстно-свободным, то существует МП-автомат, распознающий этот язык.

Доказательство. Пусть язык L порождается контекстно-свободной грамматикой , в которой каждое правило имеет вид , где ,

и

(в силу теоремы 8.8.3 такая грамматика существует). Положим , , ,

и

Можно доказать, что

тогда и только тогда, когда существует левосторонний вывод

(здесь

и ).

Пример 10.2.2.

Пусть . Контекстно-свободная грамматика

и МП-автомат , где

задают один и тот же язык.

Лемма 10.2.3.

Каждый МП-автомат эквивалентен некоторому МП-автомату , где |I| = 1, |F| = 1 и каждый переход

удовлетворяет требованиям

и .

Пример 10.2.4.

Рассмотрим МП-автомат , где , , ,

Он эквивалентен МП-автомату , где

и

Пример 10.2.5.

Рассмотрим МП-автомат , где , , ,

Он эквивалентен МП-автомату , где ,

и

Пример 10.2.6.

Рассмотрим МП-автомат , где , , ,

Он эквивалентен МП-автомату , где , , , ,

Теорема 10.2.7.

Если язык L распознается некоторым МП-автоматом, то L является контекстно-свободным.

Доказательство. Пусть язык L распознается МП-автоматом . Без ограничения общности можно считать, что ,

и каждый переход

удовлетворяет требованию . Построим искомую контекстно-свободную грамматику , положив ,

и

Можно доказать, что

тогда и только тогда, когда

(здесь ).

Пример 10.2.8.

МП-автомат , где , ,

и контекстно-свободная грамматика

задают один и тот же язык. Здесь S, T и U соответствуют символам A1,2, A1,1

и A2,2

из доказательства теоремы 10.2.7.

Упражнение 10.2.9. Найти МП-автомат, распознающий язык, порождаемый грамматикой

Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык

Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык

Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык

Определение автомата с магазинной памятью

Определение 10.1.1.

Автомат с магазинной памятью (МП-автомат, магазинный автомат, стековый автомат, pushdown automaton) - это шестерка , где , , и

- конечные множества, ,

и

Здесь Q - множество состояний, - входной алфавит, - алфавит магазинной памяти (stack alphabet), - множество переходов (transition relation), элементы I называются начальными состояниями, элементы F - заключительными или допускающими состояниями.

Пример 10.1.2.

Пусть Q = {1,2}, , ,

, . Тогда - МП-автомат.

Замечание 10.1.3.

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

является переходом данного МП-автомата.

Пример 10.1.4.

Ниже приведена диаграмма МП-автомата из примера 10.1.2.

Определение 10.1.5.

Конфигурацией МП-автомата называется любая тройка , где , , .

Определение 10.1.6.

Определим на множестве всех конфигураций МП-автомата

бинарное отношение

(такт работы) следующим образом. Если ,

и , то .

Замечание 10.1.7

Обычно из контекста ясно, о каком МП-автомате идет речь. Тогда вместо

будем писать .

Пример 10.1.8.

Для МП-автомата из примера 10.1.2 выполняется

и .

Определение 10.1.9.

Бинарное отношение

определяется как рефлексивное, транзитивное замыкание отношения .

Пример 10.1.10.

Для МП-автомата из примера 10.1.2 выполняется

и .

Лемма 10.1.11.

Если

и , то .

Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации

в конфигурацию .

Определение 10.1.12.

Слово

допускается МП-автоматом , если найдутся такие состояния

и , что .

Определение 10.1.13.

Язык, распознаваемый МП-автоматом, - множество всех слов, допускаемых этим МП-автоматом. Язык, распознаваемый МП-автоматом M, обозначается L(M).

Замечание 10.1.14.

Обычно в учебниках используется более узкое определение МП-автомата, но это не меняет класса языков, распознаваемых МП-автоматами.

Пример 10.1.15.

Пусть - МП-автомат из примера 10.1.2. Тогда .

Пример 10.1.16.

Пусть . Рассмотрим МП-автомат , где , , I = {1}, F = {4,5} и

Тогда .

Определение 10.1.17.

Два МП- автомата эквивалентны, если они распознают один и тот же язык.

Замечание 10.1.18.

В данном пособии не рассматриваются преобразователи с магазинной памятью (pushdown transducer) обобщение автоматов с магазинной памятью посредством добавления "выходного" потока (см. [7, 3.5] или [2, 3.1.4]).

Замечание 10.1.19.

Некоторые авторы изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния

и

и последовательность , что . Такое определение не изменяет класса языков, распознаваемых МП-автоматами.

Замечание 10.1.20.

Некоторые авторы добавляют в определение МП-автомата седьмую компоненту - Z0, называемую маркером магазинной памяти (start pushdown symbol), и изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния

и , что . Такое определение не изменяет класса языков, распознаваемых МП-автоматами.

Замечание 10.1.21.

Класс языков, распознаваемых МП-автоматами, не изменится также, если использовать следующую естественную комбинацию двух предыдущих определений: слово w допускается МП-автоматом , если найдутся такие состояния

и

и последовательность , что .

Замечание 10.1.22.

Некоторые авторы добавляют в определение МП-автомата маркер магазинной памяти Z0, отбрасывают множество F и изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния

и , что . Это также не изменяет класса языков, распознаваемых МП-автоматами.

Упражнение 10.1.23. Найти МП-автомат, распознающий язык

Упражнение 10.1.24. Найти МП-автомат, распознающий язык

Упражнение 10.1.25. Найти МП-автомат, распознающий язык

Деление контекстно-свободных языков

Теорема 11.1.1.

Пусть L1 - контекстно-свободный язык над алфавитом

и L2 - автоматный язык над алфавитом . Тогда язык

является контекстно-свободным.

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

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

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

и для каждого перехода

выполняется равенство |x| = 1.

Тогда язык

распознается МП-автоматом , где , I = I1,

и

Пример 11.1.2.

Пусть , язык L1

распознается МП-автоматом

и язык L2

распознается конечным автоматом

Следуя доказательству теоремы 11.1.1, получаем, что язык

распознается МП-автоматом, изображенным ниже.

Пример 11.1.3.

Пусть ,

и . Тогда

Пример 11.1.4.

Пусть ,

и . Тогда

Замечание 11.1.5.

Пусть

и . Язык

является контекстно-свободным тогда и только тогда, когда язык L является контекстно-свободным.

Упражнение 11.1.6.

Существует ли такой контекстно-свободный язык , что язык Subw не является контекстно-свободным?

Упражнение 11.1.7. Существует ли такой контекстно-свободный язык L над алфавитом {a,b}, что язык

не является контекстно-свободным?

Упражнение 11.1.8. Существует ли такой контекстно-свободный язык L над алфавитом {a,b}, что язык

не является контекстно-свободным?

Дополнительные свойства контекстно-свободных языков

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

Гомоморфизмы и контекстно-свободные языки

Теорема 11.2.1.

Для любого гомоморфизма

и контекстно-свободного языка

язык h(L) является контекстно-свободным.

Доказательство. Приведем здесь доказательство, использующее МП-автоматы, хотя эту теорему легко доказать и с помощью контекстно-свободных грамматик. Пусть язык L распознается МП-автоматом . Тогда язык h(L) распознается МП-автоматом , где

Пример 11.2.2.

Пусть

и . Рассмотрим контекстно-свободный язык L, порождаемый грамматикой

и гомоморфизм , заданный равенствами h(a) = a, h(b) = bba и h(c) = a. Тогда язык h(L) порождается контекстно-свободной грамматикой

Упражнение 11.2.3. Пусть гомоморфизм

задан соотношениями h(a) = b, , h(c) = a. Рассмотрим язык L, порождаемый грамматикой

Найти контекстно-свободную грамматику для языка h(L).

Теорема 11.2.4.

Для любого гомоморфизма

и контекстно-свободного языка

язык h-1(L) является контекстно-свободным.

Доказательство. Введем обозначение

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

выполняется неравенство . Можно проверить, что в этом случае язык h-1(L) распознается МП-автоматом , где

Пример 11.2.5.

Пусть

и . Рассмотрим гомоморфизм , заданный равенствами h(c) = aa, h(d) = b и h(e) = bba. Пусть контекстно-свободный язык L распознается МП-автоматом , где Q = {p}, , I = {p}, F = {p},

Тогда язык h-1(L) распознается МП-автоматом , где , ,

и

Язык h-1(L) также порождается контекстно-свободной грамматикой

Упражнение 11.2.6. Пусть гомоморфизм

задан соотношениями h(a) = ab, h(b) = aaba, h(c) = b. Рассмотрим язык L, порождаемый грамматикой

Описать язык h-1(L).

Упражнение 11.2.7.

задан соотношениями h(c) = a, h(d) = ba, h(e) = bb. Рассмотрим язык L, порождаемый грамматикой

Найти контекстно-свободную грамматику для языка h-1(L).

Упражнение 11.2.8. Пусть гомоморфизм

задан соотношениями , , . Рассмотрим язык , порождаемый грамматикой

Найти контекстно-свободную грамматику для языка h-1(L).

Упражнение 11.2.9. Обозначим через L язык, порождаемый грамматикой

Рассмотрим гомоморфизм , заданный соотношениями

h1(a) = ac , h1(b) = bc , h1(c) = aa , h1(d) = ab , h1(e) = ba , h1(f) = bb ,

и гомоморфизм , заданный соотношениями

h2(a) = a , h2(b) = b , h2(c) = ab , h2(d) = aa , h2(e) = bb , h2(f) = ba .

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

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

Теорема 11.3.1.

Рассмотрим алфавит

и язык , порождаемый контекстно-свободной грамматикой G0:

Произвольный язык

является контекстно-свободным тогда и только тогда, когда существует такой гомоморфизм , что L = h-1(L0) или .

Доказательство. Достаточность следует из теоремы 11.2.4. Приведем теперь идею доказательства необходимости (полное доказательство можно найти в [Сал, с. 103-109]).

Пусть дан произвольный контекстно-свободный язык L. Согласно теореме 8.4.6 язык

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

Определим вспомогательную функцию , ставящую в соответствие каждому символу из

конечный язык над алфавитом

следующим образом:

Искомый гомоморфизм h определяется следующим образом: если

положим

Пример 11.3.2.

Пусть . Рассмотрим язык L, порождаемый грамматикой

Тогда L = h-1(L0), где гомоморфизм h задан равенствами

h(d) = cb1b2b1a1a2a2a1a1a2a1c, h(f) = cb1b2b1cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c, h(g) = cb1b2b2b2b1c.

Рассмотрим, например, слово . Проверим, что слово h(dffg) выводится в грамматике G0

из теоремы 11.3.1. Очевидно, что . С помощью последних пяти правил грамматики G0

можно вывести, что

Осталось найти такие шесть выводимых из C слов , что

Подходят слова

w1 = c, w2 = c, w3 = cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c, w4 = cb1b2b1c, w5 = cb1b2b2b1a1a2a2a2a1a1a2a2a1c, w6 = c.

Теорема 11.3.3 (Теорема Хомского-Шютценберже).

Язык

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

над алфавитом

и гомоморфизм , что , где - язык Дика над 2n буквами.

Доказательство можно найти в [Лал, с. 331-333].

Упражнение 11.3.4.

Рассмотрим язык L1, порождаемый грамматикой

и язык L2, порождаемый грамматикой

Найти такой гомоморфизм , что

Детерминированные автоматы с магазинной памятью

Определение 12.1.1.

Будем говорить, что два перехода МП-автомата

и

являются совместными, если

p1 = p2;

или ;

или .

Определение 12.1.2.

МП-автомат называется детерминированным (deterministic), если он имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны.

Пример 12.1.3.

МП-автомат M из примера 10.2.8 не является детерминированным, так как переходы

и

совместны.

Определение 12.1.4.

Язык L над алфавитом

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

над алфавитом , где - дополнительный символ, не принадлежащий множеству . Символ

называется маркером конца строки.

Пример 12.1.5.

Рассмотрим алфавит . Язык - детерминированный контекстно-свободный язык, так как язык

порождается детерминированным МП-автоматом (хотя язык L не порождается никаким детерминированным МП-автоматом).

Пример 12.1.6.

Язык L, распознаваемый МП-автоматом M из примера 10.2.8, является детерминированным контекстно-свободным языком, так как язык

порождается детерминированным МП-автоматом

где

Упражнение 12.1.7. Является ли детерминированным контекстно-свободный язык ?

Детерминированные контекстно-свободные языки

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

Свойства класса детерминированных языков

Теорема 12.2.1.

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

Доказательство. Утверждение следует из теоремы 2.7.1.

Лемма 12.2.2.

Каждый детерминированный МП-автомат эквивалентен некоторому детерминированному МП-автомату , где для каждого перехода

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

Доказательство. Пусть дан детерминированный МП-автомат . Назовем избытком перехода

натуральное число . Докажем лемму индукцией по сумме избытков всех переходов.

Шаг индукции. Пусть существует переход

с положительным избытком. Рассмотрим четыре случая.

Случай 1. . Обозначим первый символ слова x0 через a0. Преобразуем МП-автомат M в эквивалентный ему детерминированный МП-автомат с меньшей суммой избытков всех переходов. Для этого добавим новое состояние r и переход . Каждый переход вида заменим на переход . К полученному таким образом детерминированному МП-автомату применимо предположение индукции.

Случай 2. . Обозначим первый символ слова

через C0. Преобразуем МП-автомат M в эквивалентный ему детерминированный МП-автомат с меньшей суммой избытков всех переходов. Для этого добавим новое состояние r и переход . Каждый переход вида заменим на переход . К полученному таким образом детерминированному МП-автомату применимо предположение индукции.

Случай 3. Существует переход . Тогда переходы

и

совместны. Противоречие.

Случай 4. Существуют переход

и переход , где

и . Тогда переходы

и

совместны. Противоречие.

Лемма 12.2.3.

Каждый детерминированный МП-автомат

эквивалентен некоторому детерминированному МП-автомату , где каждый переход

удовлетворяет условиям

и .

Доказательство. Сначала применим лемму 12.2.2, затем преобразуем МП-автомат так, чтобы для каждого перехода

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

(см. пример 10.2.4), и в заключение заменим каждый переход вида

на два последовательных перехода (см. пример 10.2.5).

Лемма 12.2.4.

Пусть ,

и язык

порождается некоторым детерминированным МП-автоматом. Тогда этот язык порождается также некоторым детерминированным МП-автоматом , где , ,

,
и каждый переход
удовлетворяет условиям
и .
Доказательство. Применив лемму 12.2.3, получим детерминированный МП-автомат . Построим искомый МП-автомат , положив , , , , , ,
Теорема 12.2.5.
Язык
является детерминированным контекстно-свободным языком тогда и только тогда, когда найдется такой детерминированный МП-автомат , что
Доказательство. Достаточность проверяется легко. Докажем необходимость. Рассмотрим МП-автомат
о котором говорится в лемме 12.2.4.
Для любых
и
введем обозначение
Очевидно, что
для любых ,
и .
Построим искомый МП-автомат , положив
(Напоминаем, что через
обозначается множество всех подмножеств множества Q2.)
Индукцией по количеству тактов работы можно доказать, что
тогда и только тогда, когда
и
для каждого .
Теорема 12.2.6.
Пусть L - детерминированный контекстно-свободный язык. Тогда язык L не является существенно неоднозначным.
Доказательство. Пусть дан детерминированный контекстно-свободный язык L. Рассмотрим МП-автомат
о котором говорится в лемме 12.2.4. Применив к этому МП-автомату конструкцию из доказательства теоремы 10.2.7, получим однозначную контекстно-свободную грамматику G, порождающую язык . Стирая в этой грамматике все вхождения символа , получим контекстно-свободную грамматику G', порождающую язык L.
Так как МП-автомат M не содержит переходов, ведущих из Q2
в Q1, а символ
встречается только на переходах, ведущих из Q1
в Q2, то в каждом G'-выводе однозначно определяется правило, которому в G соответствует правило, содержащее . Поэтому существует естественное однозначное соответствие между деревьями вывода в грамматике G' и деревьями вывода в грамматике G (при этом кроны соответствующих друг другу деревьев различаются только символом ). Следовательно, грамматика G' тоже является однозначной.
Теорема 12.2.7.
Дополнение каждого детерминированного контекстно-свободного языка является детерминированным контекстно-свободным языком.
Доказательство можно найти в [7, c. 110-116] или [2, c. 212-217].
Пример 12.2.8.
Язык
над алфавитом {a,b,c} не является детерминированным контекстно-свободным языком, так как его дополнение не является контекстно-свободным.
Теорема 12.2.9.
Неверно, что для любых детерминированных контекстно-свободных языков L1
и L2
язык
тоже является детерминированным контекстно-свободным языком.
Доказательство. Достаточно рассмотреть детерминированные контекстно-свободные языки L1
и L2
из доказательства теоремы 9.5.1.
Теорема 12.2.10.
Неверно, что для любых детерминированных контекстно-свободных языков L1
и L2
язык
тоже является детерминированным контекстно-свободным языком.
Доказательство. Утверждение следует из теорем 12.2.7 и 12.2.9 и закона де Моргана.
Упражнение 12.2.11. Является ли детерминированным контекстно-свободный язык ?

Нисходящий разбор

Определение 13.1.1.

Процесс нахождения дерева вывода слова w в заданной контекстно-свободной грамматике называется синтаксическим разбором или синтаксическим анализом (parsing).

Определение 13.1.2.

Протоколом левостороннего вывода в контекстно-свободной грамматике

будем называть последовательность правил, примененных в этом выводе. Формально говоря, протоколом левостороннего вывода

является последовательность

где для каждого i < n, если

и

для некоторых , , , , то Ai+1 = B и .

Пример 13.1.3.

Рассмотрим контекстно-свободную грамматику

Дереву вывода

соответствует левосторонний вывод

Протоколом этого вывода является последовательность

Лемма 13.1.4.

Разным левосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

Замечание 13.1.5.

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

Например, протокол левостороннего вывода из примера 13.1.3 задает процесс постепенного конструирования дерева вывода, изображенный ниже.

Определение 13.1.6.

Левым разбором (left parse) слова w в контекстно-свободной грамматике G называется протокол любого левостороннего вывода слова w в грамматике G.

Пример 13.1.7.

Левым разбором слова

aceaacecbecbb

в грамматике из примера 13.1.3 является последовательность

Определение 13.1.8.

Процесс нахождения левого разбора слова w в заданной контекстно-свободной грамматике G называется нисходящим разбором (top-down parsing).

Определение 13.1.9.

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

Пример 13.1.10.

Рассмотрим МП-автомат

из примера 10.2.8. Последовательность

является вычислительным процессом этого МП-автомата.

Определение 13.1.11.

Если в некотором вычислительном процессе МП-автомата

первая конфигурация имеет вид , где

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

Пример 13.1.12.

Вычислительный процесс из примера 13.1.10 допускает слово bab.

Замечание 13.1.13.

МП-автомат M допускает слово

тогда и только тогда, когда некоторый вычислительный процесс МП-автомата M допускает слово w.

Синтаксический разбор

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

Восходящий разбор

Определение 13.2.1.

Протоколом правостороннего вывода в контекстно-свободной грамматике

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

является последовательность

где для каждого i<n, если

и

для некоторых , , , , то An-i = B и .

Пример 13.2.2.

Рассмотрим контекстно-свободную грамматику

и дерево вывода

из примера 13.1.3. Этому дереву вывода соответствует правосторонний вывод

Протоколом этого вывода является последовательность

Лемма 13.2.3.

Разным правосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

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

Например, протокол правостороннего вывода из примера 13.2.2 задает процесс постепенного конструирования дерева вывода, изображенный ниже.

Определение 13.2.5.

Правым разбором (right parse) слова w в контекстно-свободной грамматике G называется протокол любого правостороннего вывода слова w в грамматике G.

Пример 13.2.6.

Правым разбором слова aceaacecbecbb в грамматике из примера 13.2.2 является последовательность

Определение 13.2.7.

Процесс нахождения правого разбора слова w в~заданной контекстно-свободной грамматике G называется восходящим разбором (bottom-up parsing).

Определение 13.2.8.

Пусть даны контекстно-свободная грамматика

и МП-автомат . Будем говорить, что МП-автомат M - восходящий магазинный анализатор (bottom-up, left-to-right parser) для грамматики G, если

и существует такой гомоморфизм , что для каждого вычислительного процесса (МП-автомата M), допускающего слово , образ протокола этого вычислительного процесса при гомоморфизме r является протоколом некоторого правостороннего вывода слова w в грамматике .

Пример 13.2.9.

Рассмотрим контекстно-свободную грамматику

из примера 13.1.17. Язык

распознается недетерминированным МП-автоматом , где

и

Можно проверить, что МП-автомат M является восходящим магазинным анализатором для грамматики G из примера 13.1.17.

Определение 13.2.10.

Контекстно-свободная грамматика

принадлежит классу LR(1), если для любых , , , , , , , ,

из условий

следует, что A1 = A2

и .

Замечание 13.2.11.

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

Замечание 13.2.12.

Буква L в названии класса LR(1) означает, что входное слово читается слева направо (left-to-right). Буква R означает, что строится правосторонний вывод (rightmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

Теорема 13.2.13.

Для каждой грамматики из класса LR(1) существует детерминированный восходящий магазинный анализатор.

Доказательство можно найти в [2, с. 420-447].

Теорема 13.2.14.

Грамматики из класса LR(1) порождают только детерминированные контекстно-свободные языки.

Теорема 13.2.15.

Каждая грамматика из класса LL(1) принадлежит также классу LR(1).

Упражнение 13.2.16.

Найти все правые разборы слова bbacba в грамматике

Упражнение 13.2.17.

Найти детерминированный восходящий магазинный анализатор для грамматики

Упражнение 13.2.18.

Найти детерминированный восходящий магазинный анализатор для грамматики

Алгоритмические проблемы

Основная цель этой лекции - дать определения понятий, необходимых для математически строгой формулировки результатов следующих двух лекций. Для более подробного ознакомления с вычислимостью, разрешимостью, перечислимостью и универсальными моделями вычислений следует обратиться к какому-либо вводному курсу по теории алгоритмов, например [30, с. 93-106, 109-121]

или [5,с. 8-20, 112-123].

В разделе 14.1 фиксируется конкретная модель вычислений - машина Тьюринга и даются определения (недетерминированной) машины Тьюринга, детерминированной машины Тьюринга и вычислимой функции. В разделе 14.2 определяются разрешимые и перечислимые множества. В разделе 14.3 вводятся термины "массовая задача", "индивидуальная задача", "схема кодирования", "задача распознавания", "алгоритмическая проблема". В 14.4* формулируется теорема о соответствии машин Тьюринга грамматикам типа 0, а также теорема о нормальной форме для грамматик типа 0. В разделе 14.5 формулируется известная неразрешимая проблема - проблема соответствий Поста. На сведEнии именно к этой алгоритмической проблеме основываются все доказательства неразрешимости в лекции 16, где рассматриваются алгоритмические проблемы, связанные с контекстно-свободными грамматиками.

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

Теорема 14.4.1.

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

Доказательство можно найти, например, в [СерГал с. 24-26].

Упражнение 14.4.2.

Выводимо ли слово aab в грамматике

Упражнение 14.4.3.

Выводимо ли слово aaaaaaaab в грамматике

Замечание 14.4.4.

Неизвестно, порождает ли грамматика

все слова в алфавите {a,b}.

Упражнение 14.4.5.

Пусть . Рассмотрим грамматику

Выводимо ли в ней слово ccdcdcddccddcdcccabba?

Упражнение 14.4.6.

Является ли разрешимым язык, порождаемый грамматикой

Определение 14.4.7.

Порождающая грамматика в нормальной форме - это порождающая грамматика, в которой каждое правило имеет вид ,

или , где , , , .

Теорема 14.4.8.

Каждая порождающая грамматика эквивалентна некоторой порождающей грамматике в~нормальной форме.

Упражнение 14.4.9.

Существует ли такая порождающая грамматика G, что язык

не порождается ни одной грамматикой типа 0?

Машины Тьюринга

Определение 14.1.1.

Машиной Тьюринга называется семерка

где Q, и - конечные множества, , , ,

и

Здесь Q - множество состояний - входной алфавит (внешний алфавит), - ленточный алфавит (tape alphabet), b0 - бланк (пробел, пустой символ, blank symbol), - множество переходов, I - множество начальных состояний, F - множество заключительных состояний.

Определение 14.1.2.

Конфигурацией машины Тьюринга называется любая четверка , где , , , .

Определение 14.1.3.

Определим на множестве всех конфигураций машины Тьюринга M бинарное отношение

(такт работы) следующим образом.

Если , то

для всех

и .

Если , то

для всех ,

и .

Если , то

для всех ,

и .

Замечание 14.1.4.

Если из контекста ясно, о какой машине Тьюринга идет речь, вместо

будем писать просто .

Определение 14.1.5.

Как и для МП-автомата, для машины Тьюринга бинарное отношение

определяется как рефлексивное, транзитивное замыкание отношения .

Замечание 14.1.6.

Если , то для любых

и

найдутся такие

и , что .

Замечание 14.1.7.

Конфигурацию

иногда изображают сокращенно .

Замечание 14.1.8.

Машины Тьюринга можно изображать в~виде диаграмм. При этом каждое состояние обозначается кружком, а переход - стрелкой. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое заключительное состояние отмечается на диаграмме двойным кружком. Стрелка с пометкой a:ck, ведущая из p в q, показывает, что

является переходом данной машины Тьюринга. Обычно на диаграммах вместо чисел -1, 0, 1 (обозначающих движение влево, стояние на месте, движение вправо) используются буквы L, N, R соответственно.

Пример 14.1.9.

Рассмотрим машину Тьюринга

где , , , , , ,

Можно проверить, что для любого

выполняется следующее:

Определение 14.1.10.

Машина Тьюринга

называется детерминированной, если множество I содержит ровно один элемент и для каждой пары

существует не более одной тройки

со свойством .

Пример 14.1.11

Машина Тьюринга из примера 14.1.9 является детерминированной.

Массовые задачи

Определение 14.3.1.

Массовой задачей (problem) называется бесконечная серия "однотипных" индивидуальных задач (instance), каждая из которых имеет определенный ответ. С каждой массовой задачей связана некоторая фиксированная схема кодирования (encoding scheme), которая отображает индивидуальные задачи в их коды - слова в некотором фиксированном алфавите. При этом требуется, чтобы множество кодов всех индивидуальных задач было разрешимым.

Определение 14.3.2.

Задачей распознавания (decision problem) называется массовая задача, в которой ответами индивидуальных задач могут быть только "да" и "нет" (то есть существует только два возможных ответа).

Пример 14.3.3.

Зафиксируем некоторый алфавит . Рассмотрим следующие однотипные индивидуальные задачи: даны два слова

и , необходимо выяснить, является ли слово x подсловом слова y.

Пусть # - новый символ, не принадлежащий алфавиту . Кодом индивидуальной задачи про конкретные слова x и y будем считать слово x#y в алфавите .

Эта массовая задача является задачей распознавания.

Определение 14.3.4.

Алгоритмическая проблема - проблема, в которой требуется найти алгоритм для решения массовой задачи. Если такой алгоритм существует, то данная проблема называется алгоритмически разрешимой или просто разрешимой (decidable, solvable), в противном случае ее называют алгоритмически неразрешимой (undecidable, unsolvable).

Замечание 14.3.5.

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

Пример 14.3.6.

Рассмотрим массовую задачу из примера 14.3.3. Соответствующая алгоритмическая проблема разрешима, так как разрешим язык .

Пример 14.3.7.

Зафиксируем некоторый алфавит . Рассмотрим следующие однотипные индивидуальные задачи: дана порождающая грамматика

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

Для полной строгости необходимо договориться, как кодировать грамматику G в виде слова. Например, можно использовать алфавит , где - дополнительные символы, не принадлежащие множеству . Вспомогательный символ Ai

заменим на слово, состоящее из символа

и кода числа i в двоичной системе счисления. В каждом правиле

добавим символ

на месте

и после слова . Кодом грамматики G будем считать результат конкатенации кодов всех правил из множества P. Например, грамматика

(над алфавитом ) кодируется словом

Легко понять, что соответствующая алгоритмическая проблема (проблема проверки праволинейности) разрешима.

Упражнение 14.3.8.

Разрешима ли алгоритмическая проблема распознавания четности длины слова над алфавитом {a,b}?

Проблема соответствий Поста

Определение 14.5.1.

Постовской системой соответствия над алфавитом

называется упорядоченная пара конечных последовательностей , где

и

для всех i.

Замечание 14.5.2.

Систему

иногда изображают в виде

Определение 14.5.3.

Решением (match) постовской системы соответствия ((x1,...,xn),(y1,...,yn)) называется непустая последовательность индексов , удовлетворяющая условию

где

для каждого j.

Пример 14.5.4.

Пусть . Рассмотрим постовскую систему соответствия

Последовательность (2,1,3,2,2) является решением этой системы, так как

Упражнение 14.5.5.

Пусть . Существует ли решение у постовской системы соответствия

Определение 14.5.6.

Проблемой соответствий Поста (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.

Теорема 14.5.7.

Пусть . Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом

узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)

Доказательство можно найти в [ХопМот, 9.4].

Упражнение 14.5.8.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.9.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.10.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.11.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.12.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.13.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.14.

Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.15.

Существует ли постовская система соответствия, имеющая ровно одно решение?

Разрешимые и перечислимые множества

Определение 14.2.1.

Говорят, что детерминированная машина Тьюринга

с выделенным состоянием qa

разрешает (decides) язык , если

1) для каждого слова

найдутся такие

и , что ;

2) для каждого слова

найдутся такие

и , что . Состояние qa

называется допускающим (принимающим, accept state), состояние qr

называется отвергающим (непринимающим, (reject state).

Пример 14.2.2.

Рассмотрим детерминированную машину Тьюринга

где , , , , , ,

и

Эта машина Тьюринга разрешает язык .

Определение 14.2.3.

Язык L над алфавитом

называется разрешимым или рекурсивным (decidable, recursive), если существует детерминированная машина Тьюринга

(с выделенным состоянием qa), которая разрешает язык L.

Определение 14.2.4.

Говорят, что машина Тьюринга

допускает (принимает, accepts) слово , если для некоторых

и

.

Определение 14.2.5.

Язык, допускаемый машиной Тьюринга M, - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.

Определение 14.2.6.

Язык называется перечислимым (рекурсивно перечислимым, полуразрешимым, recursively enumerable), если существует детерминированная машина Тьюринга, допускающая этот язык.

Замечание 14.2.7.

В определении 14.2.6 можно отбросить требование детерминированности машины Тьюринга.

Теорема 14.2.8.

Каждый разрешимый язык является перечислимым.

Доказательство. Пусть дана машина Тьюринга

с выделенным состоянием qa, которая разрешает язык . Тогда машина Тьюринга

допускает язык L.

Пример 14.2.9.

Если в машине Тьюринга из примера 14.1.15 заменить переход

на , то получится машина Тьюринга, допускающая язык . Следовательно, этот язык является перечислимым. Можно доказать, что он даже является разрешимым.

Теорема 14.2.10.

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

Доказательство. Доказательство существования перечислимого неразрешимого множества можно найти, например, в [31, 9.2].

Упражнение 14.2.11.

Найти детерминированную машину Тьюринга с входным алфавитом {a}, разрешающую язык .

Упражнение 14.2.12.

Найти детерминированную машину Тьюринга с входным алфавитом {a}, допускающую язык

Алгоритмически разрешимые проблемы

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

Первые два раздела этой лекции посвящены контекстным языкам. В разделах 15.3-15.6 сформулированы теоремы о разрешимости для некоторых алгоритмических проблем. Доказательства этих теорем опираются на конструктивность рассуждений, проведенных в лекциях 3 и 8. В разделе 15.7* приводится новый неожиданный результат, доказанный в 1997 году.

Проблема эквивалентности конечных автоматов (или, что то же самое, регулярных выражений) разрешима, но, к сожалению, она сложна, то есть нахождение ответа индивидуальной задачи требует (в некотором смысле) много времени. В разделе 15.9* указывается, что даже для регулярных выражений без итерации (которые, очевидно, соответствуют конечным автоматам без циклов) проблема неэквивалентности NP-полна (необходимые определения из теории сложности вычислений приведены в разделе 15.8*).

Классы P и NP

Определение 15.8.1.

Пусть машина Тьюринга M допускает язык L. Говорят, что язык L распознается за полиномиальное время на машине M, если существует такой многочлен p, что любое слово

принимается машиной M не более чем за p(|w|) тактов.

Определение 15.8.2.

Через P обозначается класс тех языков, которые распознаются за полиномиальное время на некоторой детерминированной машине Тьюринга.

Определение 15.8.3.

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

Замечание 15.8.4.

Очевидно, что . Неизвестно, совпадают ли классы P и NP.

Теорема 15.8.5.

Все языки из класса NP являются разрешимыми.

Определение 15.8.6.

Всюду определенная функция f из

в

называется вычислимой за полиномиальное время, если ее вычисляет некоторая детерминированная машина Тьюринга M (если , то данная функция f рассматривается как частичная функция из

в ) и существует такой многочлен p, что для любого слова

машина M вычисляет значение f(w) не более чем за p(|w|) тактов.

Определение 15.8.7.

Язык

полиномиально сводится (is polynomial time reducible) к языку , если существует такая вычислимая за полиномиальное время всюду определенная функция f из

в , что для любого слова

условие

равносильно условию .

Определение 15.8.8.

Формальный язык L называется NP-сложным (NP-hard}, если каждый язык из класса NP полиномиально сводится к языку L.

Определение 15.8.9.

Формальный язык называется NP-полным (NP-complete), если он принадлежит классу NP и является NP-сложным.

Определение 15.8.10.

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

Теорема 15.8.11 (теорема Кука-Левина).

Проблема выполнимости булевых формул в конъюнктивной нормальной форме N-полна.

Доказательство можно найти, например, в [Сэв, с. 325-328] или [ГэрДжо, с. 57-63].

Упражнение 15.8.12.

Существует ли такой язык

из класса P, что язык не принадлежит классу P?

Упражнение 15.8.13.

Существуют ли такие языки L1 и L2

из класса P, что язык

не принадлежит классу P?

Упражнение 15.8.14.

Существуют ли такие языки L1 и L2

из класса NP, что язык

не принадлежит классу NP?

Линейно ограниченные автоматы

Определение 15.2.1.

Машина Тьюринга

называется линейно ограниченным автоматом (linear bounded automaton), если не существует таких , , ,

и , что

и |xay| > |b0wb0|.

Теорема 15.2.2.

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

Замечание 15.2.3.

Неизвестно, верен ли аналог теоремы 15.2.2 для детерминированных линейно ограниченных автоматов.

Теорема 15.2.4.

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

Замкнутость относительно операции дополнения доказали в 1987 году (независимо друг от друга) Нил Иммерман (Neil Immerman) и Роберт Селепчени (Robert Szelepcs) (см. [Imm, Sze]). Замкнутость относительно операции объединения очевидна, а пересечение выражается через объединение и дополнение.

Упражнение 15.2.5.

Является ли контекстным язык

Упражнение 15.2.6.

Является ли контекстным язык

Неукорачивающие грамматики

Определение 15.1.1.

Порождающая грамматика

называется неукорачивающей (noncontracting), если для каждого правила

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

Теорема 15.1.2.

Существует алгоритм, позволяющий по произвольной неукорачивающей грамматике G и по слову w узнать, верно ли, что .

Теорема 15.1.3.

Каждая контекстная грамматика является неукорачивающей. Каждая неукорачивающая грамматика эквивалентна некоторой контекстной грамматике.

Пример 15.1.4.

Грамматика

эквивалентна контекстной грамматике из примера 1.5.4.

Упражнение 15.1.5.

Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.6.

Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.7.

Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.7.

Найти неукорачивающую грамматику, порождающую язык .

Проблема бесконечности языка

Теорема 15.5.1.

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

Пример 15.5.2.

Рассмотрим контекстно-свободную грамматику G из примера 8.1.4. Чтобы выяснить, является ли язык L(G) бесконечным, удалим сначала все бесполезные символы. Затем устраним все -правила. Так как

и , то можно всюду заменить W на Z. Получится грамматика

эквивалентная исходной грамматике G. Очевидно, что эта грамматика не содержит "рекурсивных" нетерминальных символов. Следовательно, язык L(G) является конечным.

Упражнение 15.5.3.

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

Проблема эквивалентности детерминированных МП-автоматов

Теорема 15.7.1.

Существует алгоритм, позволяющий по произвольным двум детерминированным МП-автоматам M1 и M2

узнать, верно ли, что L(M1) = L(M2).

Эту теорему доказал Жеро Сенизерг (Geraud Senizergues) в 1997 году. Упрощенное доказательство приводится в [Sti].

Упражнение 15.7.2.

Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?

Упражнение 15.7.3.

Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?

Проблема эквивалентности конечных автоматов

Теорема 15.6.1.

Существует алгоритм, позволяющий по произвольным двум праволинейным грамматикам G1 и G2

узнать, верно ли, что .

Теорема 15.6.2.

Существует алгоритм, позволяющий по произвольным двум праволинейным грамматикам G1 и G2

узнать, верно ли, что L(G1) = L(G2).

Упражнение 15.6.3.

Эквивалентны ли грамматика

и грамматика

Проблема неравенства регулярных выражений без итерации

Теорема 15.9.1.

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

Доказательство. По регулярному выражению без итерации легко построить конечный автомат с однобуквенными переходами, не содержащий циклов. Проблема неравенства таких конечных автоматов принадлежит классу NP: достаточно "угадать" слово, принадлежащее разности языков, распознаваемых двумя данными автоматами, и, продвигаясь по этому слову буква за буквой, подобно доказательству теоремы 2.7.1 вычислять, в каких состояниях автоматы могут оказаться. При этом длину слова можно ограничить максимумом числа состояний двух автоматов.

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

Пусть дана булева формула , составленная из пропозициональных переменных x1, x2, ..., xn

(при более формальном подходе можно считать xi обозначением слова p#i, как это сделано в примере 7.2.8). Здесь для каждого

формула Cj

является элементарной дизъюнкцией. Для краткости будем обозначать отрицание переменной xi

через

(а не через , как в примере 7.2.8).

Построим два регулярных выражения над алфавитом . В качестве первого регулярного выражения возьмем

Для удобства отождествим истинностные значения "ложь" и "истина" с символами a и b соответственно. Тогда оценку пропозициональных переменных x1, x2, ..., xn

можно естественным образом отождествить со словом длины n в алфавите . Второе регулярное выражение e построим так, чтобы выполнялось равенство

Если m = 1, то это сделать легко. Возьмем в качестве e произведение n сомножителей, каждый из которых совпадает с~одним из следующих четырех регулярных выражений: (a + b), a, b, 0.
При этом i- й сомножитель соответствует пропозициональной переменной xi

и выбирается следующим образом:



если данная элементарная дизъюнкция не содержит ни литерала xi, ни литерала , то используем выражение (a+b);

если она содержит литерал xi, но не содержит литерала , то используем выражение a;

если она содержит литерал , но не содержит литерала xi, то используем выражение b;

если она содержит оба литерала xi и , то используем выражение 0.

Если m > 1, то построим по указанному методу для каждой из булевых формул C1, C2, ..., Cm

регулярное выражение и возьмем их сумму.

Легко видеть, что два построенных так регулярных выражения равны тогда и только тогда, когда булева формула

невыполнима.

Пример 15.9.2.

Пусть . Регулярные выражения

(a+b)(a+b)(a+b)

и

ab(a+b)+(a+b)ab+b(a+b)(a+b)+(a+b)(a+b)a

равны, так как булева формула

невыполнима (или, другими словами, булева формула

является тавтологией).

Упражнение 15.9.3.

Равны ли регулярные выражения

(a+b)(a+b)(a+b)

и

bb(a+b)+ba(a+b)+a(a+b)b+(a+b)aa ?

Упражнение 15.9.4.

Равны ли регулярные выражения

(a+b)(a+b)(a+b)(a+b)

и

aab(a+b)+a(a+b)(a+b)b+(a+b)aa(a+b)+(a+b)bb(a+b)+ +(a+b)baa+bab(a+b)+b(a+b)(a+b)b ?

Упражнение 15.9.5.

Эквивалентен ли конечный автомат

конечному автомату, изображенному ниже?

Проблема пустоты языка

Теорема 15.4.1.

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

Доказательство. Удалим из G все бесполезные символы, кроме начального символа (как в доказательстве теоремы 8.1.3). Если полученная грамматика содержит хотя бы одно правило, то .

Упражнение 15.4.2.

Является ли непустым язык, порождаемый грамматикой

Проблема выводимости слова

Теорема 15.3.1.

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

Теорема 15.3.2.

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

Упражнение 15.3.3.

Принадлежит ли слово aaaaabbbabb языку, порождаемому грамматикой

Упражнение 15.3.4.

Принадлежит ли слово abababa языку, порождаемому грамматикой

Алгоритмически неразрешимые проблемы

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

В разделе 16.1 доказывается неразрешимость проблемы пустоты пересечения контекстно-свободных языков и проблемы бесконечности пересечения контекстно-свободных языков.

В разделе 16.2 доказывается неразрешимость проблемы однозначности контекстно-свободной грамматики.

В разделе 16.3 доказывается неразрешимость проблемы равенства контекстно-свободных языков.

В разделе 16.4 доказывается неразрешимость проблемы автоматности контекстно-свободного языка.

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

Дополнение контекстно-свободного языка

Лемма 16.3.1.

Рассмотрим алфавит . Язык

является контекстно-свободным при любом .

Пример 16.3.2.

Пусть . Тогда язык

над алфавитом

порождается контекстно-свободной грамматикой

Заметим, что

для каждого i.

Язык

является даже линейным (чтобы получить линейную грамматику, достаточно "раскрыть" вспомогательные символы A, B и Z).

Замечание 16.3.3.

Лемму 16.3.1 можно доказать, явно построив контекстно-свободную грамматику (как в примере 16.3.2), а можно и вывести из теоремы 12.2.7}, проверив, что - детерминированный контекстно-свободный язык.

Определение 16.3.4.

Пусть , , , где

и

для всех i. Обозначим через

язык .

Лемма 16.3.5.

Язык

является контекстно-свободным при любых и .

Доказательство. .

Лемма 16.3.6.

Дополнение языка

является непустым тогда и только тогда, когда постовская система соответствия

имеет решение.

Доказательство Утверждение следует из леммы 16.1.2.

Теорема 16.3.7.

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

узнать, верно ли, что .

Доказательство Очевидно, что

тогда и только тогда, когда дополнение языка L(G) является пустым.

Теорема 16.3.8.

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

над алфавитом

узнать, верно ли, что L(G1) = L(G2).

Доказательство Утверждение следует из предыдущей теоремы и примера 1.5.16.

Теорема 16.3.9.

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

над алфавитом

узнать, верно ли, что .

Доказательство Очевидно, что

тогда и только тогда, когда .

Лемма 16.3.10.

Дополнение языка

является бесконечным тогда и только тогда, когда постовская система соответствия

имеет решение.

Теорема 16.3.11.

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

узнать, является ли бесконечным множество .

Упражнение 16.3.12.

Рассмотрим язык, порождаемый грамматикой

Содержит ли этот язык все слова из {a,b}*?

Упражнение 16.3.13.

Рассмотрим язык, порождаемый грамматикой

{a,b}*?

Пересечение контекстно-свободных языков

Определение 16.1.1.

Рассмотрим алфавит . Пусть , где

для всех i. Обозначим через

линейную грамматику , где

Обозначим через

язык, порождаемый грамматикой .

Лемма 16.1.2.

Язык

является непустым тогда и только тогда, когда постовская система соответствия

имеет решение.

Пример 16.1.3.

Рассмотрим постовскую систему соответствия

(то есть n = 2,

и ). Решениями этой системы являются последовательности (1, 1, 2), (1, 1, 2, 1, 1, 2) и т. д. Легко убедиться, что

Теорема 16.1.4.

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

над алфавитом

узнать, верно ли, что .

Доказательство. Сначала докажем утверждение теоремы для случая . Из леммы 16.1.2 следует, что если бы проблема распознавания свойства

для контекстно-свободных грамматик над алфавитом

была разрешима, то проблема соответствий Поста тоже была бы разрешима. Поэтому из неразрешимости проблемы соответствий Поста следует неразрешимость проблемы распознавания свойства

для контекстно-свободных грамматик над алфавитом .

Чтобы доказать утверждение теоремы для случая

(например, ), достаточно заменить в определении

символ a на ede, символ b на edde и символ c на eddde.

Лемма 16.1.5.

Язык

является бесконечным тогда и только тогда, когда постовская система соответствия

имеет решение.

Доказательство. Если постовская система соответствия имеет хотя бы одно решение, то она имеет бесконечно много решений.

Теорема 16.1.6.

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

над алфавитом

узнать, является ли бесконечным язык .

Упражнение 16.1.7.

Пусть . Рассмотрим язык L1, порождаемый грамматикой

и язык L2, порождаемый грамматикой

Верно ли, что ?

Упражнение 16.1.8.

Пусть . Рассмотрим язык L1, порождаемый грамматикой

и язык , порождаемый грамматикой

Верно ли, что ?

Упражнение 16.1.9.

Пусть . Рассмотрим язык L1, порождаемый грамматикой

и язык L2, порождаемый грамматикой

Верно ли, что ?

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

Лемма 16.4.1.

Пусть , , где ,

и

для всех i. Тогда язык

является автоматным в том и только том случае, когда постовская система соответствия

не имеет решений.

Доказательство Пусть - решение постовской системы соответствия , где

для всех i. Положим

Легко проверить, что ,

и язык L0

является автоматным. Очевидно, что

Как было установлено в упражнении 3.4.2, язык

не является автоматным. Согласно теореме 3.2.1 язык

не является автоматным. Следовательно, и язык не является автоматным.

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

не имеет решений, то , а этот язык является автоматным.

Теорема 16.4.2.

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

узнать, является ли автоматным язык L(G).

Доказательство Докажем утверждение теоремы для случая . Из леммы 16.4.1 следует, что если бы проблема распознавания автоматности языка L(G) для контекстно-свободных грамматик над алфавитом

была разрешима, то также была бы разрешима проблема соответствий Поста для постовских систем соответствия , где ,

и

для всех i. Но тогда была бы разрешима проблема соответствий Поста для всех постовских систем соответствия над алфавитом {a,b} (если

для некоторого i, то рассматриваемая постовская система соответствия имеет решение, а именно (i)).

Упражнение 16.4.3.

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

Упражнение 16.4.4.

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

Упражнение 16.4.5.

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

Упражнение 16.4.6.

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

Проблема однозначности

Теорема 16.2.1.

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

узнать, является ли грамматика G однозначной.

Доказательство. Рассмотрим язык . Следуя доказательству теоремы 9.4.3, построим грамматику G для этого языка, исходя из грамматик и .

Грамматика G является неоднозначной тогда и только тогда, когда постовская система соответствия

имеет решение.

Упражнение 16.2.2.

Однозначна ли контекстно-свободная грамматика

Проблемы контекстной свободности

Определение 16.5.1.

Пусть , , , где

и

для всех i. Обозначим через

язык .

Лемма 16.5.2.

Язык

является контекстно-свободным при любых и .

Доказательство Утверждение следует из теорем 9.4.4 и 9.4.2.

Лемма 16.5.3. Рассмотрим алфавит . Пусть

и , где ,

и

для всех i. Тогда язык

является контекстно-свободным в том и только том случае, когда постовская система соответствия

не имеет решений.

Доказательство. Пусть - решение постовской системы соответствия , где

для всех i. Положим

Легко проверить, что ,

и язык L0

является автоматным. Очевидно, что

Можно доказать (например, используя лемму 9.1.1), что язык

не является контекстно-свободным. Согласно теореме 9.6.1 язык

также не~является контекстно-свободным.

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

не имеет решений, то .

Теорема 16.5.4.

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

над алфавитом

узнать, является ли контекстно-свободным язык .

Доказательство. Достаточно построить по постовской системе соответствия , где ,

и для всех i выполняется ,

и , контекстно-свободную грамматику G1, порождающую язык , и контекстно-свободную грамматику G2, порождающую язык . С учетом леммы 16.5.3 неразрешимость рассматриваемой задачи сводится к неразрешимости проблемы соответствий Поста рассуждением, аналогичным приведенному в доказательстве теоремы 16.4.2.

Лемма 16.5.5.

Рассмотрим алфавит . Язык

является контекстно-свободным при любых и .

Доказательство. Положим . Язык

можно представить в виде объединения пяти контекстно-свободных языков

Теорема 16.5.6.

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

узнать, является ли контекстно-свободным язык .

Доказательство. Рассмотрим алфавит . Достаточно построить по постовской системе соответствия , где ,

и для всех i выполняется ,

и , контекстно-свободную грамматику G, порождающую язык . С учетом леммы 16.5.5 неразрешимость рассматриваемой задачи сводится к~неразрешимости проблемы соответствий Поста рассуждением, аналогичным приведенному в доказательстве теоремы 16.4.2.

Лемма 16.5.7.

Рассмотрим алфавит . Язык

является контекстным при любых и .

Теорема 16.5.8.

Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстной грамматике G над алфавитом

узнать, является ли контекстно-свободным язык L(G).

Доказательство. Достаточно построить по постовской системе соответствия , где ,

и для всех i выполняется ,

и , контекстную грамматику G, порождающую язык .

Упражнение 16.5.9.

Является ли контекстно-свободным язык , где язык L порождается грамматикой

---

---