Обсуждение:Теорема Клини (совпадение классов автоматных и регулярных языков)

Доказательство, что [math]\mathrm{AUT} \subseteq \mathrm{REG}[/math] неправильное: алгоритм неправильно вычисляет [math]\xi_{ijk}[/math] в случаях, когда [math]i = j[/math]. (Например, регулярное выражение для автомата с одним принимающим состоянием и переходом в само себя уже получится неправильное).

На вскидку фикс какой-то такой:

• [math]\xi_{ii0} = (c_1 \mid \dots \mid c_l)^*[/math] , где [math]c_1, c_2, \dots c_l[/math] символы, по которым есть переход из состояния [math]i[/math] в него же самого.
• [math]\xi_{ij0} = c_1 \mid \dots \mid c_l[/math], где [math]c_1, c_2, \dots c_l[/math] символы, по которым есть переход из состояния [math]i[/math] в состояние [math]j[/math].
• [math]\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*[/math].
• [math]\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}[/math].

— Dmitriy D. 21:42, 3 октября 2015 (GST)