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