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

Содержание 9
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Пусть G(z)-грамматика и X,Y -некоторые сентенциальные формы в ней.
Тогда U-полная фраза сентенциальной формы для нетерминала U,если
имеется вывод U=>+u и если имеется правило U:=u.
Пример: E:=E +T|T; T:=T∗F|F; F:=(E)|i
+
Если рассмотреть все висячие вершины
слева направо, то получим предложение
i+(i*i)+i*i. i+(E) является фразой для
нетерминального символа E (2-й сверху), для
этого же символа E+T является простой
фразой. Основой всякой сентенциальной
формы называется самая левая простая фраза.
1.3. Отношения и операции над ними
Пусть есть 2 отношения: aRb и aPb, где a,b∈A. Рассмотрим отношение
RP и назовем его произведением отношений R и P.Отношение RP имеет
место тогда и только тогда, когда на множестве A есть элемент c , для
которого выполняется aRc и cPb.Тогда между a и b есть отношение RP, т.е.
aRPb.
Пример: aRb: b=a+1; aPb: b=a+2
Из этих двух предложений следует, что aRPb b=a+3
Отыскать n-ю степень отношения R на множестве A означает найти
такое подмножество элементов c1 …cn , для которых выполняется отношение:
aRc1,c1 Rn-1b,c1Rc2,c2R n-2b… .
n-1 степень R получила название транзитивного замыкания
отношения R и обозначается – R+:
R +=R1 ∪R 2∪R3∪…
Т
T i F F
(Е)i F
i
Е
Е T
Е Т F + *
Т
Т F *
i i