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

Давай, реализуй, любопытно...
Правда, как тут с быстродействием? Реализованный на С (я опять за свое :) ) подобный автомат обрабатывает на современных PC десятки миллионов входных символов в секунду. Сколько сделает на том же PC SQL сервер?

Хотя, может я и не прав... Например можно организовать движение бизнес-документа из состояния в состояние в зависимости от неких внешних воздействий. (если вся логика на каком-нить SQL-сервере) Тут быстродействия не требуется. :)

2 tchingiz

vdimas>последнего встретившегося конечного состояния
последнее всретившееся конечное состояние это что?
оно отлично от первого встретившегося КОНЕЧНОГО состояния?
типа икра второй свежести?

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

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

пример:
имеем автомат, разбирающий идентификаторы (пишу упрощенно),
целевое регулярное выражение (прим., класс регулярных формальных грамматик представим в виде конечного автомата)
id = буква ( буква | цифра )*

имеем:
Q {S0, S1},
T {буква, цифра, другой_символ},
d { (S0 x буква -> S1), (S1 x буква -> S1), (S1 x цифра -> S1) }
q0 { S0 }
F { S1 }

имеем входную последовательность:
"m_field123=456;"

Очевидно, что автомат попадет в состояние S1 на первом же шаге. Однако, мы заинтересованы в том, чтобы он отработал до знака "=".

2 c127

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

Заключительные состояние автомата - это просто то множество состояний, которые могут рассматриваться как потенциально-заключительные, и нигде не указано, что по достижении заключительного состояния автомат заканчивает цикл своей работы. Большинство известных автоматов как раз работают до "самого далекого" заключительного состояния. С т.з. физического смысла, заключительное состояние - это валидное состояние, некий выходной сигнал. Все остальные - промежуточные состояния.

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

2 ShgGena

Помимо всего прочего, различают синхронную и ассинхронную модель КА.
Так вот, реализация синхронного КА не требует оператора цикла. Предполагается, что за каждый запуск (запуск извне!!!!!), автомат делает ровно 1 шаг, т.е. просто переходит из состояние в состояние. Как раз именно это и возможно на SQL.

Как именно:
Создаем процедуру, которая за каждый свой вызов совершает ровно 1 шаг моделируемого автомата. Таблица-"лента", разумеется не нужна по своей физической сути, ибо вход КА - некий закодированный набор сигналов (внешних разражителей). В связи с самим определением КА, этот набор сигналов вполне конечен, и может быть представен в виде набора кодов - терминальных символов. Т.е. "входная лента", это по-сути или данные, подаваемые на каждом шаге на вход процедуры, либо некие извлекаемые и кодируемые данные из самой базы, либо любое их сочетание.

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

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

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

Далее, вопрос насчет Мура и Милли стоять не должен в принципе.
Software-реализация автомата подразумевает синхронную модель. Для этой модели автомат Мура требует в большинстве случаев меньше суммарных данных (в байтах :) ) для описания. (ключевое слово - в большинстве)
Для асинхронного автомата модель Милли, разумеется, гораздо предпочтительнее, но! программное моделирование асинхронных автоматов - IMHO, развлечение из области занятных, однако абсолютно бесполезных. (кто гарантирует, через сколько минимальных циклов апрокцимации "утрясется" асинхронный автомат?)

2 с127
Никто не запрещает n дать свое определение конечного автомата

гхм, гхм...
дать ссылку на твои придирки к "групповым операциям"?