низм порождения правильных текстов некоторым искажающим меха
-
низмом
,
позволяющим порождать цепочки
, “
не сильно
”
отличающиеся
от правильных
.
Для этого зададим некоторую меру сходства двух произвольных
цепочек символов алфавита
A
.
Мера сходства должна отражать сте
-
пень искажения при переходе от одной из цепочек к другой
.
Роль
искажающего механизма выполняет трансформационная грамматика
[10],
содержащая некоторое множество элементарных трансформаций
(
единичных искажений
).
Тогда в качестве меры сходства между дву
-
мя цепочками естественно принять минимальное число элементарных
трансформаций
,
необходимых для перехода от одной цепочки к другой
.
Назовем язык
ˆ
L
(
M
)
ядром нечеткого языка
J
,
определяемого парой
h
ˆ
L
(
M
)
, Q
i
,
где
Q
—
некоторая трансформационная грамматика
.
Пусть
Q
определяет меру отличия
r
( ˆ
T , T
)
произвольной цепочки
Т
∈
L
от
ядерной цепочки
ˆ
Т
∈
ˆ
L
(
M
)
.
Под степенью несоответствия данной це
-
почки
Т
нечеткому языку
J
будем понимать величину
ρ
(
T,
J
) = min
ˆ
T
∈
ˆ
L
(
M
)
r
( ˆ
T , T
)
.
Рассмотрим метод ее вычисления
.
Пусть имеется пара цепочек сим
-
волов
h
T
1
, T
2
i
.
Поставим ей в соответствие сеть
G
(
T
1
, T
2
)
,
которая стро
-
ится следующим образом
.
Составим прямоугольную решетку
,
столбцы
которой соответствуют символам первой цепочки
Т
1
,
а строки
—
сим
-
волам второй цепочки
T
2
.
Каждая клетка этой решетки
—
квадрат со
стороной единичной длины
.
Клеткам сопоставлены упорядоченные па
-
ры индексов
:
(
i, j
)
-
й клетке соответствует
i
-
й символ в
Т
1
и
j
-
й символ
в
Т
2
.
Выделим клетки
,
для каждой из которых символ
,
соответствую
-
щий ее строке
,
совпадает с символом
,
соответствующим ее столбцу
.
В
каждой такой клетке проведем диагональ
,
связывающую ее левый верх
-
ний узел с правым нижним
.
Все вертикальные стороны и диагонали
,
связывающие соседние узлы
,
ориентируем стрелкой вниз
,
а горизон
-
тальные стороны
—
стрелкой слева направо
.
Множество
Х
всех узлов такой решетки есть множество узлов гра
-
фа искомой сети
G
(
T
1
,
Т
2
)
,
число их равно
q
= (
l
1
+ 1)(
l
2
+ 1)
,
(
3
)
где
l
1
и
l
2
—
число символов в
Т
1
и
Т
2
соответственно
,
а множество
Y
всех сторон и диагоналей есть множество дуг этого графа
.
Истоком
x
1
сети служит самый левый верхний узел
,
а стоком
x
2
—
самый правый
нижний узел
.
На рис
. 4
представлена сеть
G
(
T
1
, T
2
)
трансформации цепочки
Т
1
h
hthh
i
в цепочку
T
2
=
h
hhth
i
.
Каждый путь
S
,
ведущий из истока
ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
3 103
