48
правок
Изменения
Нет описания правки
Докажем индукцией по длине порождения в грамматике <tex>\Gamma</tex>, что <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>.<br/>
'''База'''. <tex>A \underset{\Gamma}{\Rightarrow} w</tex>.<br/>
Правило <tex>A \rightarrow w</tex> присутствует в <tex>G\Gamma</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>\Gamma'</tex>, поэтому <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>.<br/>
'''Предположение индукции'''. Пусть из <tex>A \underset{\Gamma}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma'}{\Rightarrow}^*w </tex>.<br/>
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{\Gamma}{\Rightarrow}Y_1 Y_2...Y_m \underset{\Gamma}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex>.<br/>
