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

Здравствуйте, 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>А личные выпады в таких беседах обычно не украшают.
Прежде, чем вопросы на форумах задавать, ТС стоило бы сначала хоть что-то почитать.
А то он о состояниях судит по состояниям алкогольного опьянения.
И абстрактную машину сравнивает с вольво...
Подобный ОПЫТ я в сфере программирования учитывать не обязан.
Личных выпадов тут нет.
Сначала хотя бы со статьей Кодта пусть ознакомится — куда я его и послал.

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

LVV>>>Автомат-распознаватель и автомат-преобразователь — это разные вещи.
N>>Это одна и та же вещь. Только в первом случае у неё выход — "да / нет / ещё не знаю, продолжайте кормить". Иногда первое или второе объединяются с третьим.
LVV>Не совсем.
LVV>В автомате-преобразователе в каждом состоянии запускается некая функция. После ее работы устанавливается новое состояние...
LVV>А в автомате-распознавателе этого делать нет необходимости, достаточно просто установить новое состояние.

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

N>>А личные выпады в таких беседах обычно не украшают.
LVV>Прежде, чем вопросы на форумах задавать, ТС стоило бы сначала хоть что-то почитать.
LVV>А то он о состояниях судит по состояниям алкогольного опьянения.
LVV>И абстрактную машину сравнивает с вольво...
LVV>Подобный ОПЫТ я в сфере программирования учитывать не обязан.

jIMHO, это не опыт. Это психологическая защитная реакция на откровенный пригруз.
Разумеется, эта реакция показывает отсутствие достаточного жизненного опыта, который бы посоветовал сказать что-то в духе "Проф, не грузите попусту, я ничего не понял. Прошу найти другие слова." Как говорил один классик, "ещё 3000 лет назад писали, что молодёжь ленива, невоспитанна и распущенна. С тех пор ничего не изменилось. Наверно, это наследственное."
Но я с ним согласен в том смысле, что надо более адекватно вводить контекст. Даже классическое определение автомата как тройки из множества входных значений, множества состояний и функции перехода лучше, чем введение какой-то "машины", которая сразу вызывает кучу разносторонних и несочетаемых ассоциаций. А в программировании, ящетаю(tm), по крайней мере для процедурных языков, объяснение таких вещей должно происходить иллюстрацией процесса во времени.

Кстати, вот подумал — всё-таки техника старых времён имела то преимущество, что наглядно иллюстрировала прохождение выполнения программ по шагам и по связям между шагами. Умножение чисел на арифмометре "Феликс" было дешёвым способом и прочувствовать алгоритм (механически! моторная память тут очень помогает), и оценить последствия каждой ошибки (лишний или недостаточный сдвиг или поворот). Смартфоны не дадут такой опыт

LVV>Личных выпадов тут нет.
LVV>Сначала хотя бы со статьей Кодта пусть ознакомится — куда я его и послал.

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

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

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

Если вы так же читаете лекции, то не завидую вашим студентам.

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

LVV>>В автомате-преобразователе в каждом состоянии запускается некая функция. После ее работы устанавливается новое состояние...
LVV>>А в автомате-распознавателе этого делать нет необходимости, достаточно просто установить новое состояние.
N>В таком случае, распознаватель является частным случаем преобразователя с тривиальной функцией реакции на входное изменение, которая ничего не делает
Естественно.
Собственно, автомат преобразователь появился из практических нужд — надо же константы преобразовывать в двоичную форму...
http://inter-vuz.tuit.uz/Elib_baza//INTUIT.ru/html/department/ds/introsaa/4/1.html

LVV>>Прежде, чем вопросы на форумах задавать, ТС стоило бы сначала хоть что-то почитать.
LVV>>А то он о состояниях судит по состояниям алкогольного опьянения.
LVV>>И абстрактную машину сравнивает с вольво...
LVV>>Подобный ОПЫТ я в сфере программирования учитывать не обязан.
N>jIMHO, это не опыт. Это психологическая защитная реакция на откровенный пригруз.
Знаешь, опять повторю: прежде, чем задавать вопрос на форуме, я пытаюсь максимально самостоятельно разобраться в теме. И только если нифига не доходит — пишу вопрос.
У меня был один знакомый программер, который постоянно бегал ко мне с вопросами по всяким мелочам. В конце-концов я его прямо спросил: почему я это знаю, а ты нет — ведь ты старше меня и должен быть опытнее.
Причина была именно в том, что чел предпочитал СПРОСИТЬ, а не докопаться самому. Он так и сказал: так ЛЕГЧЕ.
N>Разумеется, эта реакция показывает отсутствие достаточного жизненного опыта, который бы посоветовал сказать что-то в духе "Проф, не грузите попусту, я ничего не понял. Прошу найти другие слова." Как говорил один классик, "ещё 3000 лет назад писали, что молодёжь ленива, невоспитанна и распущенна. С тех пор ничего не изменилось. Наверно, это наследственное."

Но молодежь же надо воспитывать!
Вот я довольно часто у нынешних 2-3 курсах спрашиваю: ты где и КЕМ работать будешь. В 99% случаев ответ — не знаю...
Хотя некоторые уже работают...
Так и тут: ничего не понимаю. А конкретнее? И выясняется, что студент даже не пытался что-то прочитать и хоть как-то понять.
За 20 лет в универе — насмотрелся.
N>Но я с ним согласен в том смысле, что надо более адекватно вводить контекст. Даже классическое определение автомата как тройки из множества входных значений, множества состояний и функции перехода лучше, чем введение какой-то "машины", которая сразу вызывает кучу разносторонних и несочетаемых ассоциаций. А в программировании, ящетаю(tm), по крайней мере для процедурных языков, объяснение таких вещей должно происходить иллюстрацией процесса во времени.
Должно.
И мы об этом в своем Семантике думаем...
N>Кстати, вот подумал — всё-таки техника старых времён имела то преимущество, что наглядно иллюстрировала прохождение выполнения программ по шагам и по связям между шагами. Умножение чисел на арифмометре "Феликс" было дешёвым способом и прочувствовать алгоритм (механически! моторная память тут очень помогает), и оценить последствия каждой ошибки (лишний или недостаточный сдвиг или поворот). Смартфоны не дадут такой опыт
Да, именно так.
Когда даже не на Феликсе, а на ЭЛКЕ сделаешь численный метод ручками — вопросов практически не остается.
LVV>>Личных выпадов тут нет.
LVV>>Сначала хотя бы со статьей Кодта пусть ознакомится — куда я его и послал.
N>Ваша позиция понятна, но я всё равно думаю, что это не идеальный способ понять концепции состояния и воздействия.
Не знаю. У меня в свое время почему-то проблем с изучением конечных автоматов не возникло ну просто никаких.
Интересно было! Я помнится, на ассмеблере ЕС запрограммировал автомат перевода целого в двоичную систему...

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

LVV>На входе — последовательность элементов. Чаще всего — строка символов.
LVV>КА рассматривает эту последовательность символов, и выдает ответ, принадлежит ли эта строка некоему языку или нет.

КА, вообще-то, выдаёт ответ — последовательность переходов (автомат Мили) или последовательность входов в состояния (автомат Мура).
Автоматы Мили и Мура изоморфны.

Частным случаем, когда содержательный вывод находится в двух финальных состояниях, и будет "принадлежит/нет".

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

Более сложный случай — FST, finite state transformer, — имеет содержательный вывод на промежуточных состояниях.

Примеры FST:
— Вся железная схемотехника; количество состояний определяется количеством регистров или триггеров.
— Регекспы, как ни странно! Скобки в регекспах видели? Они нужны для сегментации, а сегментация — это как раз выводы (ага! скобка!) на промежуточных состояниях.
— Распознавание речи. По-хорошему, человеческий язык — вообще контекстно-зависимый, но грубое приближение — это n-граммы и конечные фразы. Глупо вытаскивать фразу целиком в конечное состояние (получается комбинаторный взрыв), если можно выводить отдельные слова этой фразы по ходу распознавания. Опять же, сегментация.

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

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

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

ну и добавлю.. если ТС совсем захочется знать теорию, то КА частный вариант цепей Маркова... хм.. если конечно матрицу переходных вероятностей представлять с 1 единицами и в конечном пространстве...

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

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

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

Вышеприведенный текст (с небольшим дополнением) в виде конечного автомата.

Состояния:
— Еду в автобусе, лепота! (Еду)
— Еду в автобусе, WTF? (WTF)

События (входные символы):
— Наступили на ногу
— Прошло 5 минут

Действия системы:
— многозначительно промолчать
— дать в морду

Таблица переходов. Будем записывать таблицу переходов в виде "Состояние + событие = новое состояние (действие)". Т.е. если конечный автомат находиться в некотором "состоянии" и происходит некоторое "событие", то автомат переходит в состояние "новое состояние", возможно при этом выполняя некоторое "действие":

Еду + Наступили на ногу = перейти в состояние WTF (во время перехода в новое состояние "многозначительно промолчать")
WTF + Наступили на ногу = перейти в состояние Еду (во время перехода в новое состояние "дать в морду")
Еду + прошло 5 минут = перейти в состояние Еду
WTF + прошло 5 минут = перейти в состояние Еду

Стартовое состояние автомата — Еду

По сравнение с текстом добавил событие "прошло 5 минут". По хорошему надо бы добавить еще одно состояние автомата — конечное состояние "вышел из автобуса", в которое автомат попадает когда происходит событие "моя остановка".

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

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

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

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

что делает ее конечным автоматом? почему автоматом? можете привести пример?

G>что делает ее конечным автоматом? почему автоматом? можете привести пример?

ты наверно слышал про машины тьюринга

так вот основное свойство конечного автомата -- это то что это НЕ машина Тьюринга.

У машины Тьюринга есть бесконечная лента, а у конечного автомата нет.

Фактически: конечный автомат -- это машина тьюринга которую не снаблили бесконечной лентой.

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

G>что делает ее конечным автоматом?

Ну так, число классов эквивалентности предисторий конечное. В этом и смысл названия.

G>почему автоматом?

Ну автомат, машина. Здесь надо разобраться, что такое машина. Мне нравится определение Марвина Минского: машина -- это модель какого-то процесса. Под процессом подразумевается последовательность событий, протекающих во времени. Модель этой последовательности, понятно, задающая причинно-следственные связи между событиями, и есть машина (автомат). Машина -- это частный случай того, как человек смотрит на Мир. Человек этот Мир моделирует. Если для модели время не играет важной роли, оно отбрасывается и получаем объекты, признаки, отношения между ними и т.п.. Это то, что называется модель ситуации. Если в модели время существенно, то это модель процесса -- машина.

Вообще, есть хорошая книжка Марвина Минского на эту тему: Вычисления и автоматы

G>можете привести пример?

Ну сколь угодно много. Например, пусть во внешней среде имеется два типа сигналов, обозначим их символами "a" и "b". Когда машина начала свое существование нам неизвестно, этот момент утерян где-то во глубине веков. Наша машина будет выдавать сигнал "!", если было два подряд входных сигнала "+", и сигнал "-" -- в противном случае. Предыстории задаются последовательностями (бесконечными, ведь время начала существования машины неизвестно) символов алфавита V = {a,b}. Эти последовательности (предыстории) разобьем на два класса эквивалентности: те, которые заканчиваются на aa, и все остальные. Т.е. имеем:

Класс "aa":

...aababababaa
...bbbbbbbbbaa
...aaaaaaaaaaa
...

Класс "остальные":

...aaaaaaaaaab
...bbbbbbbbbbb
...bbbbbbbbbba
...

Вот эти два класс и есть память системы -- ее состояниям. Каждый раз, получая на вход очередной символ, машина получает новую предысторию входных событий. Таким образом естественно совершается переход в соответствующий класс предысторий -- состояние машины.

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

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

Была, но мало. Фактически её производство рассчитывалось только на город, а из города она вывозилась.

М> легенды о добавлении бумаги опровергались тем, что 1 кг бумаги в ссср стоил дороже 1 кг мяса.

По сравнению с городской дотационной ценой (2.20-2.80 для чего-то приличного) — да. По сравнению с реальной (6-9) — нет.

Это одна из ключевых особенностей СССР: не так страшна была плановая экономика сама по себе — она и так практически везде плановая в ключевых отраслях. Но плановая экономика в сочетании с неестественным ценообразованием, дотациями на одно и намеренными завышениями на другое, принципиально не могла работать. Никакие конечные автоматы и машины Тьюринга (в виде компьютеров) этому не помогут

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

Присоединяюсь, я бы тоже послушал.

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

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

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

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

Б>Вышеприведенный текст (с небольшим дополнением) в виде конечного автомата.

Б>Состояния:
Б>- Еду в автобусе, лепота! (Еду)
Б>- Еду в автобусе, WTF? (WTF)


Хорошее объяснение. Простое, понятное.

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

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

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

M>Есть некоторая система, которая взаимодействует с окружающей средой. На вход от среды система получает какие-то сигналы, в ответа сама что-то выдает. Чтобы система делала что-то более-менее умное, ей необходимо запоминать историю входных сигналов и от этой истории что-то выдавать в ответ.

То есть, если у нас есть класс с состоянием, которые нельзя изменить:

class MyClass1(val a: Int) {
  def func1(b: Int) = a * b
}

это не конечный автомат, потому что класс не может изменить своего состояния, потому что a — это константа и может быть задано только один раз (в C# это const a)?

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

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

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

после того, как мне 3 раз наступили на ногу, состояние сбрасывается к первоначальному? или оно сбрасывается только на следующий день?

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

G>что делает ее конечным автоматом? почему автоматом? можете привести пример?
а) конечным автоматом её делает конечность множеств состояний, входных сигналов и выходных сигналов;
б) автоматом, потомку что работает автоматически, без участия человека;
в) пример — Электрувер Трурля (известен также как Электрибальд).