Стр. 21 - Информационные структуры и их преобразование

Содержание 19
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Z
b M b
( L
M a )
a
Если между какой-либо парой символов определено более чем одно
отношение, использование матрицы невозможно. Если отношение
единственно, то можно утверждать, что основой сентенциальной формы
S1…Sn является подцепочка Si …Sj, для которой выполнено условие:
…Si-1⋖ Si ≐ Si+1 ≐ … ≐ Sj-1 ≐ Sj ⋗ Sj+1…
Пример: Возьмем цепочку b(аа)b.
Сентенциальная
форма
Основа Нетерминал, к которой
приводится цепочка
Непосред-
ственный вывод
#⋖b⋖(⋖a⋗a≐)⋗b# a M M=> a
#⋖b⋖(⋖M≐a ≐)⋗b# Ma) L L=> Ma)
#⋖b⋖(≐L⋗b# (L M M=>(L
#⋖b≐M≐b⋗# bMb Z Z=>bMb
3.2. Отношения предшествования и их вычисление
1) R≐ S тогда и только тогда, когда в грамматике G(Z) существуют
правила: U: = … RS …
2) R⋗ S тогда и только тогда, когда в грамматике существуют правила
вида: U: = … R и имеется вывод W=>+S…, т.е. W PR+ S (S – префикс
W).
3) R⋖ S тогда и только тогда, когда в грамматике существуют правила
вида: U: = …VW… и имеются выводы W=>+S…, V=>+…R (R –
суффикс V).
>• >• )
= >• a
>• L
•<= •< (
= = M
•< = b
Z
) a L ( M b Z


 
