Конечный автомат: различия между версиями

'''Коне́чный автома́т''' (сокращённо — «'''КА'''») — [[абстрактный автомат]], число возможных внутренних [[Состояние|состояний]] которого [[конечное множество|конечно]]. <!--Результат работы автомата определяется по его конечному состоянию.-->

* <math>Q</math> — ''множество внутренних [[Состояние|состояний]]'';

* <math>q_0</math> — ''начальное [[состояние]]'' <math>(q_0 \in Q)</math>;

* <math>F</math> — множество ''заключительных, или конечных [[Состояние|состояний]]'' <math>(F \subset Q)</math>;

* <math>\delta</math> — ''функция переходов'', определеннаяопределённая как отображение <math>\delta : Q \times ( V \cup \{ \lambda \} ) \rightarrow Q</math>, такое, что <math>\delta(q,a) = \{ r : q \rightarrow_a r \}</math>, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).

Читая входную цепочку символов «''x''» и делая переходы из [[Состояние|состояния]] в [[состояние]] — автомат, после прочтения последнего символа входного слова, окажется в некотором состоянии: «''q'''». Если это состояние является заключительным, то говорят, что автомат допустил слово «''x''».

# «'''[[Диаграмма Мура|Диаграмма состояний]]'''» (или, — иногда, — «''' граф переходов'''») — графическое представление [[Пространство состояний (теория управления)|множества состояний]] и функции переходов. Представляет собой размеченный ориентированный [[граф (математика)|граф]], вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а ''метки дуг'' — символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния ''q₁'' в ''q₂'' может быть осуществлен по одному из ''нескольких'' символов, то все они должны быть надписаны над дугой диаграммы.

# «'''Таблица переходов'''» — табличное представление функции ''δ''. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается состояние, в которое должен перейти автомат, если в данном состоянии он считал данный входной символ.

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

Ответ даетсядаётся в различных терминах в зависимости от того, является ли автомат (соответственно П-машина) автономным или нет<ref>''Айзерман М. А., Гусев Л. А., Розоноэр Л. И., Смирнова И. М., Таль А. А.'' Логика. Автоматы. Алгоритмы. Гос. изд. физ.-мат. литературы 1963, 556 стр.</ref>. Автономный конечный автомат, начиная с некоторого такта, может лишь генерировать периодическую последовательность состояний '''х''' (соответственно П-машина — последовательность выходных символов '''y'''). Если эта последовательность состоит лишь из одного символа, то это означает, что за конечное число тактов автомат достигает равновесного состояния. Если же эта последовательность содержит несколько символов, это означает, что автомат последовательно проходит состояния, соответствующие этим символам, а затем работа автомата неограниченно долго периодически повторяется. Более того, какова бы ни была периодическая последовательность состояний конечной длины, всегда может быть построен автономный конечный автомат, который, начиная уже со второго такта, генерирует эту последовательность. Ничего иного, кроме периодического повторения одного и того же состояния или конечной последовательности состояний, автономный автомат «делать» не может. Однако в связи с тем, что последовательное выполнение заданного цикла операций типично для многих областей современной техники, динамические системы, которые в приемлемой идеализации можно рассматривать как автономный автомат, имеют широкое применение.