Объясните простым языком что такое конечный автомат? Желательно с примерами.

Здравствуйте, Grundik2, Вы писали:

G>Объясните простым языком что такое конечный автомат? Желательно с примерами.
Сядьте там и слухайте сюды:
КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
рассматривает эту строку "под микроскопом"
и признает строку кошерной или не кошерной.
В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
Конечный — количество состояний этой машины конечно.

Здравствуйте, Grundik2, Вы писали:

G>Объясните простым языком что такое конечный автомат? Желательно с примерами.

Объект с состояниями и правилами перехода между состояниями.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Grundik2, Вы писали:

G>Объясните простым языком что такое конечный автомат? Желательно с примерами.

Всего-навсего модель некой системы с конечным числом состояний и правилами перехода из одних состояний в другие.

Изображается в виде ориентированного графа, где узлы (кружки) — это состояния, а ребра (стрелочки) — переходы.

Есть один момент в конечных автоматах, который не всегда очевиден для начинающих, в том, что каждое состояние представляет собой комбинацию (которая называется "кортеж" в математике) всех параметров системы. Например, если мы хотим описать компьютер конечным автоматом, в качестве одного состояния мы берем состояние всей постоянной и оперативной памяти целиком. То есть изменение одного бита — это другое состояние, другой кружок. Все варианты значений двух битов дают четыре состояния конечного автомата, трех битов — восемь состояний, четырех битов — шестнадцать состояний и т.д.

Необходимо понимать, что конечный автомат — математическая модель, которую не всегда удобно и возможно представить буквально в программе.

Например, модель компьютера в качестве конечного автомата будет иметь гигантское число состояний: 2 ^ ((500 + 16) * 2^30 * 8) для компьютера с 500 ГиБ дискового пространства и 16 ГиБ ОЗУ, что не влезет ни в какие границы памяти и производительности, если вы захотите представить такой конечный автомат в своей программе.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Grundik2, Вы писали:

А> Всего-навсего модель некой системы с конечным числом состояний
А> и правилами перехода из одних состояний в другие.
это вам лошадь сказала? она гонит. конечный автомат как модель некой системы -- это учебное пособие для простоты понимания на наглядных примерах.

А> каждое состояние представляет собой комбинацию (которая называется "кортеж" в математике) всех параметров системы.
состояние ка это всего лишь состояние ка. о какой системы вы говорите?

А> Например, модель компьютера в качестве конечного автомата будет иметь гигантское число состояний:
А> 2 ^ ((500 + 16) * 2^30 * 8) для компьютера с 500 ГиБ дискового пространства и 16 ГиБ ОЗУ,
А> что не влезет ни в какие границы памяти и производительности, если вы захотите представить
А> такой конечный автомат в своей программе.
вам не кажется, что в ваших рассуждениях ошибка? и для представления компьютера с памятью и диском вполне достаточно дисковой памяти с небольшим оверхидом, если хранить состояния "как есть".

Здравствуйте, LaptevVV, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
LVV>Сядьте там и слухайте сюды:
LVV>КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
LVV>рассматривает эту строку "под микроскопом"
LVV>и признает строку кошерной или не кошерной.
LVV>В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
LVV>Конечный — количество состояний этой машины конечно.

Я лично по этому объяснению, мягко говоря, нифига бы не понял.
Даже то математизированное объяснение, которое нам скормили на дискретной математике, через множество состояний и функцию перехода — в разы лучше. Потому что в Вашем варианте:
1. Участвует некая "строка", которая автоматически (если не подчеркнуть) предполагается цельной сущностью, анализируемой целиком и сразу, а не потенциально растянутым во времени на бесконечность и по частям.
2. Признание кошерности никак не является тем случаем, который нужен большинству для рассмотрения, и никак не объясняет сущность механизма.
3. Ключевой принцип — внутреннее состояние — не названо и не расписано.

Я надеюсь, Вы такое не даёте студентам, по крайней мере сразу. Иначе у ваших уборщиц есть постоянный источник проблем (убирать вскипевшие мозги).

Почти без подразумевающихся смайликов.

Здравствуйте, LaptevVV, Вы писали:

LVV>Здравствуйте, Grundik2, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
LVV>Сядьте там и слухайте сюды:
LVV>КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
LVV>рассматривает эту строку "под микроскопом"
LVV>и признает строку кошерной или не кошерной.
LVV>В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
LVV>Конечный — количество состояний этой машины конечно.

вообще непонятно.

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, LaptevVV, Вы писали:

G>>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
LVV>>Сядьте там и слухайте сюды:
LVV>>КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
LVV>>рассматривает эту строку "под микроскопом"
LVV>>и признает строку кошерной или не кошерной.
LVV>>В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
LVV>>Конечный — количество состояний этой машины конечно.

N>Я лично по этому объяснению, мягко говоря, нифига бы не понял.
N>Даже то математизированное объяснение, которое нам скормили на дискретной математике, через множество состояний и функцию перехода — в разы лучше. Потому что в Вашем варианте:
N>1. Участвует некая "строка", которая автоматически (если не подчеркнуть) предполагается цельной сущностью, анализируемой целиком и сразу, а не потенциально растянутым во времени на бесконечность и по частям.
N>2. Признание кошерности никак не является тем случаем, который нужен большинству для рассмотрения, и никак не объясняет сущность механизма.
N>3. Ключевой принцип — внутреннее состояние — не названо и не расписано.

N>Я надеюсь, Вы такое не даёте студентам, по крайней мере сразу. Иначе у ваших уборщиц есть постоянный источник проблем (убирать вскипевшие мозги).

N>Почти без подразумевающихся смайликов.

а на пример какой-нибудь простой?

Здравствуйте, netch80, Вы писали:

G>>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
LVV>>Сядьте там и слухайте сюды:
LVV>>КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
LVV>>рассматривает эту строку "под микроскопом"
LVV>>и признает строку кошерной или не кошерной.
LVV>>В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
LVV>>Конечный — количество состояний этой машины конечно.

N>Я лично по этому объяснению, мягко говоря, нифига бы не понял.
N>Даже то математизированное объяснение, которое нам скормили на дискретной математике, через множество состояний и функцию перехода — в разы лучше. Потому что в Вашем варианте:
N>1. Участвует некая "строка", которая автоматически (если не подчеркнуть) предполагается цельной сущностью, анализируемой целиком и сразу, а не потенциально растянутым во времени на бесконечность и по частям.
N>2. Признание кошерности никак не является тем случаем, который нужен большинству для рассмотрения, и никак не объясняет сущность механизма.
N>3. Ключевой принцип — внутреннее состояние — не названо и не расписано.
1. Ответ предназначался НЕ вам. Если вы НЕ поняли, то это совсем не значит, что не поймет ТС.
2. Я именно подчеркнул — последовательность неких элементов, не обязательно символов
3. Кошерность — истинность. Именно это устанавливает КА.
4. О состояниях у меня даже отдельной строкой...
N>Я надеюсь, Вы такое не даёте студентам, по крайней мере сразу. Иначе у ваших уборщиц есть постоянный источник проблем (убирать вскипевшие мозги).
Я еще и Жванецкого на лекциях цитирую...
Например, объяснение локальности переменных прекрасно проиллюстрировано Жванецким в рассказе о мясомолпроме...
"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"
N>Почти без подразумевающихся смайликов.
Ну а я со смайликами...

Здравствуйте, Grundik2, Вы писали:

G>Здравствуйте, LaptevVV, Вы писали:

LVV>>Здравствуйте, Grundik2, Вы писали:

G>>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
LVV>>Сядьте там и слухайте сюды:
LVV>>КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
LVV>>рассматривает эту строку "под микроскопом"
LVV>>и признает строку кошерной или не кошерной.
LVV>>В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
LVV>>Конечный — количество состояний этой машины конечно.

G>вообще непонятно.
Тогда смотри сюда:
КА — это абстрактная машина с конечным числом состояний...
На входе — последовательность элементов. Чаще всего — строка символов.
КА рассматривает эту последовательность символов, и выдает ответ, принадлежит ли эта строка некоему языку или нет.
В автомате самое важное — функция перехода из состояния в состояние.
Это функция двух переменных: текущее состояние и символ строки.
В зависимости от сочетания автомат переходит в новое состояние.
Если нужны подробности то, вот:

Для разбора строки используем детерминированный конечный автомат (ДКА).
Входной информацией для ДКА является строка символов (или, как обычно говорят, «входная лента»). В процессе работы автомат определяет, является ли входная строка в некотором смысле «правильной». Детерминированные конечные автоматы обычно применяются в компиляторах для распознавания лексем: идентификаторов, чисел, ключевых слов, операций.
Детерминированный конечный автомат — это абстрактное устройство, в котором можно выделить следующие элементы:
• конечное множество состояний S = {s0, s1, s2, …, sn};
• одно из состояний называется начальным (стартовым); без ограничения общности будем считать, что таковым является состояние s0;
• некоторое подмножество состояний E = {e1, e2, …, ek}, 1 ≤ k ≤ n, E -подмножество S, называемых конечными или допускающими;
• конечный словарь V = {a1, a2, …, am} входных символов;
• функция переходов F(si, ar) = sj, 1 ≤ r ≤ m, 0 ≤ i,j ≤ n
Автомат называется конечным, поскольку количество состояний конечно. Входная строка (лента) состоит из входных символов. Автомат начинает работу в стартовом состоянии и, выбирая из входной строки по одному символу, переходит из состояния в состояние. Функция переходов часто задается в виде конечного набора правил:
символ: si -> sj
Правило можно представить и в другом виде, например:
si: символ -> sj
Работа завершается либо после выборки последнего символа строки, либо при переходе автомата в одно из конечных состояний. Очевидно, что в первом случае строка считается «неправильной», а во втором — «правильной».
Обычно символы, которые могут быть записаны на входной ленте, разбиваются на несколько классов, и переход в новое состояние выполняется не по конкретному символу, а по классу символов. Например, символы, входящие в идентификатор, можно разбить на два класса:
 символы, которые могут быть первым символом идентификатора — это буквы и символ подчеркивания;
 символы, которые могут быть последующими символами идентификатора — это буквы, символ подчеркивания и цифры.
Символы, входящие в состав дробного числа, составляют четыре класса:
 цифры;
 знак — символы «+» или «-»;
 десятичная точка, отделяющая целую часть от дробной;
 символ экспоненты «е» или «Е».
Кроме того, обычно выделяется класс символов, являющихся недопустимыми для автомата. Например, для автомата, распознающего идентификатор, недопустимыми являются знаки операций и знаки пунктуации. Если автомат в некотором состоянии распознает недопустимый символ, то он завершает работу. Если это состояние — допускающее, то входная строка считается правильной. Если же состояние не является допускающим, то входная строка ошибочна.
При реализации конкретного ДКА самое сложное — определиться с состояниями. Обычно для этого нужно рассматривать варианты входной строки, чтобы разобраться, в каком порядке символы могут следовать друг за другом.

Еще? У меня есть.

Здравствуйте, Grundik2, Вы писали:

G>а на пример какой-нибудь простой?
Статья Кодта здесь на РСДН
Как проверить, является ли строка числом, e-mail'ом
http://www.rsdn.ru/article/alg/checkStr.xml

Автор(ы): Николай Меркин
Дата: 19.01.2002

Здравствуйте, Grundik2, Вы писали:

G>а на пример какой-нибудь простой?

Самый простой пример: детская качель на двоих (доска, два сиденья по краям, крепление посредине к чему-то неподвижному).
Два состояния: "наклон влево" и "наклон вправо". (Считаем, что отлично смазана и посредине не зависнет.)
Кто-то дёрнул слева вниз (сел сверху), когда была в наклоне влево — ничего не изменилось, так и стоит.
То же в наклоне вправо — перевелась в положение вправо и так и осталась.
Зеркально — два других варианта (сел сверху, нажал ногой на правую сторону).
Когда двое детей на качели — отталкивание от земли справа даёт тот же результат, что прижатие слева, и наоборот.

Итого: 2 состояния, 2 вида воздействия, чётко описаны 1) переходы между состояниями, 2) что между ними оно не меняется — неподвижно. Выходных данных — обязательной составляющей математической модели — тут отдельно не было, но будем считать, что мы копируем внутреннее состояние.

Кстати, я описал стандартный триггер памяти любого электронного устройства (уже неважно, на чём сделано — транзисторы, элементы И-НЕ или нанотахионные сборки на памяти воды).

Другой простейший вариант. На электросчётчике у меня на работе моргает лампочка и написано "1 кВт/ч — 1600 импульсов". Заведём внутри, кроме видимого счётчика сожранного, второй — с состояниями от 0 до 1599. По каждому импульсу он увеличивает число, кроме случая 1599, когда вместо этого переходит в 0. При переходе 1599->0 он рисует короткий импульс к видимому счётчику для увеличения потреблённого на 1, в остальных случаях не рисует. Вот уже автомат с 1600 состояниями и выходом. Обычно для практики такое переформулируют в состояние с параметром, но это уже более развитой вариант.

У меня в практике типичны автоматы "мы пытаемся стучаться к партнёру для обновления его состояния". Тогда у автомата есть заказ свистка "время чего-то подошло", а состояние состоит из

последних полученных данных, с таймстампом получения (ts_last_received)

флага "есть посланный запрос" или "спим между запросами" (is_sent)

тамстампом изменения флага из предыдущего пункта (ts_last_action)

На старте данных нет, в ts_last_received ноль. Ставим запрос состояния на посылку, is_sent в 1, ts_last_action в сейчас, включаем таймер на истечение времени попытки, идём спать. Если приходит ответ — записываем его, ставим ts_last_received в сейчас, is_sent в 0, ts_last_action в сейчас, ставим таймер на время между запросами, идём спать; по срабатыванию этого таймера — те же действия, что в самом начале, только данные уже какие-то есть. Если истёк таймаут ожидания ответа, а ответа нет — точно так же повторить отправку запроса. Плюс к этому счётчики событий всех интересных видов (как минимум два — ответ пришёл вовремя и ответа не дождались).

Надеюсь, понятно. Главная идея тут та, что между событиями, которые его меняют, автомат это нечто "мёртвое". У него есть только его состояние — и всё. Оно может быть сколь угодно сложным, но он не имеет собственного моторчика, который бы его оживлял, он только реагирует на события.

Вот с этого момента можно вводить математику. Есть множество состояний. Есть множество внешних воздействий. Есть функция перехода с двумя параметрами — состояние до перехода и внешнее воздействие, которая должна выдать результат — новое состояние. Есть выход автомата, который зависит только от нового состояния (автомат Мура) или и от воздействия (автомат Мили), разница между ними только в удобстве, их модели легко переводятся одна в другую. Методы теории конечных автоматов позволяют определить, например, нет ли лишних состояний, пропущенных переходов, можно ли разделить на два автомата без изменения функциональности и т.п.

Самое типичное явное (для использующего программиста) применение концепции автомата — это среды, где можно что-то делать только в коллбэках и понемножку (отреагировать, изменить что-то внутри и отдать управление). Но бывают случаи, когда и подпрограмму, которая не отдаёт управление, написать через конечный автомат — явно разделив состояние и код реакции на состояние. Вот тут уже (и не раньше) начинают работать примеры Лаптева с работой со строками. Например, движок регулярных выражений пишется только через автоматы (а DFA или NFA — это уже следующий этап). NFA — это, чуть упрощая, когда состояние внутри является набором одновременно возможных вариантов интерпретации состояния, из которых в конце сработает только одно (можешь представить себя следователем, который разрабатывает несколько версий одновременно — это будет типичный NFA). DFA — традиционно, состояние только одно. Разбор грамматики тоже может делаться на автоматах, и если это получается, то так сильно дешевле по времени, чем перебор с бэктрекингом...

Здравствуйте, LaptevVV, Вы писали:

LVV>1. Ответ предназначался НЕ вам. Если вы НЕ поняли, то это совсем не значит, что не поймет ТС.

Я угадал, что он не поймёт, и последующий комментарий подтвердил это
А ещё прошу не забывать, что любая реплика на публичном форуме адресована потенциально неограниченному кругу участников.

LVV>2. Я именно подчеркнул — последовательность неких элементов, не обязательно символов

Для того, чтобы понять, как "символы" тут связаны с реальностью, требуется дополнительное объяснение или высокий уровень математической интуиции, позволяющий легко сводить в сознании по-разному описанные концепции на основании общих свойств. Обычно это уровень минимум аспиранта.

LVV>3. Кошерность — истинность. Именно это устанавливает КА.

Не знаю, в каких теориях нужно именно это свойство КА, но на практике в большинстве случаев, когда произвольный программист использует КА, от него нужно совсем другое — на заведомо истинный входной поток (строку, в Ваших терминах) давать соответствующий выходной поток. Примеры такого заведомо истинного — все три мои примера из предыдущего постинга. Любое устанавливающее воздействие на триггер — истинно. Импульс на счётчик в любой момент или его отсутствие — истинно. Таймаут ответа от сервиса-партнёра столь же истинен, как и вовремя пришедший ответ с данными. Любой код, полученный процессором на исполнение, истинен, если в процессоре определено генерировать исключение на неподдерживаемые коды, а не умирать на месте.

Сводя все КА к варианту определения "истинности", Вы 1) идёте вразрез с основными положениями теории, заложенными ещё в 40-х годах, 2) катастрофически ограничиваете применение теории, делая её непригодной для большинства практически важных случаев.

LVV>4. О состояниях у меня даже отдельной строкой...

Которая точно так же непонятна без подробного разъяснения.

N>>Я надеюсь, Вы такое не даёте студентам, по крайней мере сразу. Иначе у ваших уборщиц есть постоянный источник проблем (убирать вскипевшие мозги).
LVV>Я еще и Жванецкого на лекциях цитирую...
LVV>Например, объяснение локальности переменных прекрасно проиллюстрировано Жванецким в рассказе о мясомолпроме...
LVV>"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"

Сильно не уверен, что это их настолько радует. Ментальное поле за 30 лет существенно изменилось.
Я уже того Жванецкого вспоминаю в лучшем случае раз в году...

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, LaptevVV, Вы писали:

LVV>>"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"
N>Сильно не уверен, что это их настолько радует. Ментальное поле за 30 лет существенно изменилось.
N>Я уже того Жванецкого вспоминаю в лучшем случае раз в году...
по колбасу и я не понял. в ссср была плохая колбаса? если я правильно помню, колбаса была хорошая, при условии если она была. проблема в том, что ее не было. легенды о добавлении бумаги опровергались тем, что 1 кг бумаги в ссср стоил дороже 1 кг мяса.

кстати, интересно как вв на примере жванецкого объясняет различие между глобальными переменными (с учетом пространства имен) и локальными переменными (с учетом статических).

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, LaptevVV, Вы писали:

LVV>>1. Ответ предназначался НЕ вам. Если вы НЕ поняли, то это совсем не значит, что не поймет ТС.

N>Я угадал, что он не поймёт, и последующий комментарий подтвердил это
N>А ещё прошу не забывать, что любая реплика на публичном форуме адресована потенциально неограниченному кругу участников.
Сколько участников — столько и мнений. На всех — не угодишь...

LVV>>2. Я именно подчеркнул — последовательность неких элементов, не обязательно символов
N>Для того, чтобы понять, как "символы" тут связаны с реальностью, требуется дополнительное объяснение или высокий уровень математической интуиции, позволяющий легко сводить в сознании по-разному описанные концепции на основании общих свойств. Обычно это уровень минимум аспиранта.
Ну, я с конечными автоматами познакомился совершенно самостоятельно, ни в какой аспирантуре не учась.
Было интересно — разобрался.
LVV>>3. Кошерность — истинность. Именно это устанавливает КА.
N>Не знаю, в каких теориях нужно именно это свойство КА, но на практике в большинстве случаев, когда произвольный программист использует КА, от него нужно совсем другое — на заведомо истинный входной поток (строку, в Ваших терминах) давать соответствующий выходной поток. Примеры такого заведомо истинного — все три мои примера из предыдущего постинга. Любое устанавливающее воздействие на триггер — истинно. Импульс на счётчик в любой момент или его отсутствие — истинно. Таймаут ответа от сервиса-партнёра столь же истинен, как и вовремя пришедший ответ с данными. Любой код, полученный процессором на исполнение, истинен, если в процессоре определено генерировать исключение на неподдерживаемые коды, а не умирать на месте.
N>Сводя все КА к варианту определения "истинности", Вы 1) идёте вразрез с основными положениями теории, заложенными ещё в 40-х годах, 2) катастрофически ограничиваете применение теории, делая её непригодной для большинства практически важных случаев.
Нет.
Автомат-распознаватель и автомат-преобразователь — это разные вещи.
Естественно, все зависит от потребностей ТС. Но он — никак эти потребности не обозначил.
LVV>>4. О состояниях у меня даже отдельной строкой...
N>Которая точно так же непонятна без подробного разъяснения.
Конкретно, что именно не понятно. Что такое последовательность — мы, естественно, знаем? Или — нет?
Тогда, может, со школы начнем?
N>>>Я надеюсь, Вы такое не даёте студентам, по крайней мере сразу. Иначе у ваших уборщиц есть постоянный источник проблем (убирать вскипевшие мозги).
LVV>>Я еще и Жванецкого на лекциях цитирую...
LVV>>Например, объяснение локальности переменных прекрасно проиллюстрировано Жванецким в рассказе о мясомолпроме...
LVV>>"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"
N>Сильно не уверен, что это их настолько радует. Ментальное поле за 30 лет существенно изменилось.
N>Я уже того Жванецкого вспоминаю в лучшем случае раз в году...
Вы хотите сказать — сузилось.
Сейчас, например, большинство не знают, что такое гамма.
Не понимает, что стопка тарелок на кухне во время мытья — это стек.
Не соображает, что класс — это выкройка (штанов, например), а объект — это конкретные штаны, пошитые по этой выкройке.
Если ТС в соседнем сообщении не понимает, что такое состояние — о чем можно говорить?
В школу надо вернуться...

Здравствуйте, мыщъх, Вы писали:

LVV>>>"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"
N>>Сильно не уверен, что это их настолько радует. Ментальное поле за 30 лет существенно изменилось.
N>>Я уже того Жванецкого вспоминаю в лучшем случае раз в году...
М>по колбасу и я не понял. в ссср была плохая колбаса? если я правильно помню, колбаса была хорошая, при условии если она была. проблема в том, что ее не было. легенды о добавлении бумаги опровергались тем, что 1 кг бумаги в ссср стоил дороже 1 кг мяса.
мыщъх — это ж элементарно: они же там ВНУТРИ все производят, ТАМ ЖЕ ВНУТРИ и потребляют. Поэтому снаружи от мясомолпрома ничего и нет...
М>кстати, интересно как вв на примере жванецкого объясняет различие между глобальными переменными (с учетом пространства имен) и локальными переменными (с учетом статических).
Никак.

Здравствуйте, LaptevVV, Вы писали:

N>>Сводя все КА к варианту определения "истинности", Вы 1) идёте вразрез с основными положениями теории, заложенными ещё в 40-х годах, 2) катастрофически ограничиваете применение теории, делая её непригодной для большинства практически важных случаев.
LVV>Нет.
LVV>Автомат-распознаватель и автомат-преобразователь — это разные вещи.

Это одна и та же вещь. Только в первом случае у неё выход — "да / нет / ещё не знаю, продолжайте кормить". Иногда первое или второе объединяются с третьим.

LVV>>>4. О состояниях у меня даже отдельной строкой...
N>>Которая точно так же непонятна без подробного разъяснения.
LVV>Конкретно, что именно не понятно. Что такое последовательность — мы, естественно, знаем? Или — нет?
LVV>Тогда, может, со школы начнем?

Пожалуйста, не передёргивайте. Вы знаете лучше меня, что знания, поданные так, что связь с известным опытом не очевидна, будут встречены непониманием. Это включает в себя и известные, но забытые факты, или непривычные связи. То, что строка — это последовательность, и что очередь вызовов — тоже последовательность, может теряться уже от того, что "строка" подразумевает текст. И уж тем более это будет затемнено, если рассуждать об автоматах, которые определяют кошерность строки.

LVV>>>"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"
N>>Сильно не уверен, что это их настолько радует. Ментальное поле за 30 лет существенно изменилось.
N>>Я уже того Жванецкого вспоминаю в лучшем случае раз в году...
LVV>Вы хотите сказать — сузилось.

В том, что Вы или даже я знали и держали в голове — сузилось. Во многом другом — расширилось.

LVV>Сейчас, например, большинство не знают, что такое гамма.
LVV>Не понимает, что стопка тарелок на кухне во время мытья — это стек.

Я бы тоже такое не соображал, потому что стопка тарелок на боку в моей сушке — это массив, а не стек.
А в раковине, как правило, тарелки навалены невпопад.
Проводя аналогии, надо всегда учитывать их адекватность представляемым реалиям.

LVV>Не соображает, что класс — это выкройка (штанов, например), а объект — это конкретные штаны, пошитые по этой выкройке.
LVV>Если ТС в соседнем сообщении не понимает, что такое состояние — о чем можно говорить?
LVV>В школу надо вернуться...

Я всё-таки подозреваю, что наличие в Вашем сообщении всяких "строк" слишком сбивает с толку.
А личные выпады в таких беседах обычно не украшают.

Здравствуйте, Grundik2, Вы писали:

G>Объясните простым языком что такое конечный автомат? Желательно с примерами.
КА это когда реакция на входное событие/воздействие зависит не только от самого события,
но и от некого состояния автомата. Например вам наступили на ногу в автобусе, а вы промолчали, вам еще раз наступили,
вы сказали больше так не делать, вам снова наступили, а вы дали в морду. Это и есть конечно-автоматное поведение — воздействие было
одно и тоже, ваше состояние и ответные действия менялись.

Здравствуйте, Аноним, Вы писали:

А> вам снова наступили, а вы дали в морду

Какой-то конченый автомат получается

You will always get what you always got
  If you always do  what you always did

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, LaptevVV, Вы писали:

N>>>Сводя все КА к варианту определения "истинности", Вы 1) идёте вразрез с основными положениями теории, заложенными ещё в 40-х годах, 2) катастрофически ограничиваете применение теории, делая её непригодной для большинства практически важных случаев.
LVV>>Нет.
LVV>>Автомат-распознаватель и автомат-преобразователь — это разные вещи.
N>Это одна и та же вещь. Только в первом случае у неё выход — "да / нет / ещё не знаю, продолжайте кормить". Иногда первое или второе объединяются с третьим.
Не совсем.
В автомате-преобразователе в каждом состоянии запускается некая функция. После ее работы устанавливается новое состояние...
А в автомате-распознавателе этого делать нет необходимости, достаточно просто установить новое состояние.
LVV>>>>4. О состояниях у меня даже отдельной строкой...
N>>>Которая точно так же непонятна без подробного разъяснения.
LVV>>Конкретно, что именно не понятно. Что такое последовательность — мы, естественно, знаем? Или — нет?
LVV>>Тогда, может, со школы начнем?
N>Пожалуйста, не передёргивайте. Вы знаете лучше меня, что знания, поданные так, что связь с известным опытом не очевидна, будут встречены непониманием. Это включает в себя и известные, но забытые факты, или непривычные связи. То, что строка — это последовательность, и что очередь вызовов — тоже последовательность, может теряться уже от того, что "строка" подразумевает текст. И уж тем более это будет затемнено, если рассуждать об автоматах, которые определяют кошерность строки.
N>Проводя аналогии, надо всегда учитывать их адекватность представляемым реалиям.
N>Я всё-таки подозреваю, что наличие в Вашем сообщении всяких "строк" слишком сбивает с толку.
N>А личные выпады в таких беседах обычно не украшают.
Прежде, чем вопросы на форумах задавать, ТС стоило бы сначала хоть что-то почитать.
А то он о состояниях судит по состояниям алкогольного опьянения.
И абстрактную машину сравнивает с вольво...
Подобный ОПЫТ я в сфере программирования учитывать не обязан.
Личных выпадов тут нет.
Сначала хотя бы со статьей Кодта пусть ознакомится — куда я его и послал.