403
правки
Изменения
м
Нет описания правки
*<tex> \Sigma = \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n\} </tex>;
*<tex> \Gamma = \Sigma \cup z_0 </tex>;
*<tex> Q = \{ S_0, S_1, S_2\} </tex>, где <tex> S_0 </tex> {{---}} стартовое состояние, а <tex> S_1 S_2 </tex> {{---}} допускающее.
Переходы определим следующим образом:
*<tex> \delta(S_0, a_i, \alpha) = \langle S_0, a_i \alpha \rangle, i \in \{1, 2, ..., n \}</tex>;
*<tex>\delta(S_0, i, a_i) = \langle S_2S_1, \varepsilon \rangle, i \in \{1, 2, ..., n \}</tex>;*<tex> \delta(S_0, c, \alpha) = \langle S_1S_2, \alpha \rangle </tex>, для всех других <tex> c </tex> и <tex> \alpha </tex>, не подходящих под первые два правила;*<tex> \delta(S_1, c, \alpha) = \langle S_1, \alpha \rangle </tex>, для любых <tex> c </tex> и <tex> \alpha </tex>;*<tex> \delta(S_2, i, a_i) = \langle S_2S_1, \varepsilon \rangle, i \in \{1, 2, ..., n\}</tex>;*<tex> \delta(S_2S_1, c, \alpha) = \langle S_1S_2, \alpha \rangle </tex>, для всех <tex> c </tex> и <tex> \alpha </tex>, кроме случая, когда <tex> c = i </tex> и <tex> \alpha = a_i </tex>;*<tex> \delta(S_2, c, \alpha) = \langle S_2, \alpha \rangle </tex>, для любых <tex> c </tex> и <tex> \alpha </tex>.
Несложно увидеть, что любое слово, принадлежащее <tex> {List(a_1, a_2, ..., a_n)} </tex>, оставит данный автомат в состоянии <tex> S_2 S_1 </tex>, в противном случае переведет его в допускающее состояние <tex> S_1 S_2 </tex>.
}}
