Составители:
11
Итак, мы можем перенумеровать упорядоченные пары целых чисел
согласно присвоенному номеру
k. Несколько первых пар есть:
(1, 1), (2, 1), (1, 2), (3, 1), (2, 2), ... .
Любая заданная пара чисел (
i , j) действительно окажется в списке под
номером
(1)(2)
.
2
ij ij
kj
+
−+−
=+
Теперь мы можем описать процедуру перечисления, т. е. порождающую
процедуру, предложений языка
L.
Процедура перенумеровывает пары целых в соответствии с табл. 1.1.
Когда пара (i , j) занумеровывается, процедура порождает i-е предложение
из множества
V
*
и выполняет первые j шагов распознающей процедуры P над
этим предложением.
Когда процедура P определяет, что порождённое предложение принад-
лежит языку
L, порождающая процедура добавляет это предложение к списку
предложений языка
L. Теперь, если слово номер i принадлежит языку L, то этот
факт устанавливается при помощи процедуры
P за j шагов для некоторого
конечного
j. Очевидно, что таким образом организованная процедура будет
перечислять все предложения языка
L.
С другой стороны, если имеется
порождающая процедура для языка L, то
на её основе можно построить
распознающую процедуру для этого языка.
Действительно, чтобы определить, имеется ли предложение
x в L, достаточно с
помощью порождающей процедуры последовательно порождать предложения
языка L и сравнивать каждое с x. Если x порождается, то распознающая
процедура заканчивается, распознав
x. Конечно, если предложение x не в L, то
распознающая процедура никогда не закончится.
Определение 1.4. Язык, предложения которого могут порождаться
процедурой, называется
рекурсивно перечислимым. Также принято говорить,
что язык рекурсивно перечислим, если существует процедура распознавания
предложений этого языка.
Определение 1.5. Язык рекурсивен, если существует алгоритм его
распознавания.
Известно, что класс рекурсивных языков является собственным
подмножеством класса рекурсивно перечислимых языков. Более того,
существуют языки и похуже, которые даже не рекурсивно перечислимы, т.е.
невозможно эффективно перечислять предложения такого языка. Пример
языка, не являющегося рекурсивно перечислимым множеством, приводится в
начале §7.3.
Теорема 1.1. Пусть L
⊆
V
*
— некоторый язык, а L = V
*
\ L — его
дополнение. Если языки L и
L
рекурсивно перечислимы, то язык L рекурсивен.
Доказательство. Пусть язык
L распознаётся процедурой P, а его
дополнение
L
распознаётся процедурой P .
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
