Изменения

Доказательство, что <tex>\mathrm{AUT} \subseteq \mathrm{REG}</tex> было неправильное: тот алгоритм неправильно вычисляет <tex>\xi_{ijk}</tex> в случаях, когда <tex>i = j</tex>. (Например, регулярное выражение для автомата с одним принимающим состоянием и переходом в само себя уже получится неправильное). На вскидку фикс какой-то такой: *<tex>\xi_{ii0} = (c_1 \mid \dots \mid c_l)^*</tex> , где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния <tex>i</tex> в него же самого.*<tex>\xi_{ij0} = c_1 \mid \dots \mid c_l</tex>, где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния <tex>i</tex> в состояние <tex>j</tex>.*<tex>\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*</tex>. *<tex>\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}</tex>.  Кто-нибудь проверьте меня и исправьте статью. Это висит там с 2010 года.— [[Участник:Dmitriy D.|Dmitriy D.]] 21:42, 3 октября 2015 (GST)