Конечные автоматы, что там внутри?⁠⁠

Предыдущая статья: Графы автоматных грамматик. Что же, начинаем знакомиться с конечными автоматами? в vk.com

Если вы ознакомились со всеми прошлыми статьями, тогда вы готовы воспринять следующую информацию, я старался максимально кратко со всей ясностью подготовить вас, так-что попрошу вас заново перечитать. Приступаем, знакомимся с формулой конечного автомата:
A = (N, T, P, S, F)

Напоминает уже знакомую вам формулу грамматик? Давайте по порядку:
N - конечное множество состояний автомата, тот самый вспомогательный алфавит, плюс два или одно дополнительных состояния K и E, где E состояние ошибки и K дополнительное конечное состояние, если оно требуется.
Т - алфавит который принимает конечный автомат или тот самый основном алфавит грамматики.
P - функция переходов состояния автомата, принимает в себя текущее состояние автомата и подающий символ на рассмотрение, строится на основе правил вывода грамматики, ниже мы остановимся подробнее.
S - начальное состояние автомата.
F - множество конечных состояний автомата.

Ещё вы можете найти следующую формулу:
A = (N, T, O, δ, λ, F)
Где δ - функция переходов состояния автомата и записывают её так
δ : N × T → N означает что берется пара значений, одно из множества N, а другое из множества T и возвращает значение из множества N.
И λ - функция выходов, записывается λ : N × T → O , собственно O - означает выходной алфавит, или грубо говоря переводной. Например, сочтём за символы два слова, английское Hello из принимаемого алфавита и русское Привет из выходного алфавита, и во время работы автомата при некотором состоянии («контексте предложения»), принимает Hello и переводит его в Привет, ведь вполне может что в другом состоянии («контексте предложения») он может перевести его в Здравствуйте! =) Дальше повествование будет, только о автомате распознавателе, то есть без функции выходов, который описан выше, просто общий принцип функции переходов и выходов сильно не отличается.

Возьмем грамматику, я надеюсь уже любимого, языка идентификаторов:
G: S → aB
B → aB | bB | ε
И построим её граф.

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

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

Наверное вы заметили, что граф конечного автомата в прошлой статье и описанный в этой отличаются, хотя они принимают один и тот же язык? Об этом я расскажу в следующий раз, но перед этим я бы хотел показать вам программную реализацию КА на одном из языке программирования, на каком бы вы предпочли? Решение будет по результатам 3-его дня, после публикации статьи.

Опрос в vk.com у пикабушки нету =(
З. Ы. Подписывайтесь! =)