Составители:
123
Глава 9
ОПЕРАЦИИ НАД ЯЗЫКАМИ
§ 9.1. Замкнутость
относительно элементарных операций
В этой главе мы применяем операции объединения, конкатенации, обра-
щения, замыкания и т.д. к языкам разных типов. Интересно выяснить, какие
операции сохраняют классы языков, к которым они применяются, т.е.
отображают языки некоторого класса в тот же самый класс.
Есть ряд причин интересоваться этим вопросом. Во-первых, знание, сохра-
няет операция или нет данный класс языков, помогает характеризовать
этот
класс. Во-вторых, часто бывает легче узнать, что сложный язык относится к
некоторому классу, при помощи того факта, что эта принадлежность является
результатом различных операций над другими языками в данном классе, чем
путём непосредственного конструирования грамматики для этого языка.
В-третьих, знание, полученное из изучения операций над языками, может быть
использовано при доказательстве теорем, как это было сделано в гл. 7, где мы
показали, что класс рекурсивно перечислимых множеств строго содержит
рекурсивные множества, используя при доказательстве тот факт, что рекурсив-
ные множества замкнуты относительно дополнения.
Начнём с рассмотрения операций объединения, конкатенации, замыкания
Клини и обращения. Используем следующую лемму о “нормальной форме” для
контекстно-зависимых языков и языков типа 0.
Лемма 9.1. Каждый контекстно-зависимый язык порождается контек-
стно-зависимой
грамматикой, в которой все правила имеют форму α→β, где α
и β — цепочки, состоящие из одних только нетерминалов, либо форму A→ b,
где A — нетерминал, b — терминал. Каждый язык типа 0 порождается
грамматикой типа 0, правила которой имеют указанную форму.
Доказательство.
Пусть G =(V
N
, V
T
, P, S) — контекстно-зависимая
грамматика. Каждому a∈V
T
сопоставим новый символ X
a
. Рассмотрим грам-
матику где = V
N
∪ {X
a
| a∈V
T
}. Множество
включает все
правила вида X
a
→ a. Если α→β∈P, то α
1
→β
1
∈ , где цепочки α
1
и β
1
получаются из цепочек α и β путём замещения в них каждого терминала a
символом X
a
.
Доказательство тривиально, и мы оставляется его читателю в качестве
упражнения. Подобное же доказательство применимо к грамматикам типа 0.
Теорема 9.1 Классы регулярных, контекстно-свободных, контекстно-зави-
симых
и рекурсивно перечислимых множеств замкнуты относительно
объединения, конкатенации, замыкания и обращения.
Доказательство.
Для класса регулярных множеств доказательство было
дано в гл. 3.
N
T
(,,,),GVVPS=
'
''
N
V
'
P
'
P
'
Страницы
- « первая
- ‹ предыдущая
- …
- 122
- 123
- 124
- 125
- 126
- …
- следующая ›
- последняя »
