Бюрократы, editor, Администраторы
422
правки
Изменения
→Определения
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> называется <b>ситуацией</b>, относящейся к цепочке <tex>\omega</tex>, если где <tex>A \rightarrow \alpha \beta </tex> {{---}} — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>\omega</tex>, называется '''ситуацией''', относящейся к цепочке <tex>\omega</tex>.
}}
{{Определение
|definition =
<btex>Cписком ситуацийj</btex> -м '''списком ситуаций''' <tex>I_j</tex> для входной цепочки <tex>\omega = a_1 a_2 ... a_n</tex>, где <tex>0 \leqslant j \leqslant n</tex> , называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] </tex> таких, что <tex>\mid \alpha \Rightarrow^* a_{i+1} ... a_j</tex>, и для некоторых <tex>; \exists \gamma</tex> и <tex>, \delta</tex> существуют выводы <tex>: S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i\rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>\omega</tex> c первого по <tex>j</tex>-й символ.
}}
