Изменения
Нет описания правки
* <tex>|\omega|=1</tex>: По построению стартовое состояние ДКА будет <tex>{s}</tex>, где <tex>s</tex> {{---}} стартовое состояние НКА, причем допускать они могут только одновременно.
* Пусть для <tex>|\omega|=n</tex> - это верно, докажем, что верно и для <tex>|\omega|=n+1</tex>:
Пусть НКА на шаге n мог находиться в состояниях <tex>{q_1...q_k}</tex>, тогда ДКА, по построению, находится в состоянии <tex>Q={q_1...q_k}</tex>. После перехода по <tex>\omega[n+1] = сc</tex> НКА будет находиться в состояниях <tex>{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex>, а ДКА в состоянии <tex>P=\delta_D(Q, c)</tex>, причем, в силу построения, оно будет допускающим, когда одно из <tex>tex{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex> {{---}} допускающее. Что нам и требовалось.
}}
