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

18 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
3. ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ
3.1. Простые предшествования.
При использовании этого метода в текущей сентенциальной форме
осуществляется поиск основы, которая в соответствии с правилами этой
грамматики приводится к нетерминальному символу, стоящему в левой
части. Будем искать основу сентенциальной формы, двигаясь слева направо,
и рассматривать одновременно два соседних символа.
Пусть имеется цепочка … RS … . Здесь возможны ситуации:
1) Оба символа принадлежат основе (правой части правила)(U:=
…RS…)
R≐ S (одновременно)
U
… R S …
2) R принадлежит основе, а S – нет (U:=…WS…; W=>+…R)
R⋗ S (R раньше S)
U
W
… R S
3) S принадлежит основе, а R – нет (U: = …RW…; W=>+S…)
R⋖ S (R позже S)
U
W
R S …
Пример: Имеется грамматика G(Z).
Z: = bMb;
M: = (L|a;
L: = Ma).