Математическая теория формальных языков

Математическая теория формальных языков

2-е издание, исправленное

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

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 519.713
ББК 5
П25
Математическая теория формальных языков / Пентус А.Е., Пентус М.Р. - M.: Национальный
Открытый Университет “ИНТУИТ”, 2016 (Основы информатики и математики)
ISBN 5-9556-0062-0

Курс посвящён классическому разделу математической лингвистики и теоретической информатики теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения,
конечные автоматы, автоматы с магазинной памятью.
Затронуты следующие классические темы математических основ информатики: праволинейные
грамматики, конечные автоматы, регулярные выражения, контекстно-свободные грамматики, деревья
разбора, нормальные формы грамматик, автоматы с магазинной памятью, детерминированные
контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно
ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга,
алгоритмические проблемы, связанные с грамматиками и автоматами. Особое внимание уделено
практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный
язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего
класса и наоборот, а также доказательству неразрешимости проблем, связанных с контекстносвободными грамматиками.

(c) ООО “ИНТУИТ.РУ”, 2006-2016
(c) Пентус А.Е., Пентус М.Р., 2006-2016

3

Предисловие

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

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

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

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

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

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

4

область использования контекстно-свободных грамматик - расширяемый язык
разметки (XML) и языки описания структуры XML-документа (например, язык DTD).

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

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

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

5

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

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

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

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

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

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

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

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

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

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

6

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

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

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

слов данной длины конечно, следовательно, 
 является объединением счетного числа

конечных множеств.

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

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

Определение 1.1.10. Если 
, то L называется языком (или формальным языком )

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

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

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

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

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

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

Определение 1.1.14. Если x - слово и 
, то через xn обозначается слово 
.

Положим 
 (знак 
 читается “равно по определению”). Всюду далее показатели

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

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

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

язык содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa, baaaa и т. д.

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

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

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

w.

Пример 1.1.20. Если 
, то |baaa|a = 3, |baaa|b = 1 и |baaa|c = 0.

7

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

.

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

?

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

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

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

случае 
?

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

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

Язык 
 называется конкатенацией языков L1 и L2.

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

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

l, |L2| = m, 

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

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

1}.

Упражнение 1.2.6. Пусть 
 и L = {aa,ab}. Найти L3.

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

Эта операция называется также звездочкой Клини (Kleene star, star operation).Пример
1.2.8. Если 
 и L = {aa,ab,ba,bb}, то

8

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

Верно ли, что 

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

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

Пример 1.2.12. Если w = baaca, то wR = acaab.

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

Язык LR называется обращением языка L.

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

?

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

 ), если y = xu для некоторого слова u.

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

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

состоящее из всех префиксов слов языка L:

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

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

 ), если y = ux для некоторого слова u.

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

состоящее из всех суффиксов слов языка L:

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

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

9

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

состоящее из всех подслов слов языка L. Множество Subw(L) называется множеством
подслов языка L.

Определение 1.2.22. Слово a1a2…an (длины 
 ) называется подпоследовательностью

(subsequence) слова y, если существуют такие слова u0, u1, …, un, что u0a1u1a2…anun =

y.

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

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

состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L)
называется множеством подпоследовательностей языка L.

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

Определение 1.2.26. Функция 
 называется биекцией (bijection), если каждый

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

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

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

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

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

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

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

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

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

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

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

Замечание 1.3.3. Пусть 
 и 
. Тогда отображение 
,

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

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

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

10