Составители:
12
Построим алгоритм распознавания языка
L, т.е. отвечающий на вопрос:
“
x∈ L?”, следующим образом:
Шаг 1.
i := 1.
Шаг 2. Применим
i шагов процедуры P к цепочке x. Если процедура P не
завершается, то перейти к шагу 3, иначе — к шагу 4.
Шаг 3. Применим
i шагов процедуры
P
к цепочке x. Если процедура
P
не
завершается, то
i := i + 1 и перейти к шагу 2.
Шаг 4. При некотором
i одна из этих двух процедур завершится, распознав
цепочку
x, так как либо x ∈ L и это распознаёт процедура P, либо x ∉ L и
это распознаёт процедура
P . Соответственно распознающий алгоритм выдаёт
либо положительный, либо отрицательный ответ.
Поскольку язык
L распознаётся описанным алгоритмом, то он рекурсивен.
Что и требовалось доказать.
Упражнения
I-1.1. Функция
отображает упорядоченные пары целых на целые. Найти обратные функции
I(k) и J(k) с таким свойством, что I(K(i, j)) = i и J(K(i, j)) = j.
Составьте процедуру на Паскале, которая по целому
k>0 выдаёт i и j —
номер строчки и столбца треугольной сетки, где расположено значение
k.
I-1.2. Пусть
m
J
(w, x, y) = J (w, J(x, y)). Какая тройка приписывается числу
1000, если
(1)(2)
(,) .
2
xy
x
y
Jx
yy
+ − + −
=+
I-1.3. Опишите простую процедуру для перенумерации предложений
рекурсивного языка.
I-1.4. Докажите, что если язык L и его дополнение = L \ V
*
рекурсивно
перечислимы, то язык
L — рекурсивен.
I-1.5. Докажите, что если существует процедура для перечисления
множества целых в монотонном порядке, то это множество рекурсивно в том
смысле, что существует алгоритм определения, находится ли данное целое в
этом множестве.
I-1.6. Покажите, что все конечные множества рекурсивны.
(1)(2)
(, )
2
ij ij
K
ij j
+ − + −
=+
L
−
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
