Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Где найти примеры конечных автоматов?  (Прочитано 22559 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Uana
Гость
« : 04-10-2004 13:26 » 

Где найти примеры конечных автоматов?
Где найти теорию и рализацию в программном коде?
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 04-10-2004 14:49 » 

Последняя статья Alf'а про рекурсию - там в общих чертах и с простейшим примером.

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

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

В любом случае для автомата нужно сформулировать цель его деятельности. Обычно их используют для распознавания образов в потоке входных символов. Возможно, выполнения некоторых действий при распознавании определённого образа. Так работают интерпретаторы/компиляторы языков, а также системы управления разными объектами, модули адаптации поведения  систем управления и т.д., и т.п...

Таблица переходов эквивалентна грамматике языка автомата - правилам перевода автомата из одного состояния в другое. Под языком понимается набор всех входных символов.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 04-10-2004 15:02 » 

Простейший автомат поведения льва Ага

Входные символы: "антилопа", "охотник".
Внутренние состояния: "сытый", "голодный".
Действия автомата: "съесть", "спать", "убежать"
Таблица переходов:
Код:

        |сытый                                |голодный
--------|-------------------------------------|---------------------------------
антилопа|спать, перейти в состояние голодный  |съесть, перейти в состояние сытый
--------|-------------------------------------|---------------------------------
охотник |убежать, перейти в состояние голодный|убежать


Условий завершения работы автомата здесь нет.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #3 : 04-10-2004 21:57 » 

Вот статьи про конечные автоматы
http://www.rsdn.ru/article/alg/FiniteStateMachine.xml
http://www.rsdn.ru/article/alg/checkStr.xml
http://www.rsdn.ru/article/alg/statemachine.xml
Записан
Uana
Гость
« Ответ #4 : 05-10-2004 08:19 » 

математическое описание туговато дается.
Множество внутренних состояний q? Таблица переходов автомата?
Какой бы пример  рассмотреть подробнее, и написать на него какую-нибудь программку.
Записан
Serega
Гость
« Ответ #5 : 11-10-2004 05:27 » 

Тут много про автоматы
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 14-08-2005 02:21 » 

Почему именно "конечные" автоматы? Это связано с конечностью состояний?
Внутренних?
Внешних?
Обоих?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #7 : 14-08-2005 10:56 » 

Количество состояний "Конечных" автоматов строго определено. Состояние  изменяется квантовано внешним воздействием.  Количество внешних воздействий не ограничено.
« Последнее редактирование: 14-08-2005 10:58 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines