Изменения

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

Удаление eps-правил из грамматики

75 байт убрано, 03:36, 6 декабря 2011
Доказательство корректности
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
Обозначим длину порождения за <tex>p</tex>.<br/>
:'''Базис'''. Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>
<tex>A \rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>.
Анонимный участник

Навигация