Обсуждение:Конечный автомат

Совершенно бездарная статья. Для сравнения - en:Finite state machine Статья в целом не раскрывает термин, содержит логические ошибки. Придется использовать английскую статью— Это сообщение написал, но не подписался участник 71.143.240.235 (обсуждение • вклад) .

Если Вы обнаружили в статье ошибки, пожалуйста, исправляйте их, или допишите статью до приемлемого уровня. mospehraict 19:52, 1 декабря 2006 (UTC)

Английский вариант достаточно бредов...нельяз сказать, что неверен, но ни последовательности, ни выделения главного там особо не наблюдается. Assargadon 09:13, 11 февраля 2007 (UTC)

«Недетерминированные автоматы являются неудобными на практике, поэтому их практически не используют» -- как раз наоборот, любая обработка текста регулярными выражениями делается исключительно посредством НКА. av 11:02, 11 июля 2008 (UTC)

Отсутстувующая информация в статье

Отсутстувующая информация в статье не даёт возможности понять ее концептуально. Мне очень жаль, но, что такое r что такое U (широкий такой символ), что такое М? Что значит определение? - нет конечного выхода. - что это работа без "выхлопа", то есть без конечного результата? Работа для работы, а не для результата?

Либо поменяйте определение на корректное, либо удалите статью.

212.3.113.251 09:40, 14 июля 2013 (UTC) Денис Р.

Неверная картинка

Картинка http://commons.wikimedia.org/wiki/File:Dfa.svg?uselang=ru не является детерменированным конечным автоматом - например, из p0 нет ребра по b 128.69.154.193 19:04, 10 сентября 2013 (UTC) Averik

Марковские цепи

Недетерминированный КА, если не ошибаюсь, является модификацией обыкновенной марковской цепи, почему про них ничего не написано? Непорядок. 176.213.208.15 11:05, 13 июня 2020 (UTC)

• Каким образом это модификация марковской цепи? adamant.pwn — contrib/talk 10:05, 15 июня 2020 (UTC)

Конечное и начальное состояния, что это такое?

Совершенно непонятно. Отсюда также непонятно выражение «автомат допустил слово». Автомат не может знать, получил ли он полное слово, или только часть его. Д.Ильин (обс.) 15:52, 16 июня 2020 (UTC).

• А что не ясно?.. Есть некоторое выделенное состояние, которое называют начальным. Ещё некоторые состояния помечены как финальные. Мы кормим автомату слово по одному символу. Если в конце оказались в финальном состоянии, то автомат принял слово. Иначе он его отверг. Это если не вдаваться в вопросы детерминированности. adamant.pwn — contrib/talk 21:04, 16 июня 2020 (UTC)
  • Ладно, с начальным состоянием почти разобрались — назначаем произвольное состояние начальным. Но остается непонятно «конечное состояние». Д. А. Поспелов называет конечным состоянием такое состояние, из которого автомат не может быть выведен любым воздействием. Но тогда повисает непонятной фраза «автомат допустил слово». Пример. RS-триггер. У него нет конечного состояния, следовательно, любое слово для него недопустимо. Явная чушь. Или исключаем его из класса конечных автоматов. Д.Ильин (обс.) 22:01, 16 июня 2020 (UTC).
    • Да, тут, вероятно, есть некоторая проблема с терминологией. Статья в данный момент, в основном, завязана на конечных автоматах из теории формальных языков. Те именно что служат абстрактными устройствами для решения задачи о принадлежности слов некоторому языку (см. задача разрешимости). Вы же сейчас говорите о некоторых устройствах более общего вида, видимо, имеющих некоторую физическую реализацию или выполняющих некоторое действие… Можете, пожалуйста, уточнить, в каком именно источнике дано такое определение конечного состояния? Я посмотрю и попробую сопоставить написанное там с текущим содержимым статьи. adamant.pwn — contrib/talk 22:27, 16 июня 2020 (UTC)

Я не помню название книги Поспелова, популярная по логике, но помню, что рефлексию высокого порядка он там иллюстрирует стишком:
- Он целовал вас, кажется?
- Боюсь, что это так!
- Но как же вы позволили?
- Ах, он такой чудак!
Он думал, что уснула я
И все во сне стерплю,
Иль думал, что я думала,
Что думал он: я сплю!
А финальное состояние конечного автомата поясняет «адской машинкой» — после взрыва никакие воздействия не могут её перевести ни в какое другое состояние.

Что касается RS-триггера — он совсем не обязательно из транзисторов-резисторов, такой себе абстрактный элемент, в терминах конечного автомата его можно описать и таблицей переходов, и графом, и формальным семантическим языком. Да вот возьмем простой выключатель света — тоже имеет 2 состояния и воспринимает буквы их двухбуквенного алфавита — следовательно, отвлекаясь от физической реализации, абстрактно является конечным автоматом.

Резюме. Статья написана плохо и требует существенной переработки. Д.Ильин (обс.) 00:08, 17 июня 2020 (UTC).

• Д.Ильин, а можете, пожалуйста, уточнить источник, по которому вы дополняете статью? adamant.pwn — contrib/talk 11:32, 18 июня 2020 (UTC)

• • Кузнецов О. П., Адельсон-Вельский Г. М. Автоматы // Дискретная математика для инженера. — М.: Энергия, 1980. — 344 с.

Д.Ильин (обс.) 12:33, 18 июня 2020 (UTC).