Изменения

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

Участник:Shovkoplyas Grigory

4 байта добавлено, 20:17, 18 января 2016
Нет описания правки
=====<b><tex>\Longrightarrow</tex>=====</b><br/>
Докажем индукцией по исполнению алгоритма.<br/>
<u> ''База индукции:'' </u><br/>
Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
=====<b><tex>\Longleftarrow</tex>=====</b><br/>
В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0...w_{i-1} A \delta</tex> из <tex>S'</tex> и <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
индукцию по длине вывода <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
69
правок

Навигация