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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показаны 2 промежуточные версии 1 участника)
Строка 1: Строка 1:
−
Доказательство, что <tex>\mathrm{AUT} \subseteq \mathrm{REG}</tex> неправильное: алгоритм неправильно вычисляет <tex>\xi_{ijk}</tex> в случаях, когда <tex>i = j</tex>. (Например, регулярное выражение для автомата с одним принимающим состоянием и переходом в само себя уже получится неправильное).
+
Доказательство, что <tex>\mathrm{AUT} \subseteq \mathrm{REG}</tex> было неправильное: тот алгоритм неправильно вычисляет <tex>\xi_{ijk}</tex> в случаях, когда <tex>i = j</tex>. (Например, регулярное выражение для автомата с одним принимающим состоянием и переходом в само себя уже получится неправильное). — [[Участник:Dmitriy D.|Dmitriy D.]] 21:42, 3 октября 2015 (GST)
−
 
+
: Соглашусь, теперь больше похоже на правду. [[Участник:Shersh|Дмитрий Коваников]] 23:23, 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)
 

Текущая версия на 22:23, 3 октября 2015

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

Соглашусь, теперь больше похоже на правду. Дмитрий Коваников 23:23, 3 октября 2015 (GST)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков)&oldid=49589»