Составители:
10
i
распознающего механизма и выводить в список только предложения языка.
Однако, если используется распознающая процедура, а не алгоритм, есть
опасность, что процесс порождения никогда не продвинется дальше первого же
предложения, на котором процедура не завершается.
Для предотвращения этой опасности надо организовать проверку таким
образом, чтобы распознающая процедура никогда не продолжала проверку
одного предложения вечно. Сделать это можно следующим образом.
Пусть в алфавите
V имеется p символов. Предложения из множества V
*
можно рассматривать как числа p-ичной системы счисления, включая и пустое
предложение
ε. Пронумеруем предложения из V
*
в порядке увеличения длины,
причём все предложения одинаковой длины будем нумеровать в “числовом”
порядке. Например, если
V = {a, b, c}, то предложения из V
*
будут
занумерованы следующим образом:
1.
ε
5.
aa
9.
bb
2.
a
6.
ab
10.
bc
3.
b
7.
ac
11.
ca
4.
c
8.
ba
12. …
Тем самым показано, что множество предложений над алфавитом
V счётно.
Пусть
P — распознающая процедура для языка L. Предполагается, что она
разбита на шаги так, что имеет смысл говорить об
i-м шаге этой процедуры для
любого заданного предложения.
Прежде чем дать процедуру перечисления предложений языка
L,
определим способ нумерации пар положительных целых. Можно отобразить
всё множество пар положительных целых (
i, j) на множество положительных
целых, как показано в табл. 1.1, при помощи следующей формулы:
.
(1)(2)
2
ij ij
kj
+− +−
=+
Таблица 1.1
Замечание 1.1. Поясним, как получена вышеприведенная формула. Пусть имеется неко-
торое k, k ≥ 1, занимающее в сетке позицию (i , j). Ясно, что k = N + j .
Здесь
(1)
123...
2
nn
Nn
+
=+++ + =
— число элементов внутри треугольной сетки с
основанием, концы которого имеют координаты
(i + j − 1, 1) и (1, i + j − 1). Очевидно, что
здесь n — число рядов клеток треугольной сетки, параллельных её основанию, считая и само
это основание. Очевидно также, что i + j = n + 2. Следовательно, n = i + j – 2. Подставив
последнее выражение для n в формулу для N, получим приведенное ранее выражение для k.
1 2 3 4 5
1
1 3 6 10 16
2
2 5 9 14 …
3
4 8 13 …
4
7 12 …
5
11 …
j
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
