Теория формальных языков

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М. В. ЛОМОНОСОВА

Механико-математический факультет

Филологический факультет

А. Е. Пентус, М. Р. Пентус

Теория формальных языков

Учебное пособие

Москва 2004

УДК 519.713

ББК 28.25

П25

Рецензенты:
Доктор физико-математических наук В. А. Успенский,
Кандидат физико-математических наук В. Н. Крупский
Печатается по постановлению
Редакционно-издательского совета
филологического факультета МГУ
Пентус А. Е., Пентус М. Р.
П25 Теория формальных языков: Учебное пособие. —
М.: Изд-во ЦПИ при механико-математическом ф-те
МГУ, 2004. — 80 с.
Учебное пособие посвящено классическому разде-
лу математической лингвистикой и теоретической ин-
форматики — теории формальных языков. Рассмат-
риваются порождающие грамматики, классификация
формальных языков по Хомскому, регулярные вы-
ражения, конечные автоматы, автоматы с магазин-
ной памятью, алгоритмические проблемы, связанные
с контекстно-свободными грамматиками.
Для студентов, аспирантов и специалистов, зани-
мающихся математической лингвистикой или теоре-
тической информатикой.
УДК 519.713
ББК 28.25
c А. Е. Пентус, М. Р. Пентус, 2003
Введение
Учебное пособие содержит основные определения и теоремы
курса по теории порождающих грамматик и формальных языков,
рассчитанного на 16 теоретических занятий по два академиче-
ских часа. Материал тщательно структурирован. Факультатив-
ные разделы и пункты помечены звёздочками.
В пособии приведены главнымоб разомтео ретические резуль-
таты. Развёрнутые доказательства, примеры и приложения мож-
но найти в других книгах, ссылки на которые имеются в каждом
разделе.
Многие определения и результаты пояснены простыми приме-
рами. Из примера, приведённого сразу после леммы или теоремы,
часто можно понять идею доказательства.
Изложение строго математическое, но в то же время исполь-
зуются только самые простые математические понятия. Пособие
можно рекомендовать студентам математических, лингвистиче-
ских и компьютерных специальностей.

1. Слова, языки и грамматики
1.1. Формальные языки
[Гин, с. 12–14], [АхоУль, 0.2], [Сал, 1.1], [Гла, 1.1], [ХопМотУль, 1.5], [ГорМол,
с. 347–349], [СокКушБад, с. 11–12], [LewPap2, 1.7], [Рей, с. 22–23], [КукБей,
с. 257–262], [АхоСетУль, 3.3]
Определение 1.1. Будемн азывать натуральными числами
неотрицательные целые числа. Множество всех натуральных
чисел {0, 1, 2, . . .} обозначается N.
Определение 1.2. Алфавитом называется конечное непустое
множество. Его элементы называются символами (буквами).
Определение 1.3. Словом (цепочкой, строкой) (string) в ал-
фавите Σ называется конечная последовательность элементов Σ.
Пример 1.4. Рассмотрим алфавит Σ = {a, b, c}. Тогда baaa
является словомв алфавите Σ.
3
Слова, языки и грамматики
Определение 1.5. Слово, не содержащее ни одного символа
(то есть последовательность длины 0), называется пустым
словом и обозначается ε.
Определение 1.6. Длина слова w, обозначаем ая |w|, есть
число символов в w, причёмк аждый символ считается столько
раз, сколько раз он встречается в w.
Пример 1.7. Очевидно, |baaa| = 4 и |ε| = 0.
Определение 1.8. Если x и y — слова в алфавите Σ, то слово
xy (результат приписывания слова y в конец слова x) называется
конкатенацией (катенацией, сцеплением) слов x и y. Иногда
конкатенацию слов x и y обозначают x · y.
Определение 1.9. Если x — слово и n ∈ N, то через xn
обозначается слово x · x · . . . · x
n раз
. По определению x0 ε (знак
читается “равно по определению”). Всюду далее показатели над
словами и символами, как правило, являются натуральными
числами.
Пример 1.10. По принятымс оглашениям, ba3 = baaa и
(ba)3 = bababa.
Определение 1.11. Множество всех слов в алфавите Σ
обозначается Σ∗.
Определение 1.12. Множество всех непустых слов в алфа-
вите Σ обозначается Σ+.
Пример 1.13. Если Σ = {a}, то Σ+ = {a, aa, aaa, aaaa, . . .}.
Определение 1.14. Говорят, что слово x — префикс (начало)
слова y (обозначение x y), если y = xu для некоторого слова u.
Пример 1.15. Очевидно, ε baa, b baa, ba baa и
baa baa.
Определение 1.16. Говорят, что слово x — суффикс (конец)
слова y (обозначение x y), если y = ux для некоторого слова u.
Определение 1.17. Говорят, что слово x — подслово (substring)
слова y, если y = uxv для некоторых слов u и v.
Определение 1.18. Через |w|a обозначается количество вхо-
ждений символа a в слово w.
Пример 1.19. Если Σ = {a, b, c}, то |baaa|a = 3, |baaa|b = 1 и
|baaa|c = 0.
4
Слова, языки и грамматики
Определение 1.20. Если L ⊆ Σ∗, то L называется языком
(или формальным языком) над алфавитом Σ.
Поскольку каждый язык является множеством, можно рас-
сматривать операции объединения, пересечения и разности язы-
ков, заданных над одними тем же алфавитом (обозначения
L1 ∪ L2, L1 ∩ L2, L1 − L2).
Пример 1.21. Множество {a, abb} является языкомн ад ал-
фавитом {a, b}.
Пример 1.22. Множество {akbal | k l} является языком
над алфавитом {a, b}.
Определение 1.23. Пусть L ⊆ Σ∗. Тогда язык Σ∗ − L
называется дополнением (complement) языка L относительно
алфавита Σ. Когда из контекста ясно, о какома лфавите идёт
речь, говорят просто, что язык Σ∗ − L является дополнением
языка L.
Определение 1.24. Пусть L1, L2 ⊆ Σ∗. Тогда L1 · L2
{xy | x ∈ L1, y ∈ L2}. Язык L1·L2 называется конкатенацией
языков L1 и L2.
Пример 1.25. Если L1 = {a, abb} и L2 = {bbc, c}, то L1 ·L2 =
= {ac, abbc, abbbbc}.
Определение 1.26. Пусть L ⊆ Σ∗. Тогда L0 {ε} и
Ln L · . . . · L
n раз
.
Пример 1.27. Если L = {akbal | 0 < k < l}, то L2 =
= {akbalbam | 0 < k < l − 1, m>1}.
Определение 1.28. Итерацией (Kleene closure) языка L
(обозначение L∗) называется язык

n∈N
Ln. Эта операция назы-
вается также звёздочкой Клини (Kleene star, star operation).
Пример 1.29. Если Σ = {a, b} и L = {aa, ab, ba, bb}, то L∗ =
= {w ∈ Σ∗ | |w| делится на 2}.
Определение 1.30. Обращением или зеркальным образом
(reversal) слова w (обозначается wR) называется слово, состав-
ленное из символов слова w в обратном порядке.
Пример 1.31. Если w = baaca, то wR = acaab.
Определение 1.32. Пусть L ⊆ Σ∗. Тогда LR {wR | w ∈ L}.
5
Слова, языки и грамматики
1.2. Гомоморфизмы
[Сал, с. 10], [Гин, с. 57], [АхоУль, 0.2.3], [ХопМотУль, 4.2.3, 4.2.4], [Гла, 1.1],
[КукБей, с. 259], [LewPap2, с. 85]
Определение 1.33. Пусть Σ1 и Σ2 — алфавиты. Если отоб-
ражение h: Σ∗
1
→ Σ∗
2 удовлетворяет условию h(x · y) = h(x) · h(y)
для всех слов x ∈ Σ∗
1 и y ∈ Σ∗
1, то отображение h называется
гомоморфизмом (морфизмом).
Замечание 1.34. Можно доказать, что если h — гомомор-
физм, то h(ε) = ε.
Пример 1.35. Пусть Σ1 = {a, b} и Σ2 = {c}. Тогда
отображение h: Σ∗
1
→ Σ∗
2, заданное равенством h(w) = c2|w|,
является гомоморфизмом.
Замечание 1.36. Каждый гомоморфизм однозначно опреде-
ляется своими значениями на однобуквенных словах.
Определение 1.37. Если h: Σ∗
1
→ Σ∗
2 — гомоморфизм и
L ⊆ Σ∗
1, то через h(L) обозначается язык {h(w) | w ∈ L}.
Пример 1.38. Пусть Σ = {a, b} и гомоморфизм h: Σ∗ → Σ∗
задан равенствами h(a) = abba и h(b) = ε. Тогда
h({baa, bb}) = {abbaabba, ε}.
Определение 1.39. Если h: Σ∗
1
→ Σ∗
2 — гом ом орфизм и
L ⊆ Σ∗
2, то через h−1(L) обозначается язык {w ∈ Σ∗
1
| h(w) ∈ L}.
Пример 1.40. Рассмотрим алфавит Σ = {a, b}. Пусть гом о-
морфизм h: Σ∗ → Σ∗ задан равенствами h(a) = ab и h(b) = abb.
Тогда h−1({ε, abbb, abbab, ababab}) = {ε, ba, aaa}.
1.3. Порождающие грамматики
[Гин, 1.1], [Сал, 2.1], [АхоУль, 2.1.2], [Гла, 1.2], [Лал, с. 159–161], [Бра, с. 32–36],
[ГлаМел, с. 34–48], [ГорМол, с. 354–355, 367–370], [СокКушБад, с. 12–13],
[ТраБар, 1.12], [LewPap2, 4.6], [Рей, с. 28–30], [КукБей, с. 264–268]
Определение 1.41. Порождающей грамматикой (грамма-
тикой типа 0) (generative grammar, rewrite grammar) называет-
ся четвёрка G N,Σ, P, S
, где N и Σ — конечные алфавиты,
N ∩Σ = ∅, P ⊂ (N ∪ Σ)+ × (N ∪ Σ)∗, P конечно и S ∈ N.
Здесь Σ — основной алфавит (терминальный алфавит), его
6
Слова, языки и грамматики
элементы называются терминальными символами или терми-
налами (terminal), N — вспомогательный алфавит (нетерми-
нальный алфавит), его элементы называются нетерминальны-
ми символами, нетерминалами или переменными (nonterminal,
variable), S — начальный символ (аксиома) (start symbol). Пары
(α, β) ∈ P называются правилами подстановки, просто прави-
лами или продукциями (rewriting rule, production) и записыва-
ются в виде α → β.
Пример 1.42. Пусть даны множества N = {S}, Σ = {a, b, c},
P = {S → acSbcS, cS → ε}. Тогда N,Σ, P, S
 является
порождающей грамматикой.
Замечание 1.43. Будемобоз начать элементы множества Σ
строчным и буквам и из начала латинского алфавита, а элементы
множества N — заглавными латинскими буквами. Обычно в
примерах мы будем задавать грамматику в виде списка правил,
подразумевая, что алфавит N составляют все заглавные буквы,
встречающиеся в правилах, а алфавит Σ — все строчные буквы,
встречающиеся в правилах. При этомп равила порождающей
грамматики записывают в таком порядке, что левая часть
первого правила есть начальный символ S.
Замечание 1.44. Для обозначения n правил с одинаковыми
левыми частями α → β1, . . . , α → βn часто используют
сокращённую запись α → β1 | . . . | βn.
Определение 1.45. Пусть дана грамматика G. Пишем φ ⇒
G
ψ,
если φ = ηαθ, ψ = ηβθ и (α → β) ∈ P для некоторых слов α, β,
η, θ в алфавите N ∪ Σ.
Замечание 1.46. Когда из контекста ясно, о какой грамма-
тике идёт речь, вместо ⇒
G
можно писать просто ⇒.
Пример 1.47. Пусть
G= {S}, {a, b, c}, {S→acSbcS, cS→ε}, S
.
Тогда cSacS ⇒
G
cSa.
Определение 1.48. Если ω0 ⇒
G
ω1 ⇒
G
. . . ⇒
G
ωn, где n 0,
то пишем ω0
∗⇒
G
ωn (другими словами, бинарное отношение
∗⇒
G
является рефлексивным, транзитивным замыканием бинарного
отношения ⇒
G
, определённого на множестве (N ∪ Σ)∗). При этом
7
Слова, языки и грамматики
последовательность слов ω0, ω1, . . . , ωn называется выводом
(derivation) слова ωn из слова ω0 в грам матике G. Число n
называется длиной (количеством шагов) этого вывода.
Замечание 1.49. В частности, для всякого слова ω ∈ (N∪Σ)∗
имеет место ω
∗⇒
G
ω (так как возможен вывод длины 0).
Пример 1.50. Пусть G = {S}, {a, b}, {S → aSa, S → b}, S
.
Тогда aSa
∗⇒
G
aaaaSaaaa. Длина этого вывода — 3.
Определение 1.51. Язык, порождаемый грамматикой G, —
это множество L(G) {ω ∈ Σ∗ | S
∗⇒
G
ω}. Будем также говорить,
что грамматика G порождаёт (generates) язык L(G).
Замечание 1.52. Существенно, что в определение порожда-
ющей грамматики включены два алфавита — Σ и N. Это позво-
лило намв определении 1.51 “отсеять” часть слов, получаемых
из начального символа. А именно, отбрасывается каждое слово,
содержащее хотя бы один символ, не принадлежащий алфави-
ту Σ.
Пример 1.53. Если G = {S}, {a, b}, {S → aSa, S → bb}, S
,
то L(G) = {anbban | n 0}.
Определение 1.54. Две грамматики эквивалентны, если
они порождают один и тот же язык.
Пример 1.55. Грамматика S → abS, S → a и грам матика
T → aU, U → baU, U → ε эквивалентны.
1.4. Классы грамматик
[Гин, с. 23–24, 78–79], [АхоУль, 2.1.3, с. 191], [Сал, 2.1, с. 94], [Гла, 1.2, 1.3],
[Бра, с. 39–45], [ГлаМел, с. 54, 63, 69–70], [ГорМол, с. 361–367], [ТраБар, 1.12],
[КукБей, с. 268–271], [ЛПИИ, 5.2.1]
Определение 1.56. Контекстной грамматикой (контекст-
но-зависимой грамматикой, грамматикой непосредственно
составляющих, НС-грамматикой, грамматикой типа 1) (context-
sensitive grammar, phrase-structure grammar) называется по-
рождающая грамматика, каждое правило которой имеет вид
ηAθ → ηαθ, где A ∈ N, η ∈ (N ∪Σ)∗, θ ∈ (N ∪Σ)∗, α ∈ (N ∪Σ)+.
8
Слова, языки и грамматики
Пример 1.57. Грамматика S → TS, S → US, S → b,
Tb → Ab, A → a, TA → AAT, UAb → b, UAAA → AAU
не является контекстной (последние три правила не имеют
требуемого вида).
Определение 1.58. Контекстно-свободной грамматикой
(КС-грамматикой, бесконтекстной грамматикой, граммати-
кой типа 2) (context-free grammar) называется порождающая
грамматика, каждое правило которой имеет вид A → α, где
A ∈ N, α ∈ (N ∪ Σ)∗.
Пример 1.59. Грамматика S → ASTA, S → AbA, A → a,
bT → bb, AT → UT, UT → UV , UV → TV , TV → TA является
контекстной, но не контекстно-свободной (последние пять правил
не имеют требуемого вида).
Определение 1.60. Линейной грамматикой (linear grammar)
называется порождающая грамматика, каждое правило ко-
торой имеет вид A → u или A → uBv, где A ∈ N, u ∈ Σ∗,
v ∈ Σ∗, B ∈ N.
Пример 1.61. Грамматика S → TT, T → cT T , T → bT ,
T → a является контекстно-свободной, но не линейной (первые
два правила не имеют требуемого вида).
Определение 1.62. Праволинейной грамматикой (рацио-
нальной грамматикой, грамматикой типа 3) (right-linear
grammar) называется порождающая грамматика, каждое прави-
ло которой имеет вид A → u или A → uB, где A ∈ N, u ∈ Σ∗,
B ∈ N.
Пример 1.63. Грамматика S → aSa, S → T , T → bT , T → ε
является линейной, но не праволинейной (первое правило не
имеет требуемого вида).
Пример 1.64. Грамматика S → T , U → abba праволинейная.
Пример 1.65. Грамматика S → aS, S → bS, S → aaaT ,
S → aabaT , S → abaaT , S → aabbaT , S → ababaT , S → abbaaT ,
T → aT , T → bT , T → ε праволинейная.
Пример 1.66. Грамматика S → ε, S → aaaS, S → abbS,
S → babS, S → aabT , T → abaT , T → baaT , T → bbbT ,
T → bbaS праволинейная. Обобщённый вариант языка, порож-
даемого этой грамматикой, используется в доказательстве разре-
шимости арифметики Пресбургера [Sip, с. 207–208].
9
Конечные автоматы
Определение 1.67. Правила вида α → ε называются ε-пра-
вилами.
Лемма 1.68. Каждая праволинейная грамматика является
линейной. Каждая линейная грамматика является контекст-
но-свободной. Каждая контекстно-свободная грамматика без
ε-правил является контекстной грамматикой.
Определение 1.69. Классы грамматик типа 0, 1, 2 и 3
образуют иерархию Хомского (Chomsky hierarchy).
Определение 1.70. Язык называется контекстным языком
(контекстно-свободным языком, линейным языком, праволи-
нейным языком), если он порождается некоторой контекстной
грамматикой (соответственно контекстно-свободной граммати-
кой, линейной грамматикой, праволинейной грамматикой). Кон-
текстно-свободные языки называются также алгебраическими
языками.
Пример 1.71. Пусть дан произвольный алфавит
Σ = {a1, . . . an}. Тогда язык Σ∗ является праволинейным, так
как он порождается грамматикой S → ε, S → a1S, . . . , S → anS.
2. Конечные автоматы
2.1. Недетерминированные
конечные автоматы
[Гин, 2.1], [Сал, 2.1], [АхоУль, 2.2.3], [ХопМотУль, 2.3], [Гла, 5.1], [Лал, с. 185],
[ГорМол, с. 391–392], [СокКушБад, с. 19–21], [ЛПИИ, 5.2.3], [Бра, с. 106–107],
[ГроЛан, 10.3.1], [ТраБар, 1.5], [LewPap2, 2.2], [Sip, 1.2], [Рей, с. 46–47],
[КукБей, с. 324–325], [АхоСетУль, 3.6]
Определение 2.1. Конечный автомат (finite automaton, finite-
state machine) — это пятёрка M = Q,Σ,Δ, I, F
, где
Σ — конечный алфавит, Q и Δ — конечные м ножества,
Δ ⊆ Q×Σ∗ ×Q, I ⊆ Q, F ⊆ Q. Элем енты Q называются состо-
яниями (state), элементы I — начальными (initial) состояниями,
элементы F — заключительными или допускающими (final, accepting)
состояниями. Если p, x, q
 ∈ Δ, то p, x, q
 называется
переходом (transition) из p в q, а слово x — меткой (label) этого
перехода.
10
Конечные автоматы
Пример 2.2. Пусть Q = {1, 2}, Σ = {a, b}, I = {2},
F = {2}, Δ = { 1, aaa, 1
, 1, ab, 2
, 1, b, 2
, 2, ε, 1
}. Тогда
Q,Σ,Δ, I, F
 — конечный автом ат.
Определение 2.3. Путь (path) конечного автомата — это
кортеж q0, e1, q1, e2, . . . , qn
, где n 0 и ei = qi−1, wi, qi
 ∈ Δ
для каждого i. При этом q0 — начало пути, qn — конец пути,
n — длина пути, w1 . . . wn — метка пути.
Замечание 2.4. Для любого состояния q ∈ Q существует
путь q
. Его м етка — ε, начало и конец совпадают.
Определение 2.5. Путь называется успешным, если его
начало принадлежит I, а конец принадлежит F.
Пример 2.6. Рассмотрим конечный автомат из примера 2.2.
Путь 2, 2, ε, 1
, 1, 1, aaa, 1
, 1, 1, b, 2
, 2
 является успеш-
ным. Его метка — aaab. Длина этого пути — 3.
Определение 2.7. Слово w допускается (is accepted, is
recognized) конечнымавт оматом M, если оно является меткой
некоторого успешного пути.
Определение 2.8. Язык, распознаваемый конечным авто-
матом M, — это язык L(M), состоящий из меток всех успешных
путей (то есть из всех допускаемых данныма втоматомс лов). Бу-
демта кже говорить, что автомат M распознаёт (accepts) язык
L(M).
Замечание 2.9. Если I ∩ F = ∅, то язык, распознаваем ый
конечнымавт оматом Q,Σ,Δ, I, F
, содержит ε.
Пример 2.10. Пусть M = Q,Σ,Δ, I, F
, где Q = {1, 2},
Σ = {a, b}, Δ = { 1, a, 2
, 2, b, 1
}, I = {1} и F = {1, 2}. Тогда
L(M) = {(ab)n | n 0} ∪ {(ab)na | n 0}.
Определение 2.11. Два конечных автомата эквивалентны,
если они распознают один и тот же язык.
Определение 2.12. Язык L называется автоматным (finite-
state language), если существует конечный автомат, распо-
знающий этот язык.
Замечание 2.13. Обычно в учебниках используется более
узкое определение недетерминированного конечного автомата, но
это не меняет класса автоматных языков (см. лемму 2.30).
Пример 2.14. Рассмотрим однобуквенный алфавит Σ = {a}.
При любых фиксированных k ∈ N и m ∈ N язык {ak+mn | n ∈ N}
является автоматным.
11
Конечные автоматы
Замечание 2.15. Каждый конечный язык является автомат-
ным.
Определение 2.16. Состояние q достижимо (reachable) из
состояния p, если существует путь, началомк оторого является p,
а концом — q.
Лемма 2.17. Каждый автоматный язык распознаётся
некоторым конечным автоматом, в котором каждое состо-
яние достижимо из некоторого начального состояния и из
каждого состояния достижимо хотя бы одно заключитель-
ное состояние.
Пример 2.18. Рассмотрим конечный автомат Q,Σ,Δ, I, F
,
где Q = {1, 2, 3, 4}, Σ = {a, b, c, d}, I = {1, 2, 4}, F = {1, 3, 4},
Δ = { 1, a, 2
, 1, b, 4
, 3, c, 4
, 4, d, 1
}. Удалимте состояния
(и содержащие их переходы), которые не удовлетворяют требо-
ваниям леммы 2.17. Получается эквивалентный конечный авто-
мат Q ,Σ,Δ , I , F
, где Q = {1, 4}, Δ = { 1, b, 4
, 4, d, 1
},
I = {1, 4} и F = {1, 4}.
Замечание 2.19. Естественнымобоб щением конечного ав-
томата является конечный преобразователь (finite-state transducer),
позволяющий на каждомта кте отправить несколько
символов в дополнительный “выходной” поток (см. [Гин, 3.3],
[АхоУль, 3.1.3] или [ТраБар, 0.1, 2.1–2.6]). В некоторых кни-
гах конечными автоматами называют именно такие устройства
(с выходнымп отоком).
В данномпо собии конечные преобразователи рассматривать-
ся не будут.
2.2*. Конфигурации конечного автомата
[АхоУль, 2.2.3], [ГорМол, с. 391], [СокКушБад, с. 20], [LewPap2, 2.2]
Определение 2.20. Конфигурацией конечного автомата на-
зывается любая упорядоченная пара q,w
, где q ∈ Q и
w ∈ Σ∗.
Замечание 2.21. Содержательно конфигурация представ-
ляет собой “мгновенное описание” конечного автомата. Ес-
ли представить, что исходное слово, принадлежность кото-
рого рассматриваемому языку надо проверить, дано в неко-
тором“ входном потоке”, то в конфигурации q,w
 сло-
12
Конечные автоматы
во w есть та часть исходного слова, которая пока оста-
лась во входномп отоке (это некоторый суффикс исходно-
го слова), а q — текущее состояние “управляющего устрой-
ства”.
Определение 2.22. Определимна множестве всех конфигу-
раций конечного автомата M бинарное отношение (такт ра-
боты (step)) следующимоб разом. Если p, x, q
 ∈ Δ и w ∈ Σ∗,
то p, xw
  q,w
. Иногда вм есто пишут
Δ
.
Пример 2.23. Рассмотрим конечный автомат из примера 2.2.
Тогда 1, abba
  2, ba
.
Определение 2.24. Бинарное отношение
∗
определяется как
рефлексивное, транзитивное замыкание отношения .
Пример 2.25. Для конечного автомата из примера 2.2
выполняется 1, aaaab
 ∗ 1, aaaab
 и 1, aaaab
 ∗ 2, ε
.
Лемма 2.26. Пусть дан конечный автомат M =
= Q,Σ,Δ, I, F
. Слово w ∈ Σ∗ принадлежит языку L(M) то-
гда и только тогда, когда для некоторых p ∈ I и q ∈ F верно
p,w
 ∗ q, ε
.
Лемма 2.27. Если q1, x
 ∗ q2, ε
 и q2, y
 ∗ q3, ε
, то
q1, xy
 ∗ q3, ε
.
2.3. Конечные автоматы
с однобуквенными переходами
[ХопМотУль, 2.5], [Рей, с. 51–53]
Лемма 2.28. Каждый автоматный язык распознаётся
некоторым конечным автоматом, не содержащим переходов
с метками длины больше единицы и имеющим ровно одно
начальное состояние и ровно одно заключительное состояние.
Пример 2.29. Рассмотримя зык, заданный конечныма в-
томатом Q,Σ,Δ, I, F
, где Q = {1, 2}, Σ = {a, b, c, d},
Δ = { 1, ab, 2
, 2, cd, 1
}, I = {1, 2}, F = {1, 2}. Тот
же язык распознаётся конечнымав томатом Q ,Σ,Δ , I , F
,
где Q = {0, 1, 2, 3, 4, 5}, I = {0}, F = {5}, Δ =
= { 1,a,3
, 3,b,2
, 2,c,4
, 4,d,1
, 0,ε,1
, 0,ε,2
, 1,ε,5
, 2,ε,5
}.
Здесь первые два перехода заменяют старый переход 1, ab, 2
 и
13
Конечные автоматы
следующие два перехода заменяют старый переход 2, cd, 1
. Что-
бы обеспечить единственность начального состояния, добавлены
переходы 0, ε, 1
 и 0, ε, 2
. Последние два перехода в Δ обес-
печивают единственность заключительного состояния.
Лемма 2.30. Каждый автоматный язык распознаётся
некоторым конечным автоматом, содержащим только пере-
ходы с метками длины единица и имеющим ровно одно на-
чальное состояние.
Доказательство. Согласно лемме 2.28 можно предположить,
что исходный язык задан конечнымавт оматом Q,Σ,Δ, I, F
,
не содержащимп ереходов с метками длины больше едини-
цы, причём |I| = 1. Построими скомый конечный автомат
Q ,Σ,Δ , I , F
, положив Q = Q, I = I,
Δ ={ p, a, r
 | a∈Σ и найдётся такое q∈Q, что q, a, r
∈Δ
и существует путь из p в q с м еткой ε},
F
= {p ∈ Q | найдётся такое q ∈ F,
что существует путь из p в q с м еткой ε}.
2.4. Характеризация праволинейных языков
[Гин, 2.2], [Сал, 2.1], [ХопМотУль, с. 196], [Гла, 5.1], [Лал, с. 186–187], [ЛПИИ,
5.2.3, 5.2.4], [АхоУль, 2.2.4], [ГорМол, с. 408–413], [Бра, с. 107–108], [ГроЛан,
10.2.4], [LewPap1, 3.2], [Рей, с. 48–50], [КукБей, с. 340–342], [АхоСетУль, с. 180]
Теорема 2.31. Каждый автоматный язык является право-
линейным.
Доказательство. Без ограничения общности можно пред-
положить, что исходный язык задан конечныма втоматом
Q,Σ,Δ, I, F
, где Q ∩ Σ = ∅ и I = {q0}. Положим N = Q,
S = q0 и P = {p → xq | p, x, q
 ∈ Δ} ∪ {p → ε | p ∈ F}.
Пример 2.32. Язык, распознаваемый конечным автоматом из
примера 2.2, порождается грамматикой K2 → K1, K1 → aaaK1,
K1 → abK2, K1 → bK2, K2 → ε.
Теорема 2.33. Каждый праволинейный язык является ав-
томатным.
14
Конечные автоматы
Доказательство. Без ограничения общности можно пред-
положить, что исходный язык задан праволинейной граммати-
кой, не содержащей правил вида A → u, где u ∈ Σ+. Поло-
жим Q = N, I = {S}, F = {A ∈ N | (A → ε) ∈ P} и
Δ = { A, u,B
 | (A → uB) ∈ P}.
Пример 2.34. Пусть Σ = {a, b}. Язык, порождаемый грамма-
тикой S → aa, S → T , T → baT , T → a, распознаётся конечным
автоматом Q,Σ,Δ, I, F
, где Q = {S, T,E}, I = {S}, F = {E} и
Δ = { S, aa,E
, S, ε, T
, T, ba,T
, T, a,E
}.
2.5*. Нормальная форма
праволинейных грамматик
[АхоУль, с. 145], [ГорМол, с. 387–390], [Бра, с. 77–78]
Определение 2.35. Праволинейная грамматика в нормаль-
ной форме (автоматная грамматика, регулярная граммати-
ка) (finite-state grammar) — это праволинейная грамматика, в ко-
торой каждое правило имеет вид A → ε, A → a или A → aB, где
A ∈ N, B ∈ N, a ∈ Σ.
Теорема 2.36. Каждая праволинейная грамматика эквива-
лентна некоторой праволинейной грамматике в нормальной
форме.
Теорема 2.37. Если праволинейный язык не содержит
пустого слова, то он порождается некоторой праволинейной
грамматикой в нормальной форме без ε-правил.
2.6. Детерминированные конечные автоматы
[Гин, 2.1], [Сал, 2.2], [АхоУль, 2.2.3], [ХопМотУль, 2.2], [Гла, 5.1], [ГорМол,
с. 392–395], [СокКушБад, с. 21], [Лал, с. 174–178, 185], [Бра, с. 101–102],
[ГроЛан, 10.2], [ТраБар, 0.1, 0.2, 1.7], [LewPap2, 2.1], [Sip, 1.1, 1.2], [Рей,
с. 44–48], [КукБей, с. 320–327], [АхоСетУль, 3.6]
Определение 2.38. Конечный автомат Q,Σ,Δ, I, F
 назы-
вается детерминированным (deterministic), если
1) множество I содержит ровно один элемент,
2) для каждого перехода p, x, q
 ∈ Δ выполняется равенство
|x| = 1,
15
Конечные автоматы
3) для любого символа a ∈ Σ и для любого состояния p ∈ Q
существует не более одного состояния q ∈ Q со свойством
p, a, q
 ∈ Δ.
Пример 2.39. Конечный автомат из примера 2.10 является
детерминированным.
Определение 2.40. Детерминированный конечный автомат
Q,Σ,Δ, I, F
 называется полным (complete), если для каждого
состояния p ∈ Q и для каждого символа a ∈ Σ найдётся такое
состояние q ∈ Q, что p, a, q
 ∈ Δ.
Пример 2.41. Конечный автомат из примера 2.10 эк-
вивалентен полному детерминированному конечному автома-
ту Q,Σ,Δ, I, F
, где Q = {1, 2, 3}, Σ = {a, b}, Δ =
= { 1, a, 2
, 1, b, 3
, 2, a, 3
, 2, b, 1
, 3, a, 3
, 3, b, 3
}, I = {1},
F = {1, 2}.
Замечание 2.42. Некоторые авторы используют в определе-
нии полного детерминированного конечного автомата вместо от-
ношения Δ функцию δ : Q×Σ → Q. От функции δ можно перейти
к отношению Δ, положив Δ = { p, a, δ(p, a)
 | p ∈ Q, a ∈ Σ}.
Теорема 2.43. Каждый автоматный язык распознаётся
некоторым полным детерминированным конечным автома-
том.
Доказательство. Без ограничения общности можно пред-
положить, что исходный язык задан конечныма втоматом
Q,Σ,Δ, I, F
, содержащимт олько переходы с метками дли-
ны единица. Для любых a ∈ Σ и H ⊆ Q обозначим
Δa(H) {q ∈ Q | p, a, q
 ∈ Δ для некоторого p ∈ H}.
Обозначимч ерез P(Q) множество всех подмножеств мно-
жества Q. Построим искомый полный детерминированный
конечный автомат Q ,Σ,Δ , I , F
, положив Q = P(Q),
Δ = { H, a,Δa(H)
 | H ⊆ Q, a ∈ Σ}, I = {I} и
F = {H ⊆ Q | H ∩ F = ∅}.
Пример 2.44. Пусть Σ = {a, b}. Рассмотрим ко-
нечный автомат M = {1, 2, 3},Σ,Δ, {1}, {3}
, где
Δ = { 1, a, 1
, 1, b, 1
, 1, a, 2
, 2, b, 3
}. Если применить кон-
струкцию из доказательства теоремы 2.43 и потом удалить
16
Основные свойства автоматных языков
состояния, не достижимые из начального состояния, то по-
лучится полный детерминированный конечный автомат M =
= {{1}, {1, 2}, {1, 3}},Σ,Δ , {{1}}, {{1, 3}}
, где
Δ = { {1}, a, {1, 2}
, {1}, b, {1}
, {1, 2}, a, {1, 2}
,
{1, 2}, b, {1, 3}
, {1, 3}, a, {1, 2}
, {1, 3}, b, {1}
}.
Определение 2.45. Для любого состояния p полного детер-
минированного конечного автомата Q,Σ,Δ, I, F
 и любого сло-
ва w обозначимч ерез Δw(p) такое состояние q, что существует
путь из p в q с м еткой w (в силу полноты и детерминированности
такое состояние существует и единственно).
3. Основные свойства
автоматных языков
3.1. Свойства замкнутости
класса автоматных языков
[Гин, 2.1], [Сал, 2.3, с. 58], [ХопМотУль, 3.2.3, 4.2.2, 4.2.5], [АхоУль, 2.3.3], [Гла,
5.2], [ГроЛан, 10.4.1, 10.4.3], [ТраБар, 1.1, 1.6], [LewPap2, 2.3], [Sip, 1.2], [Рей,
с. 40–43], [КукБей, с. 327–330], [АхоСетУль, 3.7], [ГорМол, с. 413]
Теорема 3.1. Класс автоматных языков замкнут относи-
тельно итерации, конкатенации и объединения.
Доказательство. Без ограничения общности можно предпо-
ложить, что каждый из исходных языков задан конечнымав то-
матомс одним начальным и однимзаключитель ным состоянием.
Тогда во всех трёх случаях результирующий автомат получается
из исходных путёмд обавления нескольких ε-переходов и состо-
яний и назначения новых начальных и заключительных состоя-
ний.
Пример 3.2. Пусть M1 = {1, 2, 3},Σ,Δ1, {1}, {2}
, где
Σ = {a, b, c} и Δ1 = { 1, a, 2
, 2, b, 3
, 3, c, 1
}. То-
гда язык L(M1)∗ распознаётся конечнымав томатом M2 =
= {1, 2, 3, 4},Σ,Δ1 ∪ { 4, ε, 1
, 2, ε, 4
}, {4}, {4}
.
17
Основные свойства автоматных языков
Пример 3.3. Пусть Σ = {a, b, c}. Рассмотрим конечный
автомат M1 из примера 3.2 и конечный автомат M2 =
= {4, 5},Σ,Δ2, {4}, {5}
, где Δ2 = { 4, c, 4
, 4, a, 5
, 5, c, 5
}.
Тогда язык L(M1) · L(M2) распознаётся конечнымав тома-
том M3 = {1, 2, 3, 4, 5},Σ,Δ1 ∪ Δ2 ∪ { 2, ε, 4
}, {1}, {5}
, а язык
L(M1) ∪ L(M2) распознаётся конечнымав томатом M4 =
= {1, 2, 3, 4, 5},Σ,Δ1 ∪ Δ2, {1, 4}, {2, 5}
.
Упражнение 3.4. Существует ли такой автоматный язык L,
что язык LR не является автоматным?
Ответ. Нет. Пусть язык L распознаётся конечнымав томатом
Q,Σ,Δ, I, F
. Положим ΔR = { q, xR, p
 | p, x, q
 ∈ Δ}. Тогда
язык LR распознаётся конечнымав томатом Q,Σ,ΔR, F, I
.
Упражнение 3.5. Существует ли такой автом атный язык
L ⊆ Σ∗, что язык
Pref(L) {w | w — префикс некоторого слова из L}
не является автоматным?
Ответ. Нет. Пусть язык L распознаётся конечнымав томатом
Q,Σ,Δ, I, F
, причём
1) в Δ нет переходов с метками длины больше единицы и
2) из каждого состояния достижимо некоторое заключитель-
ное состояние.
Легко проверить, что язык Pref(L) распознаётся конечным
автоматом Q,Σ,Δ, I,Q
.
Упражнение 3.6. Существует ли такой автом атный язык
L ⊆ Σ∗, что язык
Suf(L) {w | w — суффикс некоторого слова из L}
не является автоматным?
Ответ. Нет. Suf(L) = Pref(LR)R.
Упражнение 3.7. Существует ли такой автоматный язык
L ⊆ Σ∗, что язык
Subw(L) {w | w — подслово некоторого слова из L}
не является автоматным?
Ответ. Нет. Subw(L) = Suf(Pref(L)).
18
Основные свойства автоматных языков
3.2. Пересечение и дополнение
автоматных языков
[Гин, 2.1], [ХопМотУль, 4.2.1], [АхоУль, 2.3.3], [Сал, 2.2], [Гла, 5.2], [ГроЛан,
10.4.2], [ТраБар, 1.1, 1.6], [LewPap2, 2.3], [Рей, с. 50–51], [КукБей, с. 329],
[ГорМол, с. 413]
Теорема 3.8. Класс автоматных языков замкнут относи-
тельно дополнения и пересечения.
Доказательство. Если язык L распознаётся полнымд е-
терминированным конечным автоматом Q,Σ,Δ, I, F
, то язык
Σ∗ − L распознаётся конечнымав томатом Q,Σ,Δ, I,Q − F
.
Пересечение выражается через объединение и дополнение
(закон де Моргана).
Замечание 3.9. Автоматность пересечения двух авто-
матных языков можно легко доказать и без привлече-
ния теоремы 2.43. Для этого достаточно построить по
двумк онечным автоматамс однобуквенными переходами
M1 = Q1,Σ,Δ1, I1, F1
 и M2 = Q2,Σ,Δ2, I2, F2
 новый конеч-
ный автомат M = Q1 × Q2,Σ,Δ, I1 × I2, F1 × F2
, где Δ =
= { p1, p2
, a, q1, q2

 | p1, a, q1
 ∈ Δ1, p2, a, q2
 ∈ Δ2}.
3.3. Лемма о разрастании
для автоматных языков
[АхоУль, 2.3.2], [ХопМотУль, 4.1], [ГорМол, с. 414–415], [LewPap2, 2.4], [Sip,
1.4], [Сал, с. 37], [Рей, с. 62]
Лемма 3.10 (pumping lemma, лемма о разрастании, лемма
о накачке, лемма-насос). Пусть L — автоматный язык над
алфавитом Σ. Тогда найдётся такое положительное целое
число p, что для любого слова w ∈ L длины не меньше p
найдутся слова x, y, z ∈ Σ∗, для которых верно xyz = w, y = ε,
|xy| p и xyiz ∈ L для всех i 0.
Доказательство. Пусть язык L распознаётся автоматом
Q,Σ,Δ, I, F
, содержащимт олько переходы с метками дли-
ны единица. Положим p = |Q|. Пусть слово w является мет-
кой успешного пути q0, e1, q1, e2, . . . , qn
 и |w| = n p. Со-
гласно принципу Дирихле найдутся такие индексы j и k, что
19
Основные свойства автоматных языков
0 j < k p и qj = qk. Выберемсл ова x, y и z так, что |x| = j,
|y| = k − j и xyz = w.
Пример 3.11. Пусть Σ = {a, b}. Рассмотрим автоматный язык
L = {(ab)n | n 0} ∪ {a(ab)n | n 0}. Положим p = 3.
Тогда для любого слова w ∈ L длины не меньше p найдутся
слова x, y, z ∈ Σ∗, соответствующие утверждению леммы 3.10.
Действительно, если w = abu для некоторого слова u, то
положим x = ε, y = ab, z = u; иначе w = aabu и м ожно положить
x = a, y = ab, z = u.
3.4. Примеры неавтоматных языков
[АхоУль, 2.3.2], [ХопМотУль, 4.1], [ГорМол, с. 415], [LewPap2, 2.4]
Пример 3.12. Рассмотрим язык L = {abnan | n 0} над
алфавитом Σ = {a, b}. Утверждение леммы 3.10 не выполняется
ни для какого натурального числа p. Действительно, если
w = abpap, то x = abk, y = bm, z = bp−k−map для некоторых
k 0 и m 1 или x = ε, y = abl, z = bp−lap для некоторого
l 0. В обоих случаях xyyz /∈
L. Таким образом, язык L не
является автоматным.
Упражнение 3.13. Пусть Σ = {a, b, c}. При каких словах
u ∈ {a, b}∗ и v ∈ {a, b}∗ язык {umcvm | m > 0} является
автоматным?
Ответ. Этот язык является автоматным тогда и только тогда,
когда u = ε или v = ε.
Замечание 3.14. Условие, сформулированное в лемме 3.10,
является необходимым для автоматности, но не достаточным.
Пример 3.15. Пусть Σ = {a, b}. Рассмотрим язык L =
= {akbman | k = 0 или m = n}. Положим p = 1. То-
гда для любого слова w ∈ L длины не меньше p найдут-
ся слова x, y, z ∈ Σ∗, соответствующие утверждению лем-
м ы 3.10. Тем не менее язык L не является автоматным, так как
L ∩ {abman | m 0, n 0} = {abnan | n 0}.
20
Дополнительные свойства автоматных языков
4. Дополнительные свойства
автоматных языков
4.1. Гомоморфизмы и автоматные языки
[АхоУль, с. 161], [ХопМотУль, 4.2.3, 4.2.4], [LewPap2, с. 85–86]
Теорема 4.1. Для любого гомоморфизма h: Σ∗
1
→ Σ∗
2 и
автоматного языка L ⊆ Σ∗
1 язык h(L) является автоматным.
Доказательство. Пусть исходный язык L задан конеч-
нымавт оматом M = Q,Σ1,Δ, I, F
. Положим Δ =
= { p, h(x), q
 | p, x, q
 ∈ Δ}. Тогда язык h(L) распознаётся
конечнымавт оматом Q,Σ2,Δ , I, F
.
Теорема 4.2. Для любого гомоморфизма h: Σ∗
1
→ Σ∗
2 и ав-
томатного языка L ⊆ Σ∗
2 язык h−1(L) является автоматным.
Доказательство. Без ограничения общности можно пред-
положить, что исходный язык L задан конечныма втома-
том M = Q,Σ2,Δ, I, F
, где Δ не содержит перехо-
дов с метками длины больше единицы. Положим Δ =
= { p, a, q
 | a ∈ Σ1 и существует путь из p в q с м еткой h(a)}.
Тогда язык h−1(L) распознаётся конечнымав томатом M =
= Q,Σ1,Δ , I, F
.
4.2*. Длины слов в автоматных языках
[Гин, 2.1], [АхоУль, с. 147], [Сал, с. 40]
Определение 4.3. Пусть A ⊆ N, m ∈ N и m > 0.
Множество A называется заключительно периодическим (ultimately
periodic) с периодом m, если выполнено условие
(∃n0 ∈ N) (∀n n0) (n ∈ A↔n + m ∈ A).
Лемма 4.4. Пусть A ⊆ N. Тогда равносильны следующие
утверждения:
1) множество A является заключительно периодическим;
2) найдутся положительное целое число m и конечные
множества M ⊆ N и K ⊆ {0, 1, . . .,m − 1}, такие что
A = {k ∈ N | (k mod m) ∈ K}−M;
3) множество A является объединением конечного семей-
ства арифметических прогрессий.
21
Дополнительные свойства автоматных языков
Теорема 4.5. Язык L над однобуквенным алфавитом
{a} является автоматным тогда и только тогда, когда
множество {k ∈ N | ak ∈ L} является заключительно
периодическим.
Доказательство. Для доказательства необходимости доста-
точно рассмотреть детерминированный конечный автомат, рас-
познающий язык L.
Теорема 4.6. Если язык L является автоматным, то мно-
жество {|w| | w ∈ L} является заключительно периодическим.
Доказательство. Рассмотрим конечный автомат, распознаю-
щий язык L. Заменим все символы в метках переходов на сим-
вол a. Осталось применить теорему 4.5 к полученному автомат-
ному языку над однобуквенным алфавитом {a}.
Упражнение 4.7. Существует ли такой автоматный язык L
над алфавитом {a}, что язык {an | an2 ∈ L} не является
автоматным?
Ответ. Нет. Пусть L — автоматный язык. Согласно теоре-
ме 4.5 найдутся положительное целое число m и конечные
множества M ⊆ N и K ⊆ {0, 1, . . .,m − 1}, такие что
{k ∈ N | ak ∈ L} = {k ∈ N | (k mod m) ∈ K} −M.
Положим M = {n ∈ N | n2 ∈ M} и K =
= {n ∈ N | n < m, (n2 mod m) ∈ K}. Тогда {n ∈ N | an2 ∈ L} =
= {n ∈ N | (n mod m) ∈ K }−M .
Упражнение 4.8. Существует ли такой автоматный язык L
над алфавитом {a}, что язык {an | a2n ∈ L} не является
автоматным?
Ответ. Нет. Пусть L — автоматный язык. Согласно теоре-
ме 4.5 найдутся положительное целое число m и конечные
множества M ⊆ N и K ⊆ {0, 1, . . .,m − 1}, такие что
{k ∈ N | ak ∈ L} = {k ∈ N | (k mod m) ∈ K}−M. Оста-
лось проверить, что язык {an | (2n mod m) ∈ K} распознаётся
конечнымавт оматом Q, {a},Δ, I, F
, где Q = {0, 1, . . .,m − 1},
Δ = { k, a, (2k mod m)
 | k ∈ Q}, I = {20 mod m} и F = K.
Упражнение 4.9. Существует ли такой автоматный язык L1
над алфавитом Σ, что язык
L2 = {w ∈ Σ∗ | wx ∈ L1, |x| = 2|w| для некоторого слова x∈Σ∗}
не является автоматным?
22
Регулярные выражения
Ответ. Нет. Пусть язык L1 распознаётся конечнымав тома-
том Q,Σ,Δ, I, F
, не содержащим переходов с метками дли-
ны больше единицы. Обозначим Mq = Q,Σ,Δ, I, {q}
 и
M
q = Q,Σ,Δ, {q}, F
. Тогда
L2 =

q∈Q
(L(Mq)∩Aq),
где Aq = {w∈Σ∗ | x ∈ L(M
q), |x| = 2|w| для некоторого x∈Σ∗}.
Из ответа на предыдущее упражнение следует (по теоремам 4.1
и 4.2), что языки Aq являются автоматными.
5. Регулярные выражения
5.1. Определение регулярного выражения
[Сал, 2.3], [АхоУль, 2.2.1], [ХопМотУль, 3.1], [Гла, 5.2], [СокКушБад, с. 25–26],
[ГорМол, с. 397–398], [LewPap2, 1.8], [Sip, 1.3], [Рей, с. 54–55], [КукБей, с. 335],
[АхоСетУль, 3.3]
Определение 5.1. Регулярное выражение над алфавитом Σ
определяется рекурсивно следующимоб разом: 0 является регу-
лярнымв ыражением; 1 является регулярнымв ыражением; если
a ∈ Σ, то a является регулярнымв ыражением; если e и f яв-
ляются регулярными выражениями, то (e+f), (e·f) и e∗ тоже
являются регулярными выражениями.
Для экономии скобок будем считать, что умножение связы-
вает теснее, чемс ложение. Вместо e·f часто пишут просто ef.
Пример 5.2. Пусть Σ = {a, b}. Тогда ((a·b)∗·(1+a)) является
регулярнымв ыражением над алфавитом Σ.
Определение 5.3. Каждое регулярное выражение e над
алфавитом Σ задаёт (denotes, represents) некоторый язык
над алфавитом Σ (обозначение L(e)), определяемое рекурсивно
следующимо бразом:
L(a) {a}, если a ∈ Σ,
L(0) ∅,
L(1) {ε},
L(e+f) L(e) ∪ L(f),
23
Регулярные выражения
L(e·f) L(e) · L(f),
L(e
∗) L(e)∗
.
Заметим, что в правой части последнего выражения символом ∗
обозначена итерация языка (см. определение 1.28).
Вместо L(e) часто пишут просто e.
Пример 5.4. Пусть Σ = {a, b}. Согласно определению
L((ab)∗·(1+a)) = {(ab)n | n 0} ∪ {(ab)na | n 0}.
Определение 5.5. Язык L называется регулярным, если он
задаётся некоторымр егулярнымв ыражением.
Определение 5.6. Пусть e — регулярное выражение. Тогда
e+ e∗e.
5.2*. Свойства регулярных выражений
[АхоУль, 2.2.1], [ХопМотУль, 3.4], [Сал, с. 37], [СокКушБад, с. 27–28], [ГорМол,
с. 398], [Рей, с. 55–56], [КукБей, с. 335–336]
Лемма 5.7. Регулярные выражения образуют ассоциатив-
ное полукольцо с операциями (0,+, 1, ·), то есть для любых
регулярных выражений e, f и g выполняются следующие тож-
дества:
1) e+f = f+e,
2) e+0 = e,
3) (e+f)+g = e+(f+g),
4) e·1 = e,
5) 1·e = e,
6) (e·f)·g = e·(f·g),
7) e·(f+g) = e·f+e·g,
8) (f+g)·e = f·e+g·e,
9) e·0 = 0,
10) 0·e = 0.
Равенство понимается как равенство языков, задаваемых
регулярными выражениями.
Лемма 5.8. Для любых регулярных выражений e и f
выполняются следующие тождества:
1) e+e = e,
2) (1+e+ee+. . .+en−1)(en)∗ = e∗ для любого n 1,
3) (e∗f)∗e∗ = (e+f)∗,
24
Регулярные выражения
4) 1+e(fe)∗f = (ef)∗.
Лемма 5.9. Для любых регулярных выражений e, f и g,
если e = ef+g и ε /∈ L(f), то e = gf∗.
Упражнение 5.10. Упростить регулярное выражение 0∗.
Ответ. 0∗ = 1.
5.3. Теорема Клини
[Сал, 2.4], [ХопМотУль, 3.2], [Гла, 5.2], [ГроЛан, 10.4.4], [ГорМол, с. 404–408],
[LewPap2, 2.3], [Рей, с. 56–57]
Определение 5.11. Назовём обобщённым конечным авто-
матом аналог конечного автомата, где переходы помечены не
словами, а регулярными выражениями. Метка пути такого ав-
томата — произведение регулярных выражений на переходах
данного пути. Слово w допускается обобщённымк онечным ав-
томатом, если оно принадлежит языку, задаваемому меткой неко-
торого успешного пути.
Замечание 5.12. Каждый конечный автомат можно преоб-
разовать в обобщённый конечный автомат, допускающий те же
слова. Для этого достаточно заменить всюду в метках переходов
пустое слово на 1, а каждое непустое слово на произведение его
букв.
Замечание 5.13. Если к обобщённому конечному автомату
добавить переход с меткой 0, то м ножество допускаем ых этим
автоматом слов не изменится.
Пример 5.14. Пусть Σ = {a, b, c}. Обобщённый
конечный автомат Q,Σ,Δ, I, F
, где Q = {1, 2, 3},
Δ = { 1, a, 2
, 2, b∗ba, 2
, 2, b∗, 3
}, I = {1, 2} и F = {3},
допускает все слова в алфавите Σ, кром еслов, содержащих
подслово aa.
Теорема 5.15 (теорема Клини). Язык L является регуляр-
ным тогда и только тогда, когда он является автоматным.
Доказательство. Пусть e — регулярное выражение. Индук-
цией по построению e легко показать, что задаваемый им язык
является автоматным (см. теорему 3.1).
25
Регулярные выражения
Обратно, пусть язык L распознаётся некоторым( недетерми-
нированным) конечным автоматомс однимн ачальным состоя-
ниеми одним заключительным состоянием. Существует эквива-
лентный ему обобщённый конечный автомат Q,Σ,Δ, {q1}, {q2}
,
где q1 = q2. Если есть несколько переходов с общимн ачалом и
общимк онцом (такие переходы называются параллельными), за-
меним их на один переход, используя операцию +.
Устранимп о очереди все состояния, кроме q1 и q2. При устра-
нении состояния q надо для каждого перехода вида p1, f1, q
, где
p1 = q, и для каждого перехода вида q, f2, p2
, где p2 = q, до-
бавить переход p1, f1g∗f2, p2
, где регулярное выражение g —
метка перехода из q в q (если такого перехода нет, то считаем,
что g = 0), и снова всюду заменить параллельные переходы на
один переход, используя операцию +.
После устранения всех состояний, кроме q1 и q2, получится
обобщённый конечный автомат {q1, q2},Σ,Δ , {q1}, {q2}
, где
Δ = { q1, e11, q1
, q1, e12, q2
, q2, e21, q1
, q2, e22, q2
}. Очевидно,
L = L(e∗
11e12(e22+e21e∗
11e12)∗).
Пример 5.16. Рассмотрим язык, распознаваемый конечным
автоматом M = {q1, q2, q3, q4},Σ,Δ, {q1}, {q2}
, где Σ = {a, b, c}
и
Δ = { q1, a, q4
, q2, cb, q2
, q2, bac, q4
,
q3, a, q1
, q3, c, q2
, q3, c, q4
, q4, ε, q3
, q4, b, q4
}.
Тот же язык порождается обобщённымк онечныма втоматом
M1 = {q1, q2, q3, q4},Σ,Δ1, {q1}, {q2}
, где
Δ1 = { q1, a, q4
, q2, cb, q2
, q2, bac, q4
,
q3, a, q1
, q3, c, q2
, q3, c, q4
, q4, 1, q3
, q4, b, q4
}.
После устранения состояния q3 получается обобщённый конеч-
ный автомат M2 = {q1, q2, q4},Σ,Δ2, {q1}, {q2}
, где
Δ2 = { q1, a, q4
, q2, cb, q2
, q2, bac, q4
,
q4, 1·0∗·a, q1
, q4, 1·0∗·c, q2
, q4, b+1·0∗·c, q4
}.
Можно упростить регулярные выражения и получить
Δ
2 = { q1, a, q4
, q2, cb, q2
, q2, bac, q4
,
q4, a, q1
, q4, c, q2
, q4, b+c, q4
}.
26
Синтаксические моноиды
После устранения состояния q4 и упрощения регуляр-
ных выражений получается обобщённый конечный автомат
M3 = {q1, q2},Σ,Δ3, {q1}, {q2}
, где
Δ3 = { q1, a(b+c)∗
a, q1
, q1, a(b+c)∗
c, q2
,
q2, bac(b+c)∗
a, q1
, q2, cb+bac(b+c)∗
c, q2
}.
Следовательно, язык L(M) задаётся регулярнымв ыражением
(a(b+c)∗
a)∗
a(b+c)∗
c·
·(cb+bac(b+c)∗
c+bac(b+c)∗
a(a(b+c)∗
a)∗
a(b+c)∗
c)∗
.
Упростив это регулярное выражение, получим
L(M) = L(a(aa+b+c+c(cb)∗
bac)∗
c(cb)∗).
6. Синтаксические моноиды
6.1. Множества правых контекстов
[АхоУль, с. 157–158], [Лал, с. 179–180], [LewPap2, 2.5], [ТраБар, 1.2], [ГроЛан,
13.2.3, 14.3.1–14.3.5], [Рей, с. 57–59], [Сал, с. 37]
Определение 6.1. Пусть L ⊆ Σ∗ и y ∈ Σ∗. Тогда множество
правых контекстов слова y относительно языка L определяется
так: C(r)
L (y) {z ∈ Σ∗ | yz ∈ L}.
Пример 6.2. Пусть Σ = {a, b} и L = {anban | n 0}. Тогда
1) C(r)
L (ai) = {akbak+i | k 0},
2) если i j, то C(r)
L (aibaj) = {ai−j},
3) если i < j, то C(r)
L (aibaj) = ∅,
4) если |y|b > 1, то C(r)
L (y) = ∅.
Лемма 6.3. Если язык L распознаётся полным де-
терминированным конечным автоматом Q,Σ,Δ, I, F
, то
|{C(r)
L (y) | y ∈ Σ∗}| |Q|.
Доказательство. Пусть I = {s}. Введёмобоз начение
J {C(r)
L (y) | y ∈ Σ∗}. Определимф ункцию f : J → Q, положив
f(A) равным Δy(s), где y — некоторое слово, для которого вы-
полнено условие C(r)
L (y) = A (если существует несколько таких
27
Синтаксические моноиды
слов y, то можно использовать, например, первое среди них в
лексикографическомпо рядке).
Заметим, что для любых слов u и v, если C(r)
L (u) = C(r)
L (v),
то Δu(s) = Δv(s). Следовательно, функция f является инъек-
тивной. Но тогда |J| |Q|.
Пример 6.4. Рассмотрим язык L, порождаемый полным де-
терминированным конечным автоматом Q,Σ,Δ, I, F
 из приме-
ра 2.41. Тогда {C(r)
L (y) | y ∈ Σ∗} = {C(r)
L (ε),C(r)
L (a),C(r)
L (b)},
C(r)
L (ε) = {(ab)n | n 0} ∪ {(ab)na | n 0},
C(r)
L (a) = {b(ab)n | n 0} ∪ {(ba)n | n 0} и C(r)
L (b) = ∅.
Лемма 6.5. Если L ⊆ Σ∗ и множество {C(r)
L (y) | y ∈ Σ∗}
конечно, то язык L является автоматным.
Доказательство. Язык L распознаётся полнымд етерми-
нированнымк онечным автоматом Q,Σ,Δ, I, F
, где Q =
= {C(r)
L (y) | y ∈ Σ∗}, I = {C(r)
L (ε)}, F = {C(r)
L (y) | y ∈ L},
Δ = { C(r)
L (y), a,C(r)
L (ya)
 | y ∈ Σ∗, a ∈ Σ}.
Пример 6.6. Пусть Σ = {a, b}. Рассмотрим автоматный язык
L = a+b∗. Обозначим qε = C(r)
L (ε), qa = C(r)
L (a), qb = C(r)
L (b) = ∅,
qab = C(r)
L (ab). Тогда {C(r)
L (y) | y ∈ Σ∗} = {qε, qa, qb, qab}. Язык L
распознаётся полным детерминированнымк онечныма втоматом
Q,Σ,Δ, I, F
, где Q = {qε, qa, qb, qab}, I = {qε}, F = {qa, qab},
Δ = { qε, a, qa
, qε, b, qb
, qa, a, qa
, qa, b, qab
,
qb, a, qb
, qb, b, qb
, qab, a, qb
, qab, b, qab
}.
Теорема 6.7. Язык L ⊆ Σ∗ является автоматным тогда и
только тогда, когда множество {C(r)
L (y) | y ∈ Σ∗} конечно.
Доказательство. Необходимость доказана в лемме 6.3, до-
статочность — в лемме 6.5.
Замечание 6.8. В силу леммы 6.3 полный детерминирован-
ный конечный автомат, построенный в доказательстве леммы 6.5,
является минимальным (по количеству состояний) среди всех
полных детерминированных конечных автоматов, распознающих
заданный язык. Можно доказать, что любой минимальный пол-
ный детерминированный конечный автомат, распознающий за-
данный язык, изоморфен этому автомату.
28
Синтаксические моноиды
6.2. Минимизация детерминированных
конечных автоматов
[АхоУль, 2.3.1], [Сал, с. 36–37], [ХопМотУль, 4.4], [ГорМол, с. 395–397], [Рей,
с. 59–61], [LewPap2, 2.5]
Определение 6.9. Говорят, что слово w различает (distinguishes)
состояния p и q полного детерминированного конечного
автомата Q,Σ,Δ, I, F
, если одно из состояний Δw(p), Δw(q)
заключительное, а другое не является заключительным.
Определение 6.10. Состояния p и q полного детерминиро-
ванного конечного автомата Q,Σ,Δ, I, F
 называются различи-
мыми (distinguishable), если существует слово w, которое их раз-
личает.
Замечание 6.11. Пусть полный детерминированный конеч-
ный автомат Q,Σ,Δ, {qs}, F
 задаёт язык L. Рассмотрим про-
извольные слова u ∈ Σ∗ и v ∈ Σ∗. Состояния Δu(qs) и Δv(qs)
различимы тогда и только тогда, когда C(r)
L (u) = C(r)
L (v).
Теорема 6.12. Существует быстрый алгоритм, позволя-
ющий по произвольному детерминированному конечному ав-
томату находить минимальный (по количеству состояний)
автомат среди детерминированных конечных автоматов, эк-
вивалентных исходному автомату.
Доказательство. Без ограничения общности можно предпо-
ложить, что дан полный детерминированный конечный автомат
Q,Σ,Δ, I, F
, все состояния которого достижимы из начально-
го состояния (для обеспечения полноты достаточно добавить од-
но состояние). Для каждого натурального числа i определимна
множестве Q отношение эквивалентности ≡i:
p ≡0 q ⇐⇒ (p ∈ F и q ∈ F) или (p /∈ F и q /∈ F),
p ≡i+1 q ⇐⇒ p ≡i q и Δa(p) ≡i Δa(q) для каждого a ∈ Σ.
Легко видеть, что p ≡i q тогда и только тогда, когда никакое
слово длины не больше i не различает p и q. Обозначим n = |Q|.
Легко проверить, что для любого k n отношение ≡k совпада-
ет с отношением ≡n−1. Используя классы эквивалентности от-
ношения ≡n−1 как состояния, можно построить минимальный
полный детерминированный конечный автомат. Удалив из него
29
Синтаксические моноиды
бесполезное состояние (из которого не достижимо ни одно за-
ключительное состояние), если такое имеется, получим искомый
минимальный детерминированный конечный автомат.
Пример 6.13. Рассмотрим полный детерминированный ко-
нечный автомат {1, 2, 3, 4, 5, 6}, {a, b},Δ, {1}, {1, 3}
, где
Δ = { 1, a, 2
, 2, b, 3
, 3, a, 4
, 4, b, 1
, 4, a, 5
, 5, a, 5
,
1, b, 6
, 2, a, 6
, 3, b, 6
, 5, b, 6
, 6, a, 6
, 6, b, 6
}.
Он эквивалентен минимальному детерминированному конечному
автомату {{1, 3}, {2, 4}}, {a, b},Δ , {{1, 3}}, {{1, 3}}
, где
Δ = { {1, 3}, a, {2, 4}
, {2, 4}, b, {1, 3}
}.
Замечание 6.14. Неизвестно, существует ли быстрый (поли-
номиальный) алгоритм, позволяющий по произвольному конеч-
ному автомату находить минимальный автомат среди всех (не
обязательно детерминированных) конечных автоматов, эквива-
лентных исходному автомату.
6.3. Множества двусторонних контекстов
[Лал, с. 180], [Гин, 2.1], [Гла, 5.2], [ТраБар, 1.2], [ГроЛан, 13.2.1, 14.3.5], [АхоУль,
с. 158]
Определение 6.15. Пусть L ⊆ Σ∗ и y ∈ Σ∗. Тогда мно-
жество контекстов (множество двусторонних контекстов)
слова y относительно языка L определяется так: CL(y)
{ x, z
 ∈ Σ∗ × Σ∗ | xyz ∈ L}.
Пример 6.16. Пусть Σ = {a, b} и L = {anban | n 0}. Тогда
CL(ai) = { am, akbak+i+m
 | m 0, k 0} ∪
∪ { ak+i+mbak, am
 | k 0, m 0},
CL(aibaj) = { ak, am
 | k 0, m 0, k + i = m+ j},
C(r)
L (y) = ∅, если |y|b > 1.
Лемма 6.17. Если CL(u1) = CL(u2), то C(r)
L (u1) = C(r)
L (u2).
Доказательство. Из определений следует, что C(r)
L (y) =
= {z ∈ Σ∗ | ε, z
 ∈ CL(y)}.
30
Синтаксические моноиды
Лемма 6.18. Если CL(u1) = CL(u2), то CL(u1v) = CL(u2v)
и CL(vu1) = CL(vu2).
Доказательство. Пусть CL(u1) = CL(u2) и x, z
 ∈ CL(u1v).
Тогда xu1vz ∈ L. Следовательно, x, vz
 ∈ CL(u1). Далее,
x, vz
 ∈ CL(u2), xu2vz ∈ L и x, z
 ∈ CL(u2v). Второе равенство
доказывается аналогично.
Лемма 6.19. Если CL(u1) = CL(u2) и CL(v1) = CL(v2), то
CL(u1v1) = CL(u2v2).
Определение 6.20. Пусть L ⊆ Σ∗. Тогда м ножество
Synt(L) {CL(y) | y ∈ Σ∗} называется синтаксическим мо-
ноидом (syntactic monoid) языка L.
Теорема 6.21. Синтаксический моноид Synt(L) конечен
тогда и только тогда, когда язык L является автоматным.
Доказательство. Пусть множество Synt(L) конечно. Соглас-
но лемме 6.17 множество {C(r)
L (y) | y ∈ Σ∗} тоже конечно. В силу
леммы 6.5 язык L является автоматным.
Обратно, пусть язык L распознаётся конечнымав томатом
M = Q,Σ,Δ, I, F
, не содержащимп ереходов с метками длины
больше единицы. Поставимкаж дому слову y в соответствие
множество TrM(y) ⊆ Q × Q, определённое так: TrM(y) =
= { p, q
 ∈ Q×Q | существует путь из p в q с м еткой y}. Легко
проверить, что если TrM(y1) = TrM(y2), то CL(y1) = CL(y2).
Следовательно, | Synt(L)| 2n2, где n = |Q|.
Лемма 6.22. Пусть L ⊆ Σ∗, n ∈ N и для каждого слова
y ∈ Σ∗ длины n найдётся такое слово x ∈ Σ∗, что |x| < n и
CL(x) = CL(y). Тогда Synt(L) = {CL(y) | y ∈ Σ∗, |y| < n}.
Доказательство. Индукцией по k n можно доказать, что
для каждого слова y ∈ Σ∗ длины k найдётся такое слово x ∈ Σ∗,
что |x| < n и CL(x) = CL(y). В шаге индукции используется
лемма 6.19.
31
Неоднозначность в контекстно-свободных грамматиках
7. Неоднозначность
в контекстно-свободных
грамматиках
7.1. Деревья вывода
[Гин, 1.5], [ХопМотУль, 5.2.1, 5.2.2], [СокКушБад, с. 13–14, 31], [Бра, с. 45–56],
[Лал, с. 294], [АхоУль, 0.5.1–0.5.4, 2.4.1], [ГорМол, с. 370–372], [ГроЛан, 8.2.1],
[Гла, 3.1], [LewPap2, 3.2], [Рей, с. 31–32], [АхоСетУль, 2.2, 4.2], [КукБей, с. 277]
Определение 7.1. Выводамв контекстно-свободной грамма-
тике соответствуют так называемые деревья вывода (или деревья
разбора) (derivation tree, parse tree) — некоторые упорядоченные
деревья, вершины которых помечены символами алфавита N ∪Σ.
Корень дерева отвечает начальному символу. Каждому символу
слова w1, на которую заменяется начальный символ на первом
шаге вывода, ставится в соответствие вершина дерева, и к ней
проводится дуга из корня. Полученные такимоб разомн епосред-
ственные потомки корня упорядочены согласно порядку их меток
в слове w1. Для тех из полученных вершин, которые помечены
символами из множества N, делается аналогичное построение
и т. д.
Кроной (yield) дерева вывода называется слово, записанное в
вершинах, помеченных символами из алфавита Σ.
Пример 7.2. Рассмотрим контекстно-свободную грамматику
S → SS, S → ab, S → aSb. Выводу S ⇒ SS ⇒ Sab ⇒ SSab ⇒
⇒ abSab ⇒ ababab соответствует следующее дерево вывода.
S


S

S

S

S

a b
a b a b
32
Неоднозначность в контекстно-свободных грамматиках
7.2. Однозначные
контекстно-свободные грамматики
[Гин, 1.6], [АхоУль, 2.4.1, 2.6.5], [ХопМотУль, 5.1.4, 5.2.3–5.2.6, 5.4], [Бра,
с. 56–58], [Лал, с. 307], [ГорМол, с. 372–374], [СокКушБад, с. 14], [ГроЛан,
8.2.3], [Гла, 3.1, 4.3], [LewPap2, 3.2], [Sip, 2.1], [Рей, с. 32], [АхоСетУль, 2.2,
4.2], [КукБей, с. 272–275]
Определение 7.3. Вывод в контекстно-свободной грамма-
тике называется левосторонним или левым (leftmost derivation),
если на каждом шаге вывода заменяется самое левое
из всех вхождений вспомогательных символов (то есть каж-
дый шаг вывода имеет вид uAθ ⇒ uβθ, где (A → β) ∈ P,
u ∈ Σ∗ и θ ∈ (N ∪ Σ)∗). Иногда в левосторонних выводах вме-
сто ⇒ пишут ⇒
lm
. Правосторонний вывод определяется анало-
гично.
Пример 7.4. Вывод S ⇒ SS ⇒ Sab ⇒ SSab ⇒ abSab ⇒
⇒ ababab из примера 7.2 не является левосторонним.
Лемма 7.5. Для каждого слова, выводимого в контекст-
но-свободной грамматике, существует левосторонний вы-
вод.
Лемма 7.6. Пусть G — контекстно-свободная граммати-
ка над алфавитом Σ. Пусть w ∈ Σ∗. Тогда сущ ествует вза-
имно-однозначное соответствие между левосторонними вы-
водами слова w в грамматике G и деревьями вывода в грам-
матике G, кроной которых является w.
Пример 7.7. Рассмотрим дерево вывода из примера 7.2. Ему
соответствует левосторонний вывод S ⇒
lm
SS ⇒
lm
SSS ⇒
lm
abSS ⇒
lm
⇒
lm
ababS ⇒
lm
ababab.
Определение 7.8. Контекстно-свободная грамматика назы-
вается неоднозначной (ambiguous), если существует слово, ко-
торое имеет два или более левосторонних вывода. (Устаревший
термин — неопределённая грамматика.) В противном случае кон-
текстно-свободная грамматика называется однозначной (unambiguous).
33
Неоднозначность в контекстно-свободных грамматиках
Пример 7.9. Контекстно-свободная грамматика из приме-
ра 7.2 неоднозначна. Слово ababab имеет два левосторонних вы-
вода: S ⇒
lm
SS ⇒
lm
SSS ⇒
lm
abSS ⇒
lm
ababS ⇒
lm
ababab и S ⇒
lm
SS ⇒
lm
⇒
lm
abS ⇒
lm
abSS ⇒
lm
ababS ⇒
lm
ababab.
Пример 7.10. Пусть Σ = {p,#, ), (,¬,∧,∨}. Контекст-
но-свободная грамматика S → S∨D, S → D, D → D∧C, D → C,
C → ¬C, C → (S), C → V , V → V#, V → p порождает мно-
жество всех булевых формул, составленных из переменных p,
p#, p##, . . . с помощью скобок и операторов ¬, ∧ и ∨. Эта
грамматика является однозначной.
Определение 7.11. Контекстно-свободный язык называется
существенно неоднозначным (inherently ambiguous), если каж-
дая контекстно-свободная грам матика, порождающая этот язык,
является неоднозначной.
Пример 7.12. Язык, порождаемый контекстно-свободной
грамматикой из примера 7.2, не является существенно неодно-
значным. Он порождается однозначной грамматикой S → TS,
S → T , T → ab, T → aSb.
Пример 7.13*. Пусть Σ = {a, b, c}. Контекстно-свободный
язык {akbmcn | k = m или m = n} является существенно неод-
нозначным. Доказательство этого факта можно найти в [АхоУль,
с. 234–236].
7.3*. Однозначные
праволинейные грамматики
[Лал, с. 187], [АхоУль, с. 119]
Теорема 7.14. Каждый праволинейный язык порождается
некоторой однозначной праволинейной грамматикой. Други-
ми словами, ни один праволинейный язык не является суще-
ственно неоднозначным.
Доказательство. Согласно теоремам 2.33 и 2.43 исходный
язык распознаётся некоторымд етерминированнымк онечным
автоматом. Применив к нему конструкцию из доказательства
теоремы 2.31, получим однозначную праволинейную грамматику.
34
Нормальные формы контекстно-свободных грамматик
7.4. Языки Дика и Лукасевича
[Сал, с. 103, 116], [Лал, с. 293–295], [ЛПИИ, 5.1.3], [АхоУль, с. 239], [Гла, 6.5],
[ГроЛан, 15.1]
Определение 7.15. Языком Дика (Dyck language) над 2n
буквами называется контекстно-свободный язык над алфавитом
{a1, b1, a2, b2, . . . , an, bn}, порождаемый грамматикой S → ε,
S → a1Sb1S, . . . , S → anSbnS.
Замечание 7.16. Словами этого языка являются последова-
тельности правильно вложенных скобок n типов.
Замечание 7.17. При любомп оложительном целом n грам-
матика из определения 7.15 является однозначной.
Определение 7.18. Языком Лукасевича (Lukasiewicz language)
над n + 1 буквами называется контекстно-свободный
язык над алфавитом {a0, a1, . . . , an}, порождаемый грамматикой
S → a0, S → a1S, S → a2SS, . . . , S → anSn.
Замечание 7.19. При любом n ∈ N грамматика из определе-
ния 7.18 является однозначной.
8. Нормальные формы
контекстно-свободных грамматик
8.1. Устранение бесполезных символов
[АхоУль, 2.4.2], [ХопМотУль, 7.1.1, 7.1.2], [ГорМол, с. 427–429], [Гла, 4.2], [Бра,
с. 61–64], [Рей, с. 65–66], [КукБей, с. 285–287]
Определение 8.1. Пусть дана порождающая грамматика
G = N,Σ, P, S
. Сим вол A ∈ N называется полезным (useful),
если существуют такие слова α ∈ (N ∪ Σ)∗, β ∈ (N ∪ Σ)∗
и w ∈ Σ∗, что S
∗⇒
αAβ и αAβ
∗⇒
w. Сим вол A ∈ N назы-
вается бесполезным (useless), если он не является полезным .
Символ A ∈ N называется порождающим (generating), если су-
ществует такое слово w ∈ Σ∗, что A
∗⇒
w. Сим вол A ∈ N назы-
вается достижимым (reachable), если существуют такие слова
α ∈ (N ∪ Σ)∗ и β ∈ (N ∪ Σ)∗, что S
∗⇒
αAβ.
35
Нормальные формы контекстно-свободных грамматик
Теорема 8.2. Пусть дана контекстно-свободная грамма-
тика G = N,Σ, P, S
 и L(G) = ∅. Тогда существуют такие
множества N ⊆ N и P ⊆ P, что в контекстно-свободной
грамматике N ,Σ, P , S
 нет бесполезных символов и она эк-
вивалентна исходной грамматике.
Доказательство. Сначала удалимв се непорождающие сим-
волы (удалим также каждое правило, содержащее хотя бы один
такой символ). Затем из полученной грамматики удалим все
недостижимые символы (и правила, их содержащие).
Пример 8.3. Рассмотрим контекстно-свободную граммати-
ку G с правилам иS → UX, S → V Z, T → aa, T → bb, U → aUa,
U → bUb, V → aT b, V → bT a, W → Y ZY , W → aab, X → Xa,
X → Xb, X → ε, Y → Y Y , Y → aU, Y → ε, Z → W, Z → b.
Удалив четыре правила, содержащие непорождающий символ U,
получимг рамматику G1. В ней сим вол X является недостижи-
мым. Удалив три правила, содержащие X, получимгр аммати-
ку G2 с правилам иS → V Z, T → aa, T → bb, V → aT b,
V → bT a, W → Y ZY , W → aab, Y → Y Y , Y → ε, Z → W,
Z → b. Очевидно, L(G) = L(G2) и грам матика G2 не содержит
бесполезных символов.
8.2. Устранение ε-правил
[Гин, 1.8], [АхоУль, 2.4.2], [ХопМотУль, 7.1.3], [Лал, с. 295–296], [ГорМол,
с. 429–431], [Гла, 4.2], [Бра, с. 71–76], [ГроЛан, 7.2.6], [Сал, 6.2], [Sip, 2.1],
[Рей, с. 35–37], [КукБей, с. 288–289]
Теорема 8.4. Пусть язык L является контекстно-свобод-
ным. Тогда язык L − {ε} порождается некоторой контекст-
но-свободной грамматикой без ε-правил.
Доказательство. Пусть дана контекстно-свободная грамма-
тика G = N,Σ, P, S
, порождающая язык L. Проведём серию
преобразований множества P.
Если для каких-то A ∈ N, B ∈ N, α ∈ (N ∪ Σ)∗ и
β ∈ (N ∪Σ)∗ множество P содержит правила B → αAβ и A → ε,
но не содержит правила B → αβ, то добавим это правило в P.
Повторяемэ ту процедуру, пока возможно.
Теперь исключимиз множества P все правила вида A → ε.
Полученная грамматика порождает язык L − {ε}.
36
Нормальные формы контекстно-свободных грамматик
Пример 8.5. Рассмотрим язык L, порождаемый грамматикой
S → ε, S → aSbS. Язык L − {ε} порождается грамматикой
S → aSbS, S → abS, S → aSb, S → ab.
8.3. Нормальная форма Хомского
[Сал, 6.2], [АхоУль, 2.4.2, 2.4.3], [ХопМотУль, 7.1], [ГорМол, с. 431–437], [Гла,
4.1], [СокКушБад, с. 32], [Лал, с. 330], [Sip, 2.1], [Рей, с. 66–68]
Определение 8.6. Грамматика в нормальной форме Хом-
ского (грамматика в бинарной нормальной форме, квадра-
тичная грамматика) (grammar in Chomsky normal form) —
контекстно-свободная грамматика N,Σ, P, S
, в которой каждое
правило имеет один из следующих трёх видов: S → ε, A → a,
A → BC, где A ∈ N, B ∈ N − {S}, C ∈ N − {S}, a ∈ Σ.
Пример 8.7. Грамматика S → RR, S → AB, R → RR,
R → AB, A → a, B → RB, B → b — грамматика в нормальной
форме Хомского.
Теорема 8.8. Каждая контекстно-свободная грамматика
эквивалентна некоторой грамматике в нормальной форме
Хомского.
Доказательство. Пусть дана контекстно-свободная грамма-
тика G = N,Σ, P, S
. Проведёмр яд преобразований этой грам-
матики так, что порождаемый ею язык остаётся неизменным.
Если правая часть какого-нибудь правила содержит сим-
вол S, то заменим грамматику N,Σ, P, S
 на грамматику
N ∪ {S0},Σ, P ∪ {S0 → S}, S0
, где S0 — новый сим вол, не
принадлежащий множеству N ∪ Σ.
Заменим во всех правилах каждый терминальный символ a
на новый нетерминальный символ Ta и добавим к множеству P
правила Ta → a для всех a ∈ Σ.
Устранимп равила вида A → α, где |α| > 2, заменив каждое
из них на ряд более коротких правил (при этомд обавляются
новые нетерминальные символы).
Теперь устранимв се правила вида A → ε, где A не является
начальным символом. Это можно сделать, как в доказательстве
теоремы 8.4.
Если для каких-то A ∈ N, B ∈ N и α ∈ (N∪Σ)∗ множество P
содержит правила A → B и B → α, но не содержит правила
37
Нормальные формы контекстно-свободных грамматик
A → α, то добавим это правило в P. Повторяем эту процедуру,
пока возможно. После этого исключим из множества P все
правила вида A → B.
Пример 8.9. Грамматика S → ε, S → aUbU , U → S,
U → ba эквивалентна следующей грамматике в нормальной
форме Хомского: S0 → ε, S0 → AD, D → UC, D → BU, D → b,
C → BU, C → b, U → BA, U → AD, A → a, B → b.
Теорема 8.10. Если контекстно-свободный язык не содер-
жит пустого слова, то он порождается некоторой грамма-
тикой, в которой каждое правило имеет один из следующих
двух видов: A → a, A → BC, где A ∈ N, B ∈ N − {S},
C ∈ N − {S}, a ∈ Σ.
8.4*. Нормальная форма Грейбах
[Сал, 6.2], [АхоУль, 2.4.4, 2.4.5], [ГорМол, с. 437–440], [Гла, 6.2], [Бра,
с. 121–124], [Рей, с. 71–76], [СокКушБад, с. 32]
Определение 8.11. Грамматика в нормальной форме Грей-
бах (grammar in Greibach normal form) — контекстно-свободная
грамматика N,Σ, P, S
, в которой каждое правило имеет один из
следующих четырёх видов: A → ε, A → a, A → aB, A → aBC,
где A ∈ N, B ∈ N, C ∈ N, a ∈ Σ.
Пример 8.12. Грамматика S → aST , S → aT , T → bS,
T → b — грамматика в нормальной форме Грейбах.
Замечание 8.13. Некоторые авторы разрешают в граммати-
ках в нормальной форме Грейбах использовать также правила
вида A → aβ, где A ∈ N, a ∈ Σ, β ∈ N∗ (в определении 8.11
такие правила разрешены, только если |β| 2).
Теорема 8.14. Каждая контекстно-свободная грамматика
эквивалентна некоторой грамматике в нормальной форме
Грейбах.
Доказательство. Докажемт еорему для контекстно-свобод-
ных языков, не содержащих пустого слова. В силу теоре-
мы 8.10 исходный язык порождается некоторой грамматикой
G = N,Σ, P, S
, в которой каждое правило имеет вид A → a
или A → BC, где A ∈ N, B ∈ N − {S}, C ∈ N − {S}, a ∈ Σ.
38
Нормальные формы контекстно-свободных грамматик
Введём |N|2 новых вспомогательных символов, соответству-
ющих упорядоченнымп арам из множества N × N. Новый сим -
вол, соответствующий паре A,B
, будемобоз начать (A\B).
Построим грамматику “почти в нормальной форме Грейбах”
G = N,Σ, P,S
, положив N = N ∪ {(A\B) | A ∈ N, B ∈ N} и
P = {(A\A) → ε | A ∈ N} ∪
∪ {(C\E)→A(A\D)(B\E) | (B→CD)∈P, A∈N, E∈N} ∪
∪ {A → a | (A → a) ∈ P} ∪
∪ {S → a(A\S) | (A → a) ∈ P}.
Если в этой грамматике заменить
{(C\E) → A(A\D)(B\E) | (B → CD) ∈ P, A ∈ N, E ∈ N} ∪
∪ {A → a | (A → a) ∈ P}
на
{(C\E) → a(A\D)(B\E) | (B→CD) ∈ P, (A→a) ∈ P, E ∈ N},
получим эквивалентную ей грамматику в нормальной форме
Грейбах. Осталось лишь доказать, что L(G) = L(G).
Сначала проверими ндукцией по длине слова γ ∈ N∗, что
если F
∗⇒
G
Cγ, то (C\E) ∗⇒
G
γ(F\E) для любого E ∈ N. Что-
бы провести шаг индукции, допустим, что (B → CD) ∈ P,
F
∗⇒
G
Bβ ⇒
G
CDβ
∗⇒
G
CAαβ, где D
∗⇒
G
Aα и γ = Aαβ. По предпо-
ложению индукции (B\E) ∗⇒
G
β(F\E) и (A\D) ∗⇒
G
α(D\D). Под-
ключая эти выводы к правилу (C\E) ⇒
G
A(A\D)(B\E) и исполь-
зуя (D\D) ⇒
G
ε, получаеми скомый вывод (C\E) ∗⇒
G
Aαβ(F\E).
Докажемте перь, что для любого γ ∈ N∗ равносильны
утверждения F
∗⇒
G
Cγ и (C\F) ∗⇒
G
γ. В одну сторону это
следует из только что доказанного. Доказательство того, что
если (C\F) ∗⇒
G
γ, то F
∗⇒
G
Cγ, проведёми ндукцией по длине
слова γ ∈ N∗. Чтобы провести шаг индукции, допустим, что
(B → CD) ∈ P, (C\F) ⇒
G
A(A\D)(B\F), (A\D) ∗⇒
G
α,
(B\F) ∗⇒
G
β и γ = Aαβ. По предположению индукции D
∗⇒
G
Aα и
F
∗⇒
G
Bβ. Получаеми скомый вывод F
∗⇒
G
Bβ ⇒
G
CDβ
∗⇒
G
CAαβ.
39
Основные свойства контекстно-свободных языков
Теперь убедимся, что L(G) = L(G). Рассмотрим произвольное
слово a0a1 . . . am, где m 0 и ai ∈ Σ для всех i m. Пусть
S
∗⇒
G
A0A1 . . . Am
∗⇒
G
a0a1 . . . am, где Ai ∈ N для всех i m.
Тогда S ⇒
G
a0(A0\S) ∗⇒
G
a0A1 . . .Am
∗⇒
G
a0a1 . . . am. Обратно,
пусть S ⇒
G
a0(A0\S) ∗⇒
G
a0A1 . . . Am
∗⇒
G
a0a1 . . .am, где Ai ∈ N
для всех i m. Тогда S
∗⇒
G
A0A1 . . . Am
∗⇒
G
a0a1 . . .am.
Пример 8.15. Грамматика S → RT, T → b, T → UR,
U → V T, V → RT, R → a эквивалентна следующей грамматике
в нормальной форме Грейбах: S → aC, C → aD, C → b,
D → aDE, D → bE, E → aDF, E → bF , F → a. Здесь C, D, E
и F соответствуют символам (A\S), (A\T ), (V \T ) и (U\T ) из
доказательства теоремы 8.14 (удалён 21 бесполезный символ).
Теорема 8.16. Пусть язык L контекстно-свободный. Тогда
язык L−{ε} порождается некоторой грамматикой в нормаль-
ной форме Грейбах без ε-правил.
Пример 8.17. Грамматика S → aR, R → bRT , R → ε,
T → cSR, T → ε эквивалентна следующей грамматике в
нормальной форме Грейбах без ε-правил: S → aR, S → a,
R → bRT , R → bT , R → bR, R → b, T → cSR, T → cS.
9. Основные свойства
контекстно-свободных языков
9.1. Лемма о разрастании
для контекстно-свободных языков
[Sip, 2.3], [Гин, 3.1], [ХопМотУль, 7.2], [Лал, с. 299–300], [АхоУль, 2.6.1], [Гла,
4.3, 4.1], [ГорМол, с. 425–426], [СокКушБад, с. 33–34], [LewPap2, 3.5], [ГроЛан,
7.4.2], [Рей, с. 68–71], [КукБей, с. 279–281]
Лемма 9.1 (pumping lemma, лемма о разрастании, лемма
о накачке, лемма-насос). Пусть L — контекстно-свободный
язык над алфавитом Σ. Тогда найдётся такое натуральное
число p, что для любого слова w ∈ L длины не меньше p
найдутся слова u, v, x, y, z ∈ Σ∗, для которых верно uvxyz = w,
40
Основные свойства контекстно-свободных языков
vy = ε (то есть v = ε или y = ε), |vxy| p и uvixyiz ∈ L для
всех i ∈ N.
Доказательство. Пусть язык L порождается грамматикой в
нормальной форме Хомского G = N,Σ, P, S
. Индукцией по k
легко доказать, что для любого дерева вывода в грамматике G
длина кроны дерева не превышает 2k−2, где k — количество
вершин в самомд линномпути, начинающемся в корне дерева
и заканчивающемся в некоторой вершине, помеченной символом
из Σ.
Положим p = 2|N|. Пусть w ∈ L и |w| p. Зафиксируем
некоторое дерево вывода с кроной w в грам матике G. Рассмотрим
самый длинный путь в этом дереве. Этот путь содержит не менее
|N|+2 вершин. Среди них найдутся две вершины с одинаковыми
метками, причём их можно выбрать среди последних |N| + 2
вершин рассматриваемого пути. Выберем слова u, v, x, y и z
так, что uvxyz = w, поддерево с корнемв одной из найденных
вершин имеет крону x и поддерево с корнем в другой найденной
вершине имеет крону vxy.
Из того что G — грамматика в нормальной форме Хомского,
заключаем, что vxy = x. Неравенство |vxy| 2|N| следует из
того, что самый длинный путь в соответствующем слову vxy
поддереве содержит не более |N|+2 вершин. Для каждого i ∈ N
можно построить дерево вывода с кроной uvixyiz, комбинируя
части исходного дерева вывода.
Пример 9.2. Рассмотрим язык L = {anbncn | n 0}
над алфавитом {a, b, c}. Утверждение леммы 9.1 не выполняется
ни для какого натурального числа p. Действительно, если
uvxyz = apbpcp, |vy| > 0 и |vxy| p, то |vy|a = 0 или |vy|c = 0.
Следовательно, |uvvxyyz|a = p или |uvvxyyz|c = p. Так как
|uvvxyyz| > 3p, то uvvxyyz /∈
L. Из этого можно заключить,
что язык L не является контекстно-свободным.
Теорема 9.3. Каждый контекстно-свободный язык над
однобуквенным алфавитом является автоматным.
Доказательство. Пусть дан контекстно-свободный язык L
над алфавитом {a}. Согласно лемме 9.1 найдётся такое натураль-
ное число p, что м ножество {k ∈ N | ak ∈ L} является объедине-
нием некоторого семейства арифметических прогрессий, причём
у каждой прогрессии первый член и шаг не больше числа p. Так
41
Основные свойства контекстно-свободных языков
как существует лишь конечное число прогрессий натуральных
чисел с таким ограничением, то рассматриваемое семейство ко-
нечно. Следовательно, язык L является автоматным (используем
пример 2.14).
9.2. Свойства замкнутости
класса линейных языков
[АхоУль, 2.6.4]
Пример 9.4. Пусть Σ = {a, b, c}. Язык {ucuR | u ∈ {a, b}∗}
является линейным, так как он порождается грамматикой
S → aSa, S → bSb, S → c.
Пример 9.5. Рассмотрим алфавит Σ = {a, b, c}. Язык
{ambnck | 0 m < n, k 0} является линейным, так как он
порождается грамматикой S → Sc, S → T , T → aT b, T → Tb,
T → b.
Теорема 9.6. Если L1 и L2 — линейные языки над алфави-
том Σ, то L1 ∪ L2 тоже линейный язык.
Доказательство. Пусть язык L1 порождается грамматикой
N1,Σ, P1, S1
 и L2 порождается грамматикой N2,Σ, P2, S2
,
где N1 ∩ N2 = ∅. Тогда L1 ∪ L2 порождается грамматикой
N1 ∪ N2 ∪ {T },Σ, P1 ∪ P2 ∪ {T → S1, T → S2}, T
, где
T /∈ N1 ∪ N2 ∪ Σ.
Пример 9.7. Рассмотрим алфавит Σ = {a, b, c}. Язык L =
= Σ∗ − {anbncn | n 0} является линейным, поскольку L =
= L1 ∪ L2 ∪ (Σ∗ − L3), где языки L1 = {ambnck | m = n, k 0}
и L2 = {ambnck | n = k, m 0} являются линейными, а язык
L3 = {ambnck | m 0, n 0, k 0} является автоматным, и
можно применить теоремы 9.6, 3.8, 2.31 и лемму 1.68.
Упражнение 9.8. Пусть Σ = {a, b, c}. Является ли линейным
язык Σ∗ − {ucu | u ∈ {a, b}∗}?
Ответ. Да. Идею доказательства можно найти в [Гин, с. 106].
Упражнение 9.9. Пусть Σ = {a, b, c}. Является ли линейным
язык Σ∗ − {ucuR | u ∈ {a, b}∗}?
Ответ. Да.
42
Основные свойства контекстно-свободных языков
9.3. Свойства замкнутости
класса контекстно-свободных языков
[ГроЛан, 7.3.1–7.3.3], [Лал, с. 300–301], [ХопМотУль, 7.3.1–7.3.3], [АхоУль,
2.6.2], [Гин, 1.7], [Гла, 4.3], [ГорМол, с. 423–424], [LewPap2, 3.5]
Теорема 9.10. Если L — контекстно-свободный язык, то
L∗ тоже контекстно-свободный язык.
Доказательство. Пусть язык L порождается граммати-
кой N,Σ, P, S
. Тогда язык L∗ порождается грамматикой
N ∪ {T },Σ, P ∪ {T → ST, T → ε}, T
, где T /∈ N ∪ Σ.
Теорема 9.11. Если L1 и L2 — контекстно-свободные язы-
ки над алфавитом Σ, то L1 · L2 тоже контекстно-свободный
язык.
Доказательство. Пусть язык L1 порождается грамматикой
N1,Σ, P1, S1
 и L2 порождается грамматикой N2,Σ, P2, S2
,
где N1 ∩ N2 = ∅. Тогда L1 · L2 порождается грамматикой
N1∪N2∪{T },Σ, P1∪P2∪{T → S1S2}, T
, гдеT /∈ N1∪N2∪Σ.
Теорема 9.12. Если L1 и L2 — контекстно-свободные язы-
ки над алфавитом Σ, то L1∪L2 тоже контекстно-свободный
язык.
Доказательство. Пусть язык L1 порождается грамматикой
N1,Σ, P1, S1
 и L2 порождается грамматикой N2,Σ, P2, S2
,
где N1 ∩ N2 = ∅. Тогда L1 ∪ L2 порождается грамматикой
N1 ∪ N2 ∪ {T },Σ, P1 ∪ P2 ∪ {T → S1, T → S2}, T
, где
T /∈ N1 ∪ N2 ∪ Σ.
Теорема 9.13. Если L — контекстно-свободный язык, то
LR тоже контекстно-свободный язык.
9.4. Пересечение и дополнение
контекстно-свободных языков
[Гин, 3.2], [АхоУль, 2.6.2], [ХопМотУль, 7.3.4], [Гла, 4.3], [Лал, с. 300–301],
[LewPap2, 3.5], [ГроЛан, 7.3.4, 7.3.5], [ГорМол, с. 424], [Рей, с. 87–88]
Теорема 9.14. Неверно, что для любых контекстно-сво-
бодных языков L1 и L2 язык L1 ∩ L2 тоже контекстно-сво-
бодный.
43
Основные свойства контекстно-свободных языков
Доказательство. Положим L1 = {ambmcn | m 0, n 0}
и L2 = {ambncn | m 0, n 0}. В прим ере 9.2 было доказано,
что язык L1 ∩ L2 не является контекстно-свободным.
Теорема 9.15. Неверно, что для любого контекстно-сво-
бодного языка L ⊆ Σ∗ язык Σ∗ − L тоже контекстно-свобод-
ный.
Доказательство. Положим L = Σ∗ − {anbncn | n 0}, где
Σ = {a, b, c}. В прим ере 9.7 было доказано, что язык L является
линейным(и следовательно, контекстно-свободным).
9.5. Пересечение контекстно-свободного
языка с автоматным языком
[Гин, 3.2], [АхоУль, 2.6.2], [ХопМотУль, 7.3.4], [Гла, 5.2], [Лал, с. 301],
[LewPap2, 3.5], [ГроЛан, 10.6.3], [ТраБар, 1.12], [Рей, с. 87–88]
Теорема 9.16. Если L1 — контекстно-свободный язык
и L2 — автоматный язык, то язык L1 ∩ L2 является
контекстно-свободным.
Доказательство. Пусть N,Σ, P, S
 — контекстно-свободная
грамматика, порождающая язык L1. Без ограничения общности
можно считать, что множество P содержит только правила
вида A → a и A → α, где A ∈ N, a ∈ Σ и α ∈ N∗
(в силу теоремы 8.8). Пусть Q,Σ,Δ, I, F
 — конечный автомат,
распознающий язык L2. Без ограничения общности можно
считать, что для каждого перехода p, x, q
 ∈ Δ выполняется
равенство |x| = 1 (см. лемму 2.30).
Построимк онтекстно-свободную грамматику N,Σ, P, S
, по-
рождающую язык L1 ∩ L2. Положим
N = {S} ∪ (Q × N × Q),
P = {S → p, S, q
 | p ∈ I, q ∈ F} ∪
∪ { p,A, q
 → a | p, a, q
 ∈ Δ, (A → a) ∈ P} ∪
∪ { p0,A, pn
 → p0,B1, p1
 . . . pn−1,Bn, pn
 |
(A → B1 . . . Bn) ∈ P, p0 ∈ Q, . . . , pn ∈ Q},
где S — новый символ (не принадлежащий множеству Q×N×Q).
44
Основные свойства контекстно-свободных языков
Пример 9.17. Пусть Σ = {a, b, c}. Рассмотрим контекст-
но-свободный язык L1, порождаемый грамматикой S → a,
S → bS, S → cSS, и автоматный язык L2, заданный ко-
нечнымавт оматом M = Q,Σ,Δ, I, F
, где Q = {1, 2},
Δ = { 1, a, 2
, 1, c, 2
, 2, a, 1
, 2, b, 1
}, I = {1} и F = {2}.
Тогда язык L1 ∩ L2 порождается контекстно-свободной грамма-
тикой S → S12, S12 → a, S21 → a, S21 → bS11, S22 → bS12,
S11 → cS21S11, S11 → cS22S21, S12 → cS21S12, S12 → cS22S22.
Здесь S11, S12, S21 и S22 соответствуют символам 1, S, 1
,
1, S, 2
, 2, S, 1
 и 2, S, 2
 из доказательства теоремы 9.16.
Замечание 9.18*. Если L1 — линейный язык и L2 —
автоматный язык, то язык L1 ∩ L2 является линейным.
Пример 9.19*. Пусть Σ = {a, b}. Рассмотрим линей-
ный язык L1, порождаемый грамматикой S → aaSaa,
S → bSb, S → ε, и автоматный язык L2, заданный ко-
нечнымавт оматом M = Q,Σ,Δ, I, F
, где Q = {1, 2, 3},
Δ = { 1, a, 1
, 1, b, 1
, 1, a, 2
, 2, b, 3
, 3, a, 3
, 3, b, 3
},
I = {1} и F = {3}. Тогда язык L1 ∩ L2 порождается кон-
текстно-свободной грамматикой S → S13, S11 → aaS11aa,
S12 → aaS11aa, S13 → aaS13aa, S13 → aaS23aa, S33 → aaS33aa,
S11 → bS11b, S13 → bS13b, S13 → bS12b, S23 → bS33b,
S33 → bS33b, S11 → ε, S33 → ε. Эту грамм атику м ожно упро-
стить, заменив S11 и S33 на один символ.
9.6*. Теорема Парика
[Гин, 5.1, 5.2], [Гла, 4.3], [LewPap1, 3.5.2], [АхоУль, с. 239]
Замечание 9.20. В этомр азделе предполагается, что за-
фиксирован некоторый линейный порядок на алфавите Σ. Пусть
Σ = {a1, . . . , an}.
Определение 9.21. Через ΨΣ будемобоз начать функцию
из Σ∗ в Nn, определённую следующимоб разом: ΨΣ(w)
|w|a1 , . . . , |w|an

. Аналогично, каждому языку L ⊆ Σ∗
ставится в соответствие множество ΨΣ(L) ⊆ Nn, определённое
так: ΨΣ(L) {ΨΣ(w) | w ∈ L}.
Пример 9.22. Пусть Σ = {a1, a2} и L = {a1, a1a2a2, a2a2a1}.
Тогда ΨΣ(L) = { 1, 0
, 1, 2
}.
45
Основные свойства контекстно-свободных языков
Определение 9.23. Пусть B ⊆ Nn и P ⊆ Nn. Тогда через
L(B,P) обозначается множество
{b + p1 + . . . + pk | b ∈ B, k 0, p1, . . . , pk ∈ P}.
Множество B называется системой предпериодов множества
L(B,P). Множество P называется системой периодов множе-
ства L(B,P).
Определение 9.24. Множество A ⊆ Nn называется линей-
ным (linear), если A = L (B,P) для некоторых конечных мно-
жеств B и P.
Определение 9.25. Множество A ⊆ Nn называется полули-
нейным (semilinear), если оно является объединениемк онечного
числа линейных множеств.
Теорема 9.26 (Теорема Пар´ика). Если язык L ⊆ Σ∗ явля-
ется контекстно-свободным, то множество ΨΣ(L) является
полулинейным.
Доказательство можно найти в [Гин, с. 207–211].
Пример 9.27. Пусть Σ = {a, b}. Рассмотрим язык L =
= {ambn | m > n или m простое}. Можно проверить, что
множество ΨΣ(L) не является полулинейным. Следовательно,
язык L не является контекстно-свободным.
Теорема 9.28. Если множество A ⊆ Nn является полу-
линейным, то существует такой автоматный язык L, что
A = ΨΣ(L).
Доказательство. Докажемэ то для произвольного линейно-
го множества A = L (B,P) (на полулинейные множества утвер-
ждение распространяется по теореме 3.1). Рассмотрим конечный
автомат M = Q,Σ,Δ, I, F
, где Q = {1, 2}, I = {1}, F = {2} и
Δ = { 1, ak1
1 . . .akn
n , 2
 | k1, . . . , kn
 ∈ B}∪
∪ { 2, ak1
1 . . . akn
n , 2
 | k1, . . . , kn
 ∈ P}.
Очевидно, ΨΣ(L(M)) = L(B,P).
Замечание 9.29. Теорема 9.3 является следствием тео-
рем9.26 и 9.28.
46
Автоматы с магазинной памятью
10. Автоматы с магазинной памятью
10.1. Определение
автомата с магазинной памятью
[Гин, 2.4], [АхоУль, 2.5.1, 2.5.2], [ХопМотУль, 6.1, 6.2], [Гла, 4.5], [ГлаМел,
с. 136–149], [ГорМол, с. 418–420], [СокКушБад, с. 36–38], [ЛПИИ, 5.2.5, 5.2.6],
[Бра, с. 109–116], [ГроЛан, 9.1, 9.2], [LewPap2, 3.3], [Sip, 2.2], [Рей, с. 79–83]
Определение 10.1. Автомат с магазинной памятью
(МП-автомат, магазинный автомат, стековый автомат)
(pushdown automaton) — это шестёрка M = Q,Σ, Γ,Δ, I, F
,
где Q, Σ, Γ и Δ — конечные м ножества, I ⊆ Q, F ⊆ Q и
Δ ⊆ (Q × Σ∗ × Γ∗) × (Q × Γ∗). Здесь Q — множество состо-
яний, Σ — входной алфавит, Γ — алфавит магазинной па-
мяти (stack alphabet), Δ — множество переходов (transition
relation), элементы I называются начальными состояниями, эле-
менты F — заключительными или допускающими состояниями.
Пример 10.2. Пусть Q = {1, 2}, Σ = {a, b}, Γ = {A,B},
Δ = { 1, a, ε
, 1,A

, 1, b, ε
, 1,B

, 1, ε, ε
, 2, ε

,
2, a,A
, 2, ε

, 2, b,B
, 2, ε

},
I = {1}, F = {2}. Тогда Q,Σ, Γ,Δ, I, F
 — МП-автомат.
Определение 10.3. Конфигурацией МП-автомата называет-
ся любая тройка q,w,α
, где q ∈ Q, w ∈ Σ∗, α ∈ Γ∗.
Определение 10.4. Определимна множестве всех кон-
фигураций МП-автомата M = Q,Σ, Γ,Δ, I, F
 бинарное
отношение
M
(такт работы) следующим образом. Если
p, x, β
, q, γ

 ∈ Δ, w ∈ Σ∗ и α ∈ Γ∗, то p, xw, βα
 
M
q,w, γα
.
Замечание 10.5. Обычно из контекста ясно, о какомМ П-ав-
томате идёт речь. Тогда вместо
M
будемп исать .
Пример 10.6. Для МП-автомата Q,Σ, Γ,Δ, I, F
 из
примера 10.2 выполняется 1, abba, ε
  1, bba,A
 и
1, abba, ε
  2, abba, ε
.
Определение 10.7. Бинарное отношение
∗
определяется как
рефлексивное, транзитивное замыкание отношения .
47
Автоматы с магазинной памятью
Пример 10.8. Для МП-автомата Q,Σ, Γ,Δ, I, F
 из
примера 10.2 выполняется 1, abba, ε
 ∗ 1, ba,BA
 и
1, abba, ε
 ∗ 2, ε, ε
.
Лемма 10.9. Если p, x, α1
 ∗ q, ε,α2
 и q, y,α2α3
 ∗
∗ r, ε, α4
, то p, xy, α1α3
 ∗ r, ε, α4
.
Доказательство. Индукция по количеству тактов в вычис-
лении, ведущеми з конфигурации p, x, α1
 в конфигурацию
q, ε,α2
.
Определение 10.10. Слово w ∈ Σ∗ допускается МП-автома-
том M = Q,Σ, Γ,Δ, I, F
, если найдутся такие состояния s ∈ I
и q ∈ F, что s,w, ε
 ∗ q, ε, ε
.
Определение 10.11. Язык, распознаваемый МП-автома-
том , —м ножество всех слов, допускаем ых этим МП-автоматом .
Язык, распознаваемый МП-автоматом M, обозначается L(M).
Замечание 10.12. Обычно в учебниках используется более
узкое определениеМП-автомата, но это не меняет класса языков,
распознаваемых МП-автоматами.
Пример 10.13. Пусть M — МП-автомат из примера 10.2.
Тогда L(M) = {uuR | u ∈ {a, b}∗}.
Пример 10.14. Пусть Σ = {a, b, c}. Рассмотрим МП-автомат
M = Q,Σ,Γ,Δ, I,F
, где Q = {1, 2, 3, 4, 5}, Γ = {A,B}, I = {1},
F = {4, 5} и
Δ ={ 1, a, ε
, 1,A

, 1, b, ε
, 1,B

,
1, c, ε
, 2, ε

,
2, a,A
, 2, ε

, 2, b,B
, 2, ε

,
2, a,B
, 3, ε

, 2, b,A
, 3, ε

,
2, ε,A
, 4, ε

, 2, ε,B
, 4, ε

,
2, b, ε
, 5, ε

, 2, a, ε
, 5, ε

,
3, a, ε
, 3, ε

, 3, b, ε
, 3, ε

,
3, ε, ε
, 4, ε

,
4, ε,A
, 4, ε

, 4, ε,B
, 4, ε

,
5, a, ε
, 5, ε

, 5, b, ε
, 5, ε

}.
Тогда L(M) = {ucv | u ∈ {a, b}∗, v ∈ {a, b}∗, u = vR}.
48
Автоматы с магазинной памятью
Определение 10.15. Два МП-автомата эквивалентны, если
они распознают один и тот же язык.
Замечание 10.16. В данномпо собии не рассматривают-
ся преобразователи с магазинной памятью (pushdown transducer)
— обобщение автоматов с магазинной памятью по-
средствомд обавления “выходного” потока (см. [Гин, 3.5]
или [АхоУль, 3.1.4]).
Замечание 10.17. Некоторые авторы изменяют определе-
ние допускаемых слов следующим образом: слово w допуска-
ется МП-автоматом Q,Σ, Γ,Δ, I, F
, если найдутся такие со-
стояния s ∈ I и q ∈ F и последовательность α ∈ Γ∗, что
s,w, ε
 ∗ q, ε,α
. Такое определение не изменяет класса язы-
ков, распознаваемых МП-автоматами.
Замечание 10.18. Некоторые авторы добавляют в определе-
ние МП-автомата седьмую компоненту — Z0, называем ую мар-
кером магазинной памяти (start pushdown symbol), и изменя-
ют определение допускаемых слов следующим образом: слово w
допускается МП-автоматом Q,Σ, Γ,Δ, I, F, Z0
, если найдутся
такие состояния s ∈ I и q ∈ F, что s,w,Z0
 ∗ q, ε, ε
. Такое
определение не изменяет класса языков, распознаваемых МП-ав-
томатами.
Замечание 10.19. Класс языков, распознаваемых МП-авто-
матами, не изменится также, если использовать следующую
естественную комбинацию двух предыдущих определений: сло-
во w допускается МП-автоматом Q,Σ, Γ,Δ, I, F, Z0
, если най-
дутся такие состояния s ∈ I и q ∈ F и последовательность
α ∈ Γ∗, что s,w,Z0
 ∗ q, ε,α
.
Замечание 10.20. Некоторые авторы добавляют в опре-
деление МП-автомата маркер магазинной памяти Z0, отбра-
сывают множество F и изменяют определение допускаемых
слов следующимо бразом: слово w допускается МП-автоматом
Q,Σ, Γ,Δ, I, Z0
, если найдутся такие состояния s ∈ I и q ∈ Q,
что s,w,Z0
 ∗ q, ε, ε
. И это не изменяет класса языков, распо-
знаваемых МП-автоматами.
49
Автоматы с магазинной памятью
10.2. Характеризация
контекстно-свободных языков
[Sip, 2.2], [Гин, 2.5], [АхоУль, 2.5.3], [ХопМотУль, 6.3], [Гла, 4.5], [ГлаМел,
с. 149–150], [ГорМол, с. 420–422], [Бра, с. 116–120], [ГроЛан, 9.3, 15.3],
[LewPap2, 3.4], [Рей, с. 84–87]
Теорема 10.21. Если язык L является контекстно-сво-
бодным, то существует МП-автомат, распознающий этот
язык.
Доказательство. Пусть язык L порождается грамматикой
N,Σ, P, S
, в которой каждое правило имеет вид A → wβ, где
A ∈ N, w ∈ Σ∗ и β ∈ N∗ (в силу теоремы 8.8 такая грамматика
существует). Положим Γ = N, Q = {1, 2}, I = {1}, F = {2} и
Δ ={ 1, ε, ε
, 2, S

} ∪ { 2, w,A
, 2, β

 | (A → wβ) ∈ P}.
Можно доказать, что 2, u, S
 ∗ 2, ε, α
 тогда и только тогда,
когда существует левосторонний вывод S
∗⇒
lm
uα (здесь u ∈ Σ∗ и
α ∈ N∗).
Пример 10.22. Пусть Σ = {a, b, c, d}. Контекстно-свободная
грамматика S → SS, S → a, S → bcTS, T → cSS, T → dT T и
МП-автомат {1, 2},Σ, {S, T },Δ, {1}, {2}
, где
Δ = { 1, ε, ε
, 2, S

, 2, ε, S
, 2, SS

, 2, a, S
, 2, ε

,
2, bc,S
, 2, TS

, 2, c, T
, 2, SS

, 2, d, T
, 2, TT

},
задают один и тот же язык.
Лемма 10.23. Каждый МП-автомат эквивалентен неко-
торому МП-автомату Q,Σ, Γ,Δ, I, F
, где |I| = 1, |F| = 1 и
каждый переход p, x, β
, q, γ

 ∈ Δ удовлетворяет требова-
ниям |x| 1 и |β| + |γ| = 1.
Пример 10.24. Рассмотрим МП-автомат M =
= Q,Σ, Γ,Δ, I, F
, где Q = I = F = {1}, Σ = {a, b, c, d},
Γ = {A,B},
Δ = { 1, a,A
, 1, ε

, 1, b,B
, 1, ε

,
1, c, ε
, 1,A

, 1, d,A
, 1,AB

}.
50
Автоматы с магазинной памятью
Он эквивалентен МП-автомату M = Q ,Σ, Γ,Δ , I, F
, где Q =
= {1, 2, 3} и
Δ = { 1, a,A
, 1, ε

, 1, b,B
, 1, ε

, 1, c, ε
, 1,A

,
1, d,A
, 2, ε

, 2, ε, ε
, 3,B

, 3, ε, ε
, 1,A

}.
Пример 10.25. Рассмотрим МП-автомат M =
= Q,Σ, Γ,Δ, I, F
, где Q = I = F = {1}, Σ = {a, b, c}, Γ =
= {A}, Δ = { 1, a, ε
, 1,A

, 1, b,A
, 1, ε

, 1, c, ε
, 1, ε

}.
Он эквивалентен МП-автомату M = Q ,Σ, Γ ,Δ , I, F
, где
Q = {1, 2}, Γ = {A, T } и
Δ = { 1, a, ε
, 1,A

, 1, b,A
, 1, ε

,
1, c, ε
, 2, T

, 2, ε, T
, 1, ε

}.
Пример 10.26. Рассмотрим МП-автомат M =
= Q,Σ, Γ,Δ, I, F
, где Q = I = F = {1, 2}, Σ = {a, b}, Γ = {C},
Δ = { 1, a, ε
, 1, C

, 1, b, C
, 1, ε

,
2, b, ε
, 2, C

, 2, a, C
, 2, ε

}.
Он эквивалентен МП-автомату {0, 1, 2, 3},Σ, Γ,Δ , {0}, {3}
, где
Δ = Δ∪ { 0, ε, ε
, 1, ε

, 0, ε, ε
, 2, ε

,
1, ε, ε
, 3, ε

, 2, ε, ε
, 3, ε

}.
Теорема 10.27. Если язык L распознаётся некоторым
МП-автоматом, то L является контекстно-свободным.
Доказательство. Пусть язык L распознаётся МП-автоматом
Q,Σ, Γ,Δ, I, F
. Без ограничения общности можно считать, что
I = {qs}, F = {qa} и каждый переход p, x, β
, q, γ

 ∈ Δ
удовлетворяет требованию |β| + |γ| = 1. Построим иско-
мую контекстно-свободную грамматику N,Σ, P, S
, положив
N = {Ap,q | p ∈ Q, q ∈ Q}, S = Aqs,qa и
P = {Ap,p → ε | p ∈ Q} ∪
∪ {Ap,t → xAq,ryAs,t | p, x, ε
, q,C

 ∈ Δ,
r, y,C
, s, ε

 ∈ Δ, C ∈ Γ, t ∈ Q}.
Можно доказать, что p, x, ε
 ∗ q, ε, ε
 тогда и только тогда,
когда Ap,q
∗⇒
x (здесь x ∈ Σ∗).
51
Автоматы с магазинной памятью
Пример 10.28. МП-автомат M = {1, 2},Σ, Γ,Δ, {1}, {2}
,
где Σ = {a, b}, Γ = {D,E},
Δ = { 1, ab, ε
, 1,E

, 1, aa,E
, 1, ε

, 1, b, ε
, 2,D

,
2, a, ε
, 1,D

, 2, ε,D
, 2, ε

, 2, b,E
, 2, ε

},
и контекстно-свободная грамматика S → abT aaS, S → abSbU,
S → bUU , T → abT aaT , T → ε, U → aSU, U → ε задают один и
тот же язык. Здесь S, T и U соответствуют символам A1,2, A1,1
и A2,2 из доказательства теоремы 10.27.
10.3*. Автоматы с магазинной памятью
с однобуквенными переходами
[АхоУль, с. 218], [Гла, 6.2], [Бра, с. 124–125]
Теорема 10.29. Каждый МП-автомат эквивалентен неко-
торому МП-автомату Q,Σ, Γ,Δ, I, F
, где |Q| = 2 и каж-
дый переход p, x, β
, q, γ

 ∈ Δ удовлетворяет требованиям
|x| = 1, |β| 1 и |γ| 2.
Доказательство. Пусть исходнымМ П-автоматомраспо -
знаётся контекстно-свободный язык L ⊆ Σ∗. Согласно теоре-
м е 8.16 язык L − {ε} порождается некоторой контекстно-сво-
бодной грамматикой N,Σ, P, S
, в которой каждое прави-
ло имеет вид A → aγ, где A ∈ N, a ∈ Σ, γ ∈ N∗ и
|γ| 2. Аналогично тому, как было сделано при доказатель-
стве теоремы 10.21, положим Γ = N, Q = {1, 2}, I = {1},
Δ={ 2, a,A
, 2,γ

 | (A→aγ)∈P}∪{ 1, a,ε
, 2,γ

 | (S→aγ)∈P},
F =

{1, 2}, если ε ∈ L,
{2}, если ε /∈ L.
Теорема 10.30. Каждый МП-автомат эквивалентен неко-
торому МП-автомату Q,Σ, Γ,Δ, I, F
, в котором каждый пе-
реход p, x, β
, q, γ

 ∈ Δ удовлетворяет требованиям |x| = 1,
|β| 1 и |γ| 1.
Доказательство. Пусть исходнымМ П-автоматомраспо зна-
ётся контекстно-свободный язык L ⊆ Σ∗. Согласно теорем е8.16
52
Дополнительные свойства контекстно-свободных языков
язык L−{ε} порождается некоторой контекстно-свободной грам-
матикой G = N,Σ, P, S
, в которой каждое правило имеет один
из следующих трёх видов: A → a, A → aB, A → aBC, где
A ∈ N, B ∈ N, C ∈ N, a ∈ Σ. Легко добиться того, чтобы B = S
и C = S в правилах грамматики G.
Положим Q = N ∪ {⊥}, где ⊥ /∈
N. Далее, положим Γ = N,
I = {S}, F=

{S, ⊥}, если ε ∈ L,
{⊥}, если ε /∈ L,
Δ = { A, a, ε
, B,C

 | (A → aBC) ∈ P} ∪
∪ { A, a, ε
, B, ε

 | (A → aB) ∈ P} ∪
∪ { A, a,D
, D, ε

 | (A → a) ∈ P, D ∈ N} ∪
∪ { A, a, ε
, ⊥, ε

 | (A → a) ∈ P}.
11. Дополнительные свойства
контекстно-свободных языков
11.1*. Деление контекстно-свободных языков
[АхоУль, с. 236], [LewPap2, с. 148–149]
Теорема 11.1. Пусть L1 — контекстно-свободный язык над
алфавитом Σ и L2 — автоматный язык над алфавитом Σ.
Тогда язык {x ∈ Σ∗ | (∃y ∈ L2) xy ∈ L1} является контекст-
но-свободным.
Доказательство. Пусть Q1,Σ, Γ1,Δ1, I1, F1
 — МП-авто-
мат, распознающий язык L1. Без ограничения общности можно
считать, что для каждого перехода p, x, β
, q, γ

 ∈ Δ1 выпол-
няется неравенство |x| 1.
Пусть Q2,Σ,Δ2, I2, F2
 — конечный автомат, распознаю-
щий язык L2. Без ограничения общности можно считать, что
Q1 ∩(Q1×Q2) = ∅ и для каждого перехода p, x, q
 ∈ Δ2 выпол-
няется равенство |x| = 1.
53
Дополнительные свойства контекстно-свободных языков
Тогда язык {x ∈ Σ∗ | (∃y ∈ L2) xy ∈ L1} распознаётся
МП-автоматом Q,Σ, Γ1,Δ, I, F
, где Q = Q1∪(Q1×Q2), I = I1,
F = F1 × F2 и
Δ =Δ1 ∪
∪ { p, ε, ε
, p1, p2
, ε

 | p1 ∈ Q1, p2 ∈ I2} ∪
∪ { p1, p2
, ε, β
, q1, q2
, γ

 | p1, a, β
, q1, γ

 ∈ Δ1,
p2, a, q2
 ∈ Δ2 для некоторого a ∈ Σ} ∪
∪ { p1, p2
, ε, β
, q1, p2
,γ

 | p1, ε, β
, q1,γ

∈Δ1, p2∈Q2}.
Упражнение 11.2. Существует ли такой контекстно-свобод-
ный язык L ⊆ Σ∗, что язык
Subw(L) {w | w — подслово некоторого слова из L}
не является контекстно-свободным?
Ответ. Нет. Положив в теореме 11.1 L1 = L и L2 = Σ∗, получим ,
что множество всех префиксов слов из языка L является
контекстно-свободным. То же верно для множества суффиксов.
Далее рассуждаем, как в упражнении 3.7.
11.2. Гомоморфизмы
и контекстно-свободные языки
[АхоУль, 2.6.2], [ХопМотУль, 7.3.5], [Гла, 4.2], [LewPap2, с. 148]
Теорема 11.3. Для любого гомоморфизма h: Σ∗
1
→ Σ∗
2 и
контекстно-свободного языка L ⊆ Σ∗
1 язык h(L) является
контекстно-свободным.
Доказательство. Приведёмдо казательство, основанное на
МП-автоматах, хотя эту теорему легко доказать и с помощью
контекстно-свободных грамматик. Пусть язык L распознаётся
МП-автоматом Q,Σ1, Γ,Δ, I, F
. Тогда язык h(L) распознаётся
МП-автоматом Q,Σ2, Γ,Δ , I, F
, где
Δ = { p, h(x), β
, q, γ

 | p, x, β
, q, γ

 ∈ Δ}.
54
Дополнительные свойства контекстно-свободных языков
Пример 11.4. Пусть Σ1 = {a, b, c} и Σ2 = {a, b}. Рассмот-
римк онтекстно-свободный язык L, порождаемый грамматикой
S → aSSc, S → b, и гом ом орфизм h: Σ∗
1
→ Σ∗
2, заданный равен-
ствами h(a) = a, h(b) = bba и h(c) = a. Тогда язык h(L) порож-
дается контекстно-свободной грамматикой S → aSSa, S → bba.
Теорема 11.5. Для любого гомоморфизма h: Σ∗
1
→ Σ∗
2 и
контекстно-свободного языка L ⊆ Σ∗
2 язык h−1(L) является
контекстно-свободным.
Доказательство. Обозначим
A = {x ∈ Σ∗
2
| x h(a) для некоторого a ∈ Σ1}.
Пусть язык L распознаётся МП-автоматом Q,Σ2, Γ,Δ, I, F
.
Без ограничения общности можно считать, что для каждого
перехода p, x, β
, q, γ

 ∈ Δ выполняется неравенство |x| 1.
Можно проверить, что язык h−1(L) распознаётся МП-автоматом
Q ,Σ1, Γ,Δ , I , F
, где Q = A×Q, I = {ε}× I, F = {ε} × F
и
Δ = { ε, p
, a, ε
, h(a), p
, ε

 | a ∈ Σ1, p ∈ Q} ∪
∪ { xw, p
, ε, β
, w, q
, γ

 | p, x, β
, q, γ

∈Δ, xw∈A}.
Пример 11.6. Пусть Σ1 = {c, d, e} и Σ2 = {a, b}. Рассмотрим
гомоморфизм h: Σ∗
1
→ Σ∗
2, заданный равенствами h(c) = aa,
h(d) = b и h(e) = bba. Пусть контекстно-свободный язык L
распознаётся МП-автоматом Q,Σ2, Γ,Δ, I, F
, где Q = {p},
Γ = {A}, Δ = { p, a, ε
, p,A

, p, b,A
, p, ε

}, I = {p}
и F = {p}. Тогда язык h−1(L) распознаётся МП-автоматом
Q ,Σ1, Γ,Δ , I , F
, где Q = {pε, pa, paa, pb, pba, pbba}, I = {pε},
F = {pε} и
Δ = { pε, c, ε
, paa, ε

, pε, d, ε
, pb, ε

, pε, e, ε
, pbba, ε

,
pa, ε, ε
, pε,A

, paa, ε, ε
, pa,A

, pb, ε,A
, pε, ε

,
pba, ε,A
, pa, ε

, pbba, ε,A
, pba, ε

}.
Язык h−1(L) также порождается контекстно-свободной грам-
матикой S → ε, S → cTUdS , T → ε, T → cTUU , U → dT ,
U → eT .
55
Дополнительные свойства контекстно-свободных языков
11.3*. Представления контекстно-свободных
языков посредством гомоморфизмов
[Сал, с. 103–109, 115], [Лал, с. 331–333], [Гла, 6.5], [ГроЛан, 15.2]
Теорема 11.7. Рассмотрим алфавит Σ0 = {a1, a2, b1, b2, c}
и язык L0 ⊆ Σ∗
0, порождаемый контекстно-свободной грам-
матикой G0: S → Cb1b2b1RC, C → c, C → cDC, D → A,
D → AD, A → a1, A → a2, A → b1, A → b2, R → ε, R → Ta1Tb1,
R → Ta2Tb2, T → R, T → RCC.
Произвольный язык L ⊆ Σ∗ является контекстно-свобод-
ным тогда и только тогда, когда существует такой гомо-
морфизм h: Σ∗ → Σ∗
0, что L = h−1(L0) или L = h−1(L0 ∪ {ε}).
Доказательство. Достаточность следует из теоремы 11.5.
Приведёмте перь идею доказательства необходимости (полное
доказательство можно найти в [Сал, с. 103–109]).
Пусть дан произвольный контекстно-свободный язык L. Со-
гласно теореме 8.16 язык L − {ε} порождается некоторой кон-
текстно-свободной грамматикой {A1, . . .,An},Σ, P,A1
, в ко-
торой каждое правило имеет один из следующих трёх видов:
Ai → a, Ai → aAj , Ai → aAjAk, где a ∈ Σ.
Определимвс помогательную функцию ¯h, ставящую в соот-
ветствие каждому символу из Σ конечный язык над алфавитом
Σ0 следующимо бразом:
¯h
(a) = {b1bi
2b1 | (Ai → a) ∈ P} ∪
∪ {b1bi
2b1a1aj
2a1 | (Ai → aAj) ∈ P} ∪
∪ {b1bi
2b1a1ak2
a1a1aj
2a1 | (Ai → aAjAk) ∈ P}.
Искомый гомоморфизм h определяется так: если ¯h(a) =
= {w1, w2, . . . , wk}, то положим h(a) = cw1cw2c . . . cwkc.
Пример 11.8. Пусть Σ = {d, f, g}. Рассмотрим язык L,
порождаемый грамматикой A1 → f, A1 → dA1A2, A2 → fA3,
A2 → fA2A3, A3 → g. Тогда L = h−1(L0), где гом ом орфизм h
задан равенствами
h(d) = cb1b2b1a1a2a2a1a1a2a1c,
h(f) = cb1b2b1cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,
h(g) = cb1b2b2b2b1c.
56
Детерминированные контекстно-свободные языки
Рассмотрим, например, слово dffg ∈ L. Проверим , ч то
слово h(dffg) выводится в грамматике G0 из теоре-
мы 11.7. Очевидно, S
∗⇒
cb1b2b1Rc. С помощью послед-
них пяти правил грамматики G0 можно вывести, что R
∗⇒
∗⇒
a1a22
a21
a2a1CCb1b2b1CCb1b22
b1a1a32
a1CCb1b32
b1. Осталось най-
ти такие шесть выводимых из C слов w1, . . ., w6, что h(dffg)=
= cb1b2b1a1a22
a21
a2a1w1w2b1b2b1w3w4b1b22
b1a1a32
a1w5w6b1b32
b1c.
Подходят слова w1 = w2 = w6 = c, w3 =
= cb1b22
b1a1a32
a1cb1b22
b1a1a32
a21
a22
a1c, w4 = cb1b2b1c, w5 =
= cb1b22
b1a1a32
a21
a22
a1c.
Теорема 11.9 (Теорема Хомского –Шютценберже). Про-
извольный язык L ⊆ Σ∗ является контекстно-свобод-
ным тогда и только тогда, когда существуют на-
туральное число n, автоматный язык L1 над алфа-
витом Σ(D)
n = {a1, b1, a2, b2, . . . , an, bn} и гомоморфизм
h:

Σ(D)
n
∗
→ Σ∗, такие что L = h(L(D)
n ∩ L1), где L(D)
n — язык
Дика над 2n буквами.
Доказательство можно найти в [Лал, с. 331–333].
12. Детерминированные
контекстно-свободные языки
12.1. Детерминированные автоматы
с магазинной памятью
[АхоУль, 2.5.4], [ХопМотУль, 6.4], [ГорМол, с. 423], [СокКушБад, с. 38], [Рей,
с. 88–89]
Определение 12.1. Будемго ворить, что два перехода МП-ав-
томата p1, x1, β1
, q1, γ1

 и p2, x2, β2
, q2, γ2

 являются сов-
местными, если
1) p1 = p2,
2) x1 x2 или x2 x1,
3) β1 β2 или β2 β1.
Определение 12.2. МП-автомат называется детерминиро-
ванным (deterministic), если он имеет ровно одно начальное со-
стояние и все переходы этого автомата попарно несовместны.
57
Детерминированные контекстно-свободные языки
Пример 12.3. МП-автомат M из примера 10.28 не явля-
ется детерминированным, так как переходы 2, a, ε
, 1,D

 и
2, ε,D
, 2, ε

 совместны.
Определение 12.4. Язык L над алфавитом Σ называется
детерминированным контекстно-свободным языком, если су-
ществует детерминированный МП-автомат, распознающий язык
L · {$} над алфавитом Σ∪{$}, где $ — дополнительный символ,
не принадлежащий множеству Σ.
Пример 12.5. Пусть Σ = {a, b}. Язык L =
= {ambn | m = n или n = 0} — детерминированный кон-
текстно-свободный язык, так как язык L · {$} порождается де-
терминированным МП-автоматом (хотя язык L не порождается
никаким детерминированным МП-автоматом).
12.2*. Свойства класса детерминированных
контекстно-свободных языков
[АхоУль, 2.5.4, 2.6.4], [Рей, с. 90–93], [ХопМотУль, 6.4], [ГорМол, с. 424–425],
[LewPap2, с. 160–161]
Теорема 12.6. Каждый автоматный язык является детер-
минированным контекстно-свободным языком.
Теорема 12.7. Язык L ⊆ Σ∗ является детерминированным
контекстно-свободным языком тогда и только тогда, когда
найдётся такой детерминированный МП-автомат M =
= Q ,Σ, Γ ,Δ , I , F
, что
L={w∈Σ∗ | s,w,ε
 ∗ q,ε,α
 для некоторых s∈I

, q∈F

, α∈Γ ∗}.
Теорема 12.8. Пусть L — детерминированный контекст-
но-свободный язык. Тогда язык L не является существенно
неоднозначным.
Теорема 12.9. Дополнение каждого детерминированного
контекстно-свободного языка является детерминированным
контекстно-свободным языком.
Доказательство можно найти в [Гин, с. 110–116] или [АхоУль,
с. 212–217].
58
Алгоритмические проблемы
Пример 12.10. Язык L = {akbmcn | k = m или m = n}
над алфавитом {a, b, c} не является детерминированным кон-
текстно-свободнымя зыком, так как его дополнение не является
контекстно-свободным.
Теорема 12.11. Неверно, что для любых детерминирован-
ных контекстно-свободных языков L1 и L2 язык L1 ∩ L2
тоже является детерминированным контекстно-свободным
языком.
Доказательство. Достаточно рассмотреть детерминирован-
ные контекстно-свободные языки L1 и L2 из доказательства тео-
ремы 9.14.
Теорема 12.12. Неверно, что для любых детерминирован-
ных контекстно-свободных языков L1 и L2 язык L1 ∪ L2
тоже является детерминированным контекстно-свободным
языком.
Доказательство. Утверждение следует из теорем12 .9 и 12.11
и закона де Моргана.
13. Алгоритмические проблемы
13.1. Машины Тьюринга
[АхоУль, 0.4.6], [ХопМотУль, 8.2, 9.2.1], [Гла, 1.4], [Бра, с. 86–91], [Sip, 3.1, 3.2]
Определение 13.1. Машина Тьюринга — это сем ё рка
M = Q,Σ, Γ, b0,Δ, I, F
, где Q, Γ и Δ — конечные м но-
жества, Σ ⊂ Γ, b0 ∈ Γ − Σ, I ⊆ Q, F ⊆ Q и
Δ ⊆ ((Q − F) × Γ) × (Q × Γ × {−1, 0, 1}). Здесь Q — множе-
ство состояний, Σ — входной алфавит (внешний алфавит),
Γ — ленточный алфавит (tape alphabet), b0 — бланк (пробел,
пустой символ) (blank symbol), Δ — множество переходов, I —
множество начальных состояний, F — множество заключи-
тельных состояний.
Определение 13.2. Конфигурацией машины Тьюринга назы-
вается любая четвёрка x, q, a, y
, где x ∈ Γ∗, q ∈ Q, a ∈ Γ,
y ∈ Γ∗.
59
Алгоритмические проблемы
Определение 13.3. Определимна множестве всех конфигу-
раций машины Тьюринга M бинарное отношение
M
(такт ра-
боты) следующим образом.
Если p, a
, q, c, 0

 ∈ Δ, то x, p, a, y
  x, q, c, y
 для всех
x ∈ Γ∗ и y ∈ Γ∗.
Если p, a
, q, c, 1

 ∈ Δ, то x, p, a, dy
  xc, q, d, y
 и
x, p, a, ε
  xc, q, b0, ε
 для всех x ∈ Γ∗, y ∈ Γ∗ и d ∈ Γ.
Если p, a
, q, c,−1

 ∈ Δ, то xd, p, a, y
  x, q, d, cy
 и
ε, p, a, y
  ε, q, b0, cy
 для всех x ∈ Γ∗, y ∈ Γ∗ и d ∈ Γ.
Замечание 13.4. Если из контекста ясно, о какой машине
Тьюринга идёт речь, вместо
M
будемпи сать просто .
Определение 13.5. Как и для МП-автомата, для машины
Тьюринга бинарное отношение ∗ определяется как рефлексивное,
транзитивное замыкание отношения .
Замечание 13.6. Если x1, q1, a1, y1
 ∗ x2, q2, a2, y2
, то для
любых k ∈ N и l ∈ N найдутся такие m ∈ N и n ∈ N, что
bk0
x1, q1, a1, y1bl
0

 ∗ bm0
x2, q2, a2, y2bn0

.
Замечание 13.7. Конфигурацию bm0
x, q, a, ybn0

 иногда изоб-
ражают сокращённо xa
q
y.
Пример 13.8. Рассмотрим машину Тьюринга M =
= Q,Σ, Γ, b0,Δ, I, F
, где Q = {0, 1, 2, 3}, Σ = {a},
Γ = {a, b}, b0 = b, I = {0}, F = {3}, Δ =
= { 0, b
, 1, b, 1

, 1, a
, 2, b, 1

, 2, a
, 1, b, 1

, 1, b
, 3, b, 0

}.
Можно проверить, что для любого k ∈ N выполняется следую-
щее: b0
ak+1 a1
ak, a1
ak+2
∗
a1
ak, a1
a2k+1
∗
b3
.
Определение 13.9. Машина Тьюринга Q,Σ, Γ, b0,Δ, I, F

называется детерминированной, если м ножество I содержит
ровно один элемент и для каждой пары p, a
 ∈ (Q − F) × Γ
существует не более одной тройки q, c, k
 ∈ Q × Γ × {−1, 0, 1}
со свойством p, a
, q, c, k

 ∈ Δ.
Пример 13.10. Машина Тьюринга из примера 13.8 является
детерминированной.
Определение 13.11. Пусть f — частичная функция из Σ∗
в Σ∗. Машина Тьюринга M = Q,Σ, Γ, b0,Δ, I, F
 вычисляет
(computes) функцию f тогда и только тогда, когда для каждого
слова w ∈ Σ∗
60
Алгоритмические проблемы
1) если f(w) не определено, то не существует таких p ∈ I,
q ∈ F, a ∈ Γ, x ∈ Γ∗, y ∈ Γ∗, что ε, p, b0, w
 ∗ x, q, a, y
,
2) если f(w) = z, то для некоторых p ∈ I, q ∈ F, m ∈ N и
n ∈ N ε, p, b0, w
 ∗ bm0
, q, b0, zbn0

.
Пример 13.12. Машина Тьюринга из примера 13.8 вычисляет
следующую частичную функцию:
f(an) =

ε, если число n чётно,
не определено, если число n нечётно.
Пример 13.13*. Рассмотрим детерминированную машину
Тьюринга Q,Σ, Γ, b0,Δ, I, F
, где Σ = {a}, Γ = {a, b}, b0 = b,
Q = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, I = {1}, F = {7} и
Δ = { 1, b
, 2, b, 1

, 2, b
, 7, b, 0

, 2, a
, 3, a,−1

,
3, b
, 3, a, 1

, 3, a
, 4, b, 1

,
4, b
, 5, b,−1

, 4, a
, 8, a, 0

,
5, b
, 6, b,−1

, 6, a
, 6, a,−1

, 6, b
, 7, b, 0

,
8, b
, 8, b, 1

, 8, a
, 9, a, 1

,
9, a
, 9, a, 1

, 9, b
, 10, b,−1

,
10, a
, 11, b,−1

, 11, b
, 11, b, 0

, 11, a
, 12, b,−1

,
12, a
, 12, a,−1

, 12, b
, 13, b,−1

,
13, b
, 13, b,−1

, 13, a
, 14, b,−1

,
14, a
, 8, a, 1

, 14, b
, 3, b, 1

}.
Можно проверить, что для любых i ∈ N, j ∈ N и k ∈ N
выполняется следующее: b1
ak+2
∗
aba
8
ak, abj+1a8
a2
∗
b7
aj+2,
abj+1a8
ak+3
∗
aj+2ba
8
ak, ai+2bj+1a8
ak+2
∗
ai+1bj+2a8
ak,
abj+1a8
ak+2j+5
∗
abj+2a8
ak. Следовательно,b1
ai+(j+2)2 ∗ abj+1a8
ai+2
и b1
a(k+2)2 ∗
b7
ak+2. Рассматриваемая машина Тьюринга вычисля-
ет следующую частичную функцию:
f(an) =

a
√
n, если
√
n ∈ N,
не определено, если
√
n /∈ N.
61
Алгоритмические проблемы
Определение 13.14. Говорят, что детерминированная маши-
на Тьюринга Q,Σ, Γ, b0,Δ, {qs}, {qa, qr}
 с выделеннымс остоя-
нием qa разрешает (decides) язык L ⊆ Σ∗, если
1) для каждого слова w ∈ L найдутся такие m ∈ N и n ∈ N,
что ε, qs, b0, w
 ∗ bm0
, qa, b0, bn0

,
2) для каждого слова w ∈ Σ∗ − L найдутся такие m ∈ N и
n ∈ N, что ε, qs, b0, w
 ∗ bm0
, qr, b0, bn0

.
Состояние qa называется допускающим (accept state), состоя-
ние qr называется отвергающим (reject state).
Пример 13.15. Рассмотрим детерминированную ма-
шину Тьюринга M = Q,Σ, Γ, b0,Δ, {qs}, {qa, qr}
, где
Q = {0, 1, 2, 3, 4, 5}, Σ = {a}, Γ = {a, b}, b0 = b, qs = 0, qa = 4,
qr = 5 и
Δ = { 0, b
, 1, b, 1

,
1, a
, 2, b, 1

, 2, a
, 3, b, 1

, 3, a
, 1, b, 1

,
1, b
, 4, b, 0

, 2, b
, 5, b, 0

, 3, b
, 5, b, 0

}.
Эта машина Тьюринга разрешает язык {a3n | n ∈ N}.
Определение 13.16. Язык L над алфавитом Σ назы-
вается разрешимым или рекурсивным (decidable, recursive),
если существует детерминированная машина Тьюринга
Q,Σ, Γ, b0,Δ, {qs}, {qa, qr}
 (с выделеннымс остоянием qa), ко-
торая разрешает язык L.
Определение 13.17. Говорят, что машина Тьюринга M =
= Q,Σ, Γ, b0,Δ, {qs}, {qa}
 допускает (accepts) слово w ∈ Σ∗,
если для некоторых m ∈ N и n ∈ N ε, qs, b0, w
 ∗ bm0
, qa, b0, bn0

.
Определение 13.18. Язык, допускаемый машиной Тьюрин-
га M, — это язык, состоящий из всех допускаемых данной ма-
шиной Тьюринга слов.
Определение 13.19. Язык называется перечислимым (или
рекурсивно перечислимым, или полуразрешимым) (recursively
enumerable), если существует детерминированная машина Тью-
ринга, допускающая этот язык.
Замечание 13.20. В определении 13.19 можно отбросить
требование детерминированности машины Тьюринга.
62
Алгоритмические проблемы
Теорема 13.21. Каждый разрешимый язык является пере-
числимым.
Доказательство. Пусть дана машина Тьюринга M =
= Q,Σ, Γ, b0,Δ, {qs}, {qa, qr}
 с выделеннымс остоянием qa,
которая разрешает язык L ⊆ Σ∗. Тогда машина Тьюринга
M = Q,Σ, Γ, b0,Δ, {qs}, {qa}
 допускает язык L.
Пример 13.22*. Если в машине Тьюринга из примера 13.13*
заменить переход 6, a
, 6, a,−1

 на 6, a
, 6, b,−1

, то полу-
чится машина Тьюринга, допускающая язык {an2 | n ∈ N}. Сле-
довательно, этот язык является перечислимым. Можно доказать,
что он даже является разрешимым.
13.2. Массовые задачи
[АхоУль, 0.4.5], [Гла, 8.1], [Sip, 4.2], [ХопМотУль, 9.2]
Определение 13.23. Массовой задачей (problem) называет-
ся бесконечная серия “однотипных” индивидуальных задач (instance),
каждая из которых имеет определённый ответ. С каж-
дой массовой задачей связана некоторая фиксированная схема
кодирования (encoding scheme), которая отображает индивиду-
альные задачи в их коды — слова в некоторомфи ксированном
алфавите. При этомтреб уется, чтобы множество кодов всех ин-
дивидуальных задач было разрешимым.
Определение 13.24. Задачей распознавания (decision problem)
называется массовая задача, в которой ответами индивиду-
альных задач могут быть только “да” и “нет” (то есть существует
только два возможных ответа).
Пример 13.25. Зафиксируемнек оторый алфавит Σ. Рассмот-
римс ледующие однотипные индивидуальные задачи: даны два
слова x ∈ Σ∗ и y ∈ Σ∗, необходимо выяснить, является ли сло-
во x подсловомсл ова y.
Пусть # — новый символ, не принадлежащий алфавиту Σ.
Кодоми ндивидуальной задачи про конкретные слова x и y будем
считать слово x#y в алфавите Σ ∪ {#}.
Эта массовая задача является задачей распознавания.
63
Алгоритмические проблемы
Определение 13.26. Алгоритмическая проблема — пробле-
ма, в которой требуется найти алгоритм для решения массовой
задачи. Если такой алгоритмс уществует, то данная проблема на-
зывается алгоритмически разрешимой или просто разрешимой
(decidable, solvable), иначе — алгоритмически неразрешимой
(undecidable, unsolvable).
Замечание 13.27. Алгоритмическая проблема, относящаяся
к некоторой задаче распознавания, алгоритмически разрешима
тогда и только тогда, когда разрешимо множество кодов индиви-
дуальных задач с ответом“ да”.
Пример 13.28. Рассмотрим массовую задачу из приме-
ра 13.25. Соответствующая алгоритмическая проблема разреши-
ма, так как разрешим язык {x#uxv | x ∈ Σ∗, u ∈ Σ∗, v ∈ Σ∗}.
Пример 13.29. Зафиксируемнек оторый алфавит Σ. Рассмот-
римс ледующие однотипные индивидуальные задачи: дана по-
рождающая грамматика G = {A1, . . . , An},Σ, P,A1
, необходи-
мо выяснить, является ли эта грамматика праволинейной.
Для полной строгости необходимо договориться, как коди-
ровать грамматику G в виде слова. Например, можно исполь-
зовать алфавит Σ ∪ {♥, ♠, 0, 1}, где ♥, ♠, 0, 1 — дополни-
тельные символы, не принадлежащие множеству Σ. Вспомога-
тельный символ Ai заменим на слово, состоящее из симво-
ла ♥ и кода числа i в двоичной системе счисления. В каж-
домп равиле α → β добавимс имвол ♠ на месте → и по-
сле слова β. Кодом грамматики G будемсч итать результат
конкатенации кодов всех правил из множества P. Наприм ер,
грамматика A1 → a, A1 → A2A1, A2 → aA3, A3 → ε,
A3 → bA1 (над алфавитом Σ = {a, b}) кодируется словом
♥1♠a♠♥1♠♥10♥1♠♥10♠a♥11♠♥11♠♠♥11♠b♥1♠.
Легко понять, что соответствующая алгоритмическая пробле-
ма (проблема проверки праволинейности) разрешима.
Теорема 13.30. Существует такая машина Тьюринга над
однобуквенным алфавитом Σ = {a}, что язык, допускаемый
этой машиной Тьюринга, неразрешим.
Доказательство. Доказательство существования перечис-
лимого неразрешимого множества можно найти, например,
в [ХопМотУль, 9.2].
64
Алгоритмические проблемы
13.3*. Грамматики типа 0
[ЛПИИ, 5.2.8], [Гла, 1.4], [АхоУль, с. 50, 120]
Теорема 13.31. Класс языков, порождаемых грамматика-
ми типа 0, совпадает с классом перечислимых языков.
Упражнение 13.32. Выводимо ли слово aab в грам матике
S → Sb, S → ST, S → SU, S → ε, Ta → aaT , Tb → ab,
Uaaa → aaU, Uab → b?
Ответ. Да. S
∗⇒
UUTTTb
∗⇒
UUaaaaaaab
∗⇒
aab.
Замечание 13.33. Неизвестно, порождает ли грамматика
R → Ra, R → S, S → Sb, S → ST, S → SU, S → ε, Ta → aaT ,
Tb → ab, Uaaa → aaU, Uab → b все слова в алфавите {a, b}.
Упражнение 13.34. Пусть Σ = {a, b, c, d, e}. Рассмотрим
грамматику R → ccdcdcddccddcdccca, ac → ca, ca → ac, bc → cb,
cb → bc, ad → da, da → ad, bd → db, db → bd, ce → eca, eca → ce,
de → edb, edb → de, cca → ccae, ccae → cca. Выводим оли в ней
слово ccdcdcddccddcdcccabba?
Ответ. Да. Пусть w = ccdcdcddccddcdccc. Тогда wa
∗⇒
∗⇒
wabababba
∗⇒
wabbababababba
∗⇒
wabbababababbababba
∗⇒
∗⇒
wabbabababba
∗⇒
wabba.
Упражнение 13.35. Является ли разрешимым язык, порож-
даемый грамматикой S → cS, S → dS, S → aa, ac → ca,
ca → ac, bc → cb, cb → bc, ad → da, da → ad, bd → db,
db → bd, cdc → cdcR, Rcca → ccR, Rddb → ddR, Rcdd → cddT ,
Tcc → ccaT , Tdd → ddbT , Tcdc → cdc?
Ответ. Нет. Неразрешимо пересечение этого языка с языком
cdc((cc+dd)∗cdd(cc+dd)∗cdc)∗(a+b)∗. В пересечении можно зако-
дировать любую грамматику типа 0 (вспомогательный символ Ai
заменяется на ccd2icc, в каждомправ иле α → β добавляется сло-
во cdd на месте → и слово cdc после слова β).
Определение 13.36. Порождающая грамматика в нор-
мальной форме — порождающая грамматика, в которой каждое
правило имеет вид A → a, A → BC или AB → ε, где A ∈ N,
B ∈ N, C ∈ N, a ∈ Σ.
Теорема 13.37. Каждая порождающая грамматика экви-
валентна некоторой порождающей грамматике в нормальной
форме.
65
Алгоритмические проблемы
13.4. Проблема соответствий Поста
[Sip, 5.2], [Гин, 4.2], [Сал, 4.6], [АхоУль, 0.4.6], [ГорМол, с. 375], [ХопМотУль,
9.4], [ГроЛан, 6.2.3]
Определение 13.38. Постовской системой соответствия
над алфавитом Σ называется пара конечных последовательно-
стей ((x1, . . . , xn), (y1, . . . , yn)), где xi ∈ Σ∗ и yi ∈ Σ∗ для всех i.
Замечание 13.39. Систему ((x1, . . . , xn), (y1, . . . , yn)) иногда
изображают в виде

x1
y1

, . . . ,

xn
yn

.
Определение 13.40. Решением (match) постовской системы
соответствия ((x1, . . . , xn), (y1, . . . , yn)) называется непустая по-
следовательность индексов (i1, . . . , ik), удовлетворяющая усло-
вию xi1 . . . xik = yi1 . . . yik, где 1 ij n для каждого j.
Пример 13.41. Пусть Σ = {a, b, c}. Рассмотрим постовскую
систему соответствия

aab
a

,

 a
aa

,

caa
bc

. Последовательность
(2, 1, 3, 2, 2) является решениемэ той системы.
Упражнение 13.42. Пусть Σ = {a, b, c, 0, 1,♦,♥, ♠}. Суще-
ствует ли решение у постовской системы соответствия

 a♠
a♠aba♥1aca♠a

,

 ab
ba

,

ac
ca

,

a♠
♠a

,

 a♠
ba♠a

,

 a♠
♠aba

,

a♥1ab
♦a

,

 a♥1ac
ca♥10a

,

 aba♥10ab
♥10abaca

,

aca♥10ab
♥10acaca

,

a♥10ac
ca♥11a

,

a♥11ac
ca♥1a

,

a♦ab
♦a

,

a♦ac
♦a

,

aba♦
♦a

,

aca♦
♦a

,

a♦a♠a♠
♠

?
Ответ. Да. Например, (1, 2, 8, 5, 2, 10, 4, 2, 11, 3, 4, 2, 3, 12, 5,
2, 3, 3, 7, 4, 2, 3, 16, 4, 2, 16, 4, 15, 4, 17).
Определение 13.43. Проблемой соответствий Поста (Post
correspondence problem) называется проблема нахождения алго-
ритма, выясняющего для каждой постовской системы соответ-
ствия, существует ли решение этой системы.
Теорема 13.44. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольной постовской системе
соответствия над алфавитом Σ узнать, имеет ли она реше-
ние. (То есть проблема соответствий Поста неразрешима.)
Доказательство можно найти в [ХопМотУль, 9.4].
66
Алгоритмически разрешимые проблемы
14. Алгоритмически разрешимые
проблемы
14.1. Неукорачивающие грамматики
[ГроЛан, 12.1], [АхоУль, с. 117, 119], [Бра, с. 37–38], [Гла, 3.2, 3.5], [Лал, с. 161],
[ГлаМел, с. 54], [ГорМол, с. 361–362], [LewPap2, с. 271], [КукБей, с. 271–272],
[ЛПИИ, 5.2.7]
Определение 14.1. Порождающая грамматика называется
неукорачивающей, если для каждого правила (α → β) ∈ P
выполняется неравенство |α| |β|.
Теорема 14.2. Существует алгоритм, позволяющий по
произвольной неукорачивающей грамматике G и по слову w
узнать, верно ли, что w ∈ L(G).
Теорема 14.3. Каждая контекстная грамматика являет-
ся неукорачивающей. Каждая неукорачивающая грамматика
эквивалентна некоторой контекстной грамматике.
Пример 14.4. Грамматика S → ASTA, S → AbA, A → a,
bT → bb, AT → TA эквивалентна контекстной грамматике из
примера 1.59.
14.2*. Линейно ограниченные автоматы
[Бра, с. 91–100], [Гин, с. 107–108], [Гла, 3.2], [АхоУль, с. 120], [ГроЛан, 12.2],
[Sip, с. 177], [LewPap2, с. 271]
Определение 14.5. Машина Тьюринга Q,Σ, Γ, b0,Δ, I, F

называется линейно ограниченным автоматом (linear bounded
automaton), если не существует таких w ∈ Σ∗, x ∈ Γ∗, q ∈ Q,
a ∈ Γ и y ∈ Γ∗, что ε, p, b0, wb0
 ∗ x, q, a, y
 и |xay| > |b0wb0|.
Теорема 14.6. Язык L, не содержащий пустого слова, по-
рождается некоторой неукорачивающей грамматикой тогда
и только тогда, когда существует линейно ограниченный ав-
томат (в общем случае недетерминированный), который до-
пускает язык L.
Замечание 14.7. Неизвестно, верен ли аналог теоремы 14.6
для детерминированных линейно ограниченных автоматов.
67
Алгоритмически разрешимые проблемы
Теорема 14.8. Класс языков, порождаемых неукорачиваю-
щими грамматиками, замкнут относительно операций объ-
единения, пересечения и дополнения.
14.3. Проблема выводимости слова
[Гин, 4.1, 1.8], [ХопМотУль, 7.4.4], [Лал, с. 305], [ГроЛан, 7.2.4], [Sip, 4.1],
[LewPap2, 3.6]
Теорема 14.9. Существует алгоритм, позволяющий по
произвольной контекстно-свободной грамматике G узнать,
верно ли, что ε ∈ L(G).
Теорема 14.10. Существует алгоритм, позволяющий по
произвольной контекстно-свободной грамматике G и по сло-
ву w узнать, верно ли, что w ∈ L(G).
14.4. Проблема пустоты языка
[Гин, 4.1, 1.4], [АхоУль, 2.4.2], [ХопМотУль, 7.4.3], [Гла, 4.2], [ГроЛан, 7.2.3],
[Лал, с. 305], [Sip, 4.1], [Рей, с. 65–66]
Теорема 14.11. Существует алгоритм, позволяющий по
произвольной контекстно-свободной грамматике G узнать,
верно ли, что L(G) = ∅.
Доказательство. Удалими з G все бесполезные символы,
кроме начального символа (как в доказательстве теоремы 8.2).
Если полученная грамматика содержит хотя бы одно правило, то
L(G) = ∅.
14.5. Проблема бесконечности языка
[Гин, 4.1], [ГроЛан, 7.2.3], [Гла, 4.2], [Лал, с. 297–299, 305], [Бра, с. 65–70],
[Рей, с. 71]
Теорема 14.12. Существует алгоритм, позволяющий по
произвольной контекстно-свободной грамматике G узнать,
является ли бесконечным язык L(G).
68
Алгоритмически неразрешимые проблемы
Пример 14.13. Рассмотрим контекстно-свободную граммати-
ку G из примера 8.3. Чтобы выяснить, является ли язык L(G)
бесконечным, удалим сначала все бесполезные символы. Затем
устранимв се ε-правила. Так как W
∗⇒
Z и Z
∗⇒
W, то м ож-
но всюду заменить W на Z. Получится грамматика S → V Z,
T → aa, T → bb, V → aT b, V → bT a, Z → aab, Z → b, эк-
вивалентная исходной грамматике G. Очевидно, эта грам матика
не содержит “рекурсивных” нетерминальных символов. Следова-
тельно, язык L(G) является конечным.
14.6. Проблема равенства
автоматных языков
[Гин, 4.1], [АхоУль, 2.3.4], [Сал, с. 35], [ХопМотУль, 4.4.2], [ГроЛан, 10.4.5],
[ТраБар, 1.1, 1.4], [Sip, 4.1], [LewPap2, 2.6], [Рей, с. 62–63]
Теорема 14.14. Существует алгоритм, позволяющий по
произвольным двум праволинейным грамматикам G1 и G2
узнать, верно ли, что L(G1) ⊆ L(G2).
Теорема 14.15. Существует алгоритм, позволяющий по
произвольным двум праволинейным грамматикам G1 и G2
узнать, верно ли, что L(G1) = L(G2).
15. Алгоритмически неразрешимые
проблемы
15.1. Пересечение
контекстно-свободных языков
[Гин, 4.2], [ГроЛан, 8.1.1, 8.1.2], [АхоУль, с. 237], [Лал, с. 306]
Определение 15.1. Пусть Bx = (x1, . . . , xn), где xi ∈ {a, b}∗
для всех i. Рассмотрим алфавит Σ3 = {a, b, c}. Обозна-
чимч ерез G(Bx) линейную грамматику {S},Σ3, P, S
, где
P = {S → baiSxi | 1 i n} ∪ {S → baicxi | 1 i n}.
Обозначимч ерез L x язык, порождаемый грамматикой G(Bx).
69
Алгоритмически неразрешимые проблемы
Лемма 15.2. Язык L x ∩ L y является непустым тогда и
только тогда, когда постовская система соответствия (Bx, By)
имеет решение.
Пример 15.3. Рассмотрим постовскую систему соответствия

 b
bba

,

abbaa
a

(то есть n = 2, Bx = (b, abbaa) и By = (bba, a)). Решениями этой си-
стемы являются последовательности (1, 1, 2), (1, 1, 2, 1, 1, 2) и т. д.
Легко убедиться, что L x ∩L y = {(baababa)nc(bbabbaa)n | n 1}.
Теорема 15.4. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольным контекстно-свобод-
ным грамматикам G1 и G2 над алфавитом Σ узнать, верно
ли, что L(G1) ∩ L(G2) = ∅.
Доказательство. Сначала докажемутв ерждение теоремы
для случая |Σ| 3. Из леммы 15.2 следует, что если бы про-
блема распознавания свойства L(G1) ∩ L(G2) = ∅ для контекст-
но-свободных грамматик над алфавитом Σ была разрешима, то
проблема соответствий Поста тоже была бы разрешима. Поэтому
из неразрешимости проблемы соответствий Поста следует нераз-
решимость проблемы распознавания свойства L(G1)∩L(G2) = ∅
для контекстно-свободных грамматик над алфавитом Σ.
Чтобы доказать утверждение теоремы для случая |Σ| = 2
(например, Σ = {d, e}), достаточно заменить в определении G(Bx)
символ a на ede, сим вол b на edde и сим вол c на eddde.
Лемма 15.5. Язык L x ∩ L y является бесконечным тогда и
только тогда, когда постовская система соответствия (Bx, By)
имеет решение.
Доказательство. Если постовская система соответствия
имеет хотя бы одно решение, то она имеет бесконечно много
решений.
Теорема 15.6. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольным контекстно-свобод-
ным грамматикам G1 и G2 над алфавитом Σ узнать, явля-
ется ли бесконечным язык L(G1) ∩ L(G2).
70
Алгоритмически неразрешимые проблемы
15.2. Проблема однозначности
[Гин, 4.5], [АхоУль, 2.6.5], [ГроЛан, 8.2.4], [Лал, с. 307], [ХопМотУль, 9.5.2],
[Гла, 8.4]
Теорема 15.7. Пусть |Σ| 2. Тогда не существует алго-
ритма, позволяющего по произвольной контекстно-свободной
грамматике G над алфавитом Σ узнать, является ли грам-
матика G однозначной.
Доказательство. Рассмотрим язык L x ∪ L y. Следуя доказа-
тельству теоремы 9.12, построим грамматику G для этого язы-
ка, исходя из грамматик G(Bx) и G(By). Грам матика G является
неоднозначной тогда и только тогда, когда постовская система
соответствия (Bx, By) имеет решение.
15.3. Дополнение
контекстно-свободного языка
[Гин, 4.2], [ГроЛан, 8.1.4], [АхоУль, 2.6.3], [ХопМотУль, 9.5.3], [Sip, с. 181–182],
[Сал, 5.3], [LewPap2, 5.5], [Гла, 8.4]
Лемма 15.8. Рассмотрим алфавит Σ3 = {a, b, c}. Язык
Σ∗
3
−L x является контекстно-свободным.
Пример 15.9. Пусть Bx = (b, abbaa). Тогда язык Σ∗
3
− L x
над алфавитом Σ3 = {a, b, c} порождается контекстно-свободной
грамматикой S → ε, S → AW, S → bR, A → a, A → c,
B → b, B → c, Z → a, Z → B, W → ZW, W → ε,
Ua → WB, Ua → ε, Ub → WA, Ub → ε, R → ε, R → BW,
R → aaaW, R → a, R → aa, R → abRb, R → aabRabbaa,
R → acZWb, R → aacZWabbaa, R → aBT1, R → aaBT2,
T1 → Ub, T2 → Uabbaa, T2 → Ubbaa, T2 → Ubaa, T2 → Uaa,
T2 → Ua. Зам етим, что {w ∈ Σ∗
3
| Ti
∗⇒
w} = Σ∗
3
− (Σ∗
3
· {xi}) для
каждого i.
Язык Σ∗
3
− L x является даже линейным( чтобы получить
линейную грамматику, достаточно “раскрыть” вспомогательные
символы A, B и Z).
Замечание 15.10. Лемму 15.8 можно доказать, явно построив
контекстно-свободную грамматику (как в примере 15.9), а можно
и вывести из теоремы 12.9, проверив, что L x — детерминирован-
ный контекстно-свободный язык.
71
Алгоритмически неразрешимые проблемы
Определение 15.11. Пусть Σ3 = {a, b, c}, Bx = (x1, . . . , xn),
By = (y1, . . . , yn), где xi ∈ {a, b}∗ и yi ∈ {a, b}∗ для всех i.
Обозначимч ерез M x, y язык Σ∗
3
− (L x ∩L y).
Лемма 15.12. ЯзыкM x, y является контекстно-свободным.
Доказательство. M x, y = (Σ∗
3
−L x) ∪ (Σ∗
3
−L y).
Лемма 15.13. Дополнение языка M x, y является непустым
тогда и только тогда, когда постовская система соответ-
ствия (Bx, By) имеет решение.
Доказательство. Утверждение следует из леммы 15.2.
Теорема 15.14. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольной контекстно-свобод-
ной грамматике G над алфавитом Σ узнать, верно ли, что
L(G) = Σ∗.
Доказательство. Очевидно, L(G) = Σ∗ тогда и только тогда,
когда дополнение языка L(G) является пустым.
Теорема 15.15. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольным контекстно-свобод-
ным грамматикам G1 и G2 над алфавитом Σ узнать, верно
ли, что L(G1) = L(G2).
Доказательство. Утверждение следует из предыдущей тео-
ремы и примера 1.71.
Теорема 15.16. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольным контекстно-свобод-
ным грамматикам G1 и G2 над алфавитом Σ узнать, верно
ли, что L(G1) ⊆ L(G2).
Доказательство. Очевидно, Σ∗ ⊆ L(G) тогда и только тогда,
когда L(G) = Σ∗.
Лемма 15.17. Дополнение языка M x, y является бесконеч-
ным тогда и только тогда, когда постовская система соот-
ветствия (Bx, By) имеет решение.
Теорема 15.18. Пусть |Σ| 2. Тогда не существует алго-
ритма, позволяющего по произвольной контекстно-свободной
грамматике G над алфавитом Σ узнать, является ли беско-
нечным множество Σ∗ − L(G).
72
Алгоритмически неразрешимые проблемы
15.4. Проблема автоматности
[Гин, 4.2], [ГроЛан, 8.1.4], [Лал, с. 306], [АхоУль, с. 237], [ХопМотУль, 9.5.3],
[Гла, 8.4]
Лемма 15.19. Пусть Bx = (x1, . . . , xn), By = (y1, . . . , yn), где
xi ∈ {a, b}∗, yi ∈ {a, b}∗ и xiyi = ε для всех i. Тогда язык
M x, y является автоматным тогда и только тогда, когда
постовская система соответствия (Bx, By) не имеет решений.
Доказательство. Пусть (i1, . . . , ik) — решение постовской
системы соответствия (Bx, By), где xiyi = ε для всех i. Обозначим
u baikbaik−1 . . . bai1 , v xi1 . . . xik и L0 {u}∗ · {c} · {v}∗.
Легко проверить, что u = ε, v = ε и язык L0 является
автоматным. Очевидно, L x ∩ L y ∩ L0 = {umcvm | m > 0}.
Как было установлено в упражнении 3.13, язык L x ∩ L y ∩ L0
не является автоматным. Согласно теореме 3.8 язык L x ∩ L y не
является автоматным. Следовательно, и язык M x, y не является
автоматным.
Обратно, если постовская система соответствия (Bx, By) не
имеет решений, то M x, y = {a, b, c}∗, а этот язык является
автоматным.
Теорема 15.20. Пусть |Σ| 2. Тогда не существует алго-
ритма, позволяющего по произвольной контекстно-свободной
грамматике G над алфавитом Σ узнать, является ли авто-
матным язык L(G).
Доказательство. Докажемутв ерждение теоремы для слу-
чая |Σ| 3. Из леммы 15.19 следует, что если бы проблема
распознавания автоматности языка L(G) для контекстно-свобод-
ных грамматик над алфавитом Σ была разрешима, то также бы-
ла бы разрешима проблема соответствий Поста для постовских
системс оответствия ((x1, . . . , xn), (y1, . . . , yn)), где xi ∈ {a, b}∗,
yi ∈ {a, b}∗ и xiyi = ε для всех i. Но тогда была бы разрешима
проблема соответствий Поста для всех постовских систем соот-
ветствия над алфавитом {a, b} (если xiyi = ε для некоторого i,
то рассматриваемая постовская система соответствия имеет ре-
шение, а именно (i)).
73
Алгоритмически неразрешимые проблемы
15.5. Проблемы контекстно-свободности
[Гин, 4.2], [ГроЛан, 8.1.3, 8.1.4], [Лал, с. 306], [Гла, 8.4]
Определение 15.21. Пусть Σ3 = {a, b, c}, Bx = (x1, . . . , xn),
By = (y1, . . . , yn), где xi ∈ {a, b}∗ и yi ∈ {a, b}∗ для всех i.
Обозначимч ерез K x, y язык L x · {c} · LR
y .
Лемма 15.22. Язык K x, y является контекстно-свободным.
Доказательство. Утверждение следует из теорем9.13 и 9.11.
Лемма 15.23. Пусть Σ3 = {a, b, c}, Bx = (x1, . . . , xn),
By = (y1, . . . , yn), где xi ∈ {a, b}∗, yi ∈ {a, b}∗ и xiyi = ε для
всех i. Тогда язык K x, y ∩ {zczR | z ∈ Σ∗
3
} является контекст-
но-свободным тогда и только тогда, когда постовская систе-
ма соответствия (Bx, By) не имеет решений.
Доказательство. Пусть (i1, . . . , ik) — решение постов-
ской системы соответствия (Bx, By), где xiyi = ε для
всех i. Обозначим u baikbaik−1 . . . bai1 , v xi1 . . . xik и
L0 {u}∗ · {c} · {v}∗ · {c} · {vR}∗ · {c} · {uR}∗. Легко проверить,
что u = ε, v = ε и язык L0 является автоматным. Очевидно,
K x, y ∩ {zczR | z ∈ Σ∗
3
} ∩ L0 = {umcvmc(vR)mc(uR)m | m > 0}.
Можно доказать (наприм ер, используя лемм у 9.1), что язык
{umcvmc(vR)mc(uR)m | m > 0} не является контекстно-свобод-
ным. Согласно теореме 9.16 язык K x, y ∩{zczR | z ∈ Σ∗
3
} также не
является контекстно-свободным.
Теорема 15.24. Пусть |Σ| 2. Тогда не существует ал-
горитма, позволяющего по произвольным контекстно-свобод-
ным грамматикам G1 и G2 над алфавитом Σ узнать, явля-
ется ли контекстно-свободным язык L(G1) ∩ L(G2).
Доказательство. Достаточно построить по постовской си-
стеме соответствия (Bx, By), где Bx = (x1, . . . , xn), By = (y1, . . . , yn)
и для всех i выполняется xi ∈ {a, b}∗, yi ∈ {a, b}∗ и xiyi = ε,
контекстно-свободную грамматику G1, порождающую язык K x, y,
и контекстно-свободную грамматику G2, порождающую язык
{zczR | z ∈ Σ∗
3
}. В силу леммы 15.23 неразрешимость рассмат-
риваемой задачи сводится к неразрешимости проблемы соответ-
ствий Поста рассуждением, аналогичным приведённому в дока-
зательстве теоремы 15.20.
74
Литература
Лемма 15.25. Рассмотрим алфавит Σ3 = {a, b, c}. Язык
Σ∗
3
−(K x, y ∩{zczR | z ∈ Σ∗
3
}) является контекстно-свободным.
Доказательство. Обозначим L0 = {w ∈ Σ∗
3
| |w|c = 1}.
Язык Σ∗
3
− (K x, y ∩ {zczR | z ∈ Σ∗
3
}) м ожно представить в виде
объединения пяти контекстно-свободных языков
L1 = {w ∈ Σ∗
3
| |w|c = 3},
L2 = {v1cv2cv3cv4 | v1, v2, v3, v4 ∈ {a, b}∗
, v1 = vR
4
},
L3 = {v1cv2cv3cv4 | v1, v2, v3, v4 ∈ {a, b}∗
, v2 = vR
3
},
L4 = ((Σ∗
3
−L x) ∩ L0) · {c} · L0,
L5 = L0 · {c} · ((Σ∗
3
−L y)R ∩ L0).
Теорема 15.26. Пусть |Σ| 2. Тогда не существует алго-
ритма, позволяющего по произвольной контекстно-свободной
грамматике G над алфавитом Σ узнать, является ли кон-
текстно-свободным язык Σ∗ − L(G).
Доказательство. Рассмотрим алфавит Σ3 = {a, b, c}. До-
статочно построить по постовской системе соответствия (Bx, By),
где Bx = (x1, . . . , xn), By = (y1, . . . , yn) и для всех i выполняется
xi ∈ {a, b}∗, yi ∈ {a, b}∗ и xiyi = ε, контекстно-свободную грам-
матику G, порождающую язык Σ∗
3
− (K x, y ∩ {zczR | z ∈ Σ∗
3
}).
В силу леммы 15.25 неразрешимость рассматриваемой задачи
сводится к неразрешимости проблемы соответствий Поста рас-
суждением, аналогичным приведённому в доказательстве теоре-
м ы 15.20.
Литература
[АхоСетУль] Ахо А., Сети Р., Ульман Дж. Д. Компиляторы:
принципы, технологии и инструменты. М.: Вильямс,
2001. — 768 с.
[АхоУль] Ахо А., Ульман Дж. Теория синтаксического анализа,
перевода и компиляции. Т. 1: Синтаксический анализ.
М.: Мир, 1978. — 612 с.
[Бра] Братчиков И. Л. Синтаксис языков программирования.
М.: Мир, 1975. — 232 с.
75
Литература
[Гин] Гинзбург С. Математическая теория контекстно-свобод-
ных языков. М.: Мир, 1970. — 326 с.
[Гла] Гладкий А. В. Формальные грамматики и языки.
М.: Наука, 1973. — 368 с.
[ГлаМел] Гладкий А. В., Мельчук И. А. Элементы математической
лингвистики. М.: Наука, 1969. — 192 с.
[ГорМол] Гордеев А. В., Молчанов А. Ю. Системное программное
обеспечение. СПб.: Питер, 2001. — 736 с.
[ГроЛан] Гросс М., Лантен А. Теория формальных грамматик.
М.: Мир, 1971. — 294 с.
[КукБей] Кук Д., Бейз Г. Компьютерная математика. М.: Наука,
1990. — 384 с.
[Лал] Лаллеман Ж. Полугруппы и комбинаторные приложе-
ния. М.: Мир, 1985. — 440 с.
[ЛПИИ] Логический подход к искусственному интеллекту: От
классической логики к логическому программированию.
М.: Мир, 1990. — 432 с.
[Рей] Рейуорд-Смит В. Дж. Теория формальных языков.
Вводный курс. М.: Радио и связь, 1988. — 128 с.
[Сал] Саломаа А. Жемчужины теории формальных языков.
М.: Мир, 1986. — 159 с.
[СокКушБад] Соколов В. А., Кушниренко О. Б., Бадин Н. М. Фор-
мальные языки и грамматики. Задачи и упражнения.
Ярославль: Ярославский государственный университет,
1993. — 55 с.
[ТраБар] Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы
(поведение и синтез). М.: Наука, 1970. — 400 с.
[ХопМотУль] Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введе-
ние в теорию автоматов, языков и вычислений, 2-е изд.
М.: Вильям с, 2002. — 528 с.
[LewPap1] Lewis H. R., Papadimitriou C. H. Elements of the Theory
of Computation. Prentice Hall, 1981. — 466 p.
[LewPap2] Lewis H. R., Papadimitriou C. H. Elements of the Theory
of Computation. 2nd ed. Prentice Hall, 1998. — 361 p.
[Sip] Sipser M. Introduction to the Theory of Computation. PWS
Publishing company, 1997. — 396 p.
76
Оглавление
Схема зависимости глав
1
2

8

7
13

3


4







10


9



5


6

12



11








14


















15









 
Оглавление
1. Слова, языки и грам матики . . . . . . . . . . . . . . . . 3
1.1. Форм альные языки . . . . . . . . . . . . . . . . 3
1.2. Гом ом орфизмы . . . . . . . . . . . . . . . . . . . 6
1.3. Порождающие грам матики . . . . . . . . . . . . 6
1.4. Классы грам матик . . . . . . . . . . . . . . . . . 8
2. Конечные автом аты . . . . . . . . . . . . . . . . . . . . 10
2.1. Недетерминированные конечные автоматы . . . 10
2.2*. Конфигурации конечного автом ата . . . . . . . 12
2.3. Конечные автоматы с однобуквенными
переходам и. . . . . . . . . . . . . . . . . . . . . 13
2.4. Характеризация праволинейных языков . . . . . 14
2.5*. Нормальная форма праволинейных грамматик . 15
2.6. Детерминированные конечные автоматы . . . . 15
3. Основные свойства автом атных языков . . . . . . . . . 17
3.1. Свойства замкнутости класса автоматных
языков . . . . . . . . . . . . . . . . . . . . . . . 17
3.2. Пересечение и дополнение автоматных языков . 19
3.3. Лемма о разрастании для автоматных языков . 19
3.4. Прим еры неавтом атных языков . . . . . . . . . 20
77
Оглавление
4. Дополнительные свойства автоматных языков . . . . . 21
4.1. Гом ом орфизмы и автом атные языки . . . . . . . 21
4.2*. Длины слов в автом атных языках . . . . . . . . 21
5. Регулярные выражения . . . . . . . . . . . . . . . . . . 23
5.1. Определение регулярного выражения . . . . . . 23
5.2*. Свойства регулярных выражений . . . . . . . . 24
5.3. Теорем аКлини . . . . . . . . . . . . . . . . . . . 25
6. Синтаксические м оноиды . . . . . . . . . . . . . . . . . 27
6.1. Множества правых контекстов . . . . . . . . . . 27
6.2. Минимизация детерминированных конечных
автом атов . . . . . . . . . . . . . . . . . . . . . . 29
6.3. Множества двусторонних контекстов . . . . . . 30
7. Неоднозначность в контекстно-свободных грамматиках 32
7.1. Деревья вывода . . . . . . . . . . . . . . . . . . 32
7.2. Однозначные контекстно-свободные грамматики 33
7.3*. Однозначные праволинейные грамматики . . . . 34
7.4. Языки Дика и Лукасевича . . . . . . . . . . . . 35
8. Нормальные формы контекстно-свободных грамматик 35
8.1. Устранение бесполезных сим волов . . . . . . . . 35
8.2. Устранение ε-правил. . . . . . . . . . . . . . . . 36
8.3. Нормальная форма Хомского . . . . . . . . . . . 37
8.4*. Норм альная форм аГрейбах . . . . . . . . . . . 38
9. Основные свойства контекстно-свободных языков . . . 40
9.1. Лемма о разрастании для
контекстно-свободных языков . . . . . . . . . . 40
9.2. Свойства замкнутости класса линейных языков 42
9.3. Свойства замкнутости класса
контекстно-свободных языков . . . . . . . . . . 43
9.4. Пересечение и дополнение
контекстно-свободных языков . . . . . . . . . . 43
9.5. Пересечение контекстно-свободного языка
с автом атным языком . . . . . . . . . . . . . . . 44
9.6*. Теорем аПарика . . . . . . . . . . . . . . . . . . 45
10. Автом аты с м агазинной памятью. . . . . . . . . . . . . 47
10.1. Определение автомата с магазинной памятью . 47
10.2. Характеризация контекстно-свободных языков . 50
10.3*. Автоматы с магазинной памятью с
однобуквенными переходами . . . . . . . . . . . 52
78
Оглавление
11. Дополнительные свойства контекстно-свободных
языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
11.1*. Деление контекстно-свободных языков . . . . . 53
11.2. Гомоморфизмы и контекстно-свободные языки . 54
11.3*. Представления контекстно-свободных языков
посредством гом ом орфизм ов . . . . . . . . . . . 56
12. Детерминированные контекстно-свободные языки . . . 57
12.1. Детерминированные автоматы с магазинной
пам ятью. . . . . . . . . . . . . . . . . . . . . . . 57
12.2*. Свойства класса детерминированных
контекстно-свободных языков . . . . . . . . . . 58
13. Алгоритм ические проблем ы . . . . . . . . . . . . . . . 59
13.1. Машины Тьюринга . . . . . . . . . . . . . . . . 59
13.2. Массовые задачи . . . . . . . . . . . . . . . . . 63
13.3*. Грамматики типа 0 . . . . . . . . . . . . . . . . 65
13.4. Проблем асоответствий Поста . . . . . . . . . . 66
14. Алгоритмически разрешимые проблемы . . . . . . . . . 67
14.1. Неукорачивающие грам матики . . . . . . . . . . 67
14.2*. Линейно ограниченные автоматы . . . . . . . . 67
14.3. Проблем авыводим ости слова . . . . . . . . . . 68
14.4. Проблем апустоты языка . . . . . . . . . . . . . 68
14.5. Проблем абесконечности языка . . . . . . . . . 68
14.6. Проблема равенства автоматных языков . . . . 69
15. Алгоритмически неразрешимые проблемы . . . . . . . 69
15.1. Пересечение контекстно-свободных языков . . . 69
15.2. Проблем аоднозначности . . . . . . . . . . . . . 71
15.3. Дополнение контекстно-свободного языка . . . 71
15.4. Проблем аавтом атности . . . . . . . . . . . . . . 73
15.5. Проблем ыконтекстно-свободности . . . . . . . 74
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
79
Учебное издание
Пентус Анна Евгеньевна, Пентус Мати Рейнович
Теория формальных языков
M.: Издательство Центра прикладных исследований при
механико-математическом факультете МГУ, 80 стр.
Оригинал-макет подготовлен авторами в пакете LATEX.
Подписано в печать 08.12.2003.
Формат 60×90 1/16. Объём5 усл. печ. л.
Заказ 5. Тираж 100 экз.
Изд-во ЦПИ при механико-математическом факультете МГУ.
119992, Москва, Ленинские горы.
Лицензия на издательскую деятельность ИД №04059
от 20.02.2001.
Отпечатано с оригинал-макета на типографском оборудовании
механико-математического факультета и Франко-русского цен-
тра им . А. М. Ляпунова.