Изменения

Перейти к: навигация, поиск

Участник:Shovkoplyas Grigory

545 байт убрано, 19:29, 18 января 2016
Нет описания правки
{{Определение
|definition =
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 w_2 ... w_nw_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>. '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
}}
{{Определение
|definition =
'''<tex>j</tex>-м списком ситуаций''' <tex>D_j</tex> для входной цепочки <tex>w = w_1 w_2 Ситуации хранятся в множествах D_0,... w_n</tex>, где <tex>0 \leqslant j \leqslant D_{n</tex>-1}, называется множество называемых спиками ситуаций . Причем наличие ситуации <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* w_{i+1} ... w_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* w_1...w_i \rbrace</tex>. То есть в <tex>\gamma \alpha j</tex> выводит часть -м списком ситуаций <tex>wD_j</tex> c первого по <tex>j</tex>-й символ.}} {{Леммаравносильна тому, что |statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] delta \in D_n) \Leftrightarrow w Sigma \in Lcup N : ((G)</tex>.|proof = Поскольку <tex>S ' \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = w_0...w_{i-1} A \delta = \varepsilon</tex>), из определения <tex>D_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow (S \Rightarrow \alpha wedge A \Rightarrow^* w_1 w_i... w_n = ww_{j-1})</tex>.
}}
{{Определение
|definition =
Последовательность списков ситуаций <tex>D_0, D_1, .., D_nD_{n-1}</tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
}}
69
правок

Навигация