223
правки
Изменения
Новая страница: «Доказательство, что <tex>\mathrm{AUT} \subseteq \mathrm{REG}</tex> неправильное: алгоритм неправильно вычисл...»
Доказательство, что <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>.
— [[Участник:Dmitriy D.|Dmitriy D.]] 21:42, 3 октября 2015 (GST)
На вскидку фикс какой-то такой:
*<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>.
— [[Участник:Dmitriy D.|Dmitriy D.]] 21:42, 3 октября 2015 (GST)
