|
'''Коне́чный автома́т''' (сокращённо — «'''КА'''») — [[абстрактный автомат]], число возможных внутренних [[Состояние|состояний]] которого [[конечное множество|конечно]]. <!--Результат работы автомата определяется по его конечному состоянию.-->
Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятёркипятерки элементов некоторых [[Множество (математика)|множеств]]: ▼
Результат работы автомата определяется по его конечному состоянию.
=== Способы задания алгоритма функционирования КА ===
Существуют различные способы задания [[Алгоритм функционирования|алгоритма функционирования]] конечного автомата.
==== Задание в виде упорядоченной пятёрки элементов ====
▲Например, конечный автомат может быть задан в виде упорядоченной пятёрки элементов некоторых [[Множество (математика)|множеств]]:
: <math>~M = (V, Q, q_0, F, \delta) </math>,
где
* <math>V</math> — ''входной алфавит'' (конечное множество ''входных символов''), из которого формируются ''входные слова'', воспринимаемые конечным автоматом;
* <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>, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).
Принято полагать, что конечный автомат начинает работу в состоянии «''q<sub>0</sub>'' », последовательно считывая по одному символу входного слова (цепочки входных символов). Считанный символ — переводит автомат в новое [[состояние ]], в соответствии с функцией переходов. ▼
Читая входную цепочку символов ''x'' и делая переходы из состояния в состояние, автомат после прочтения последнего символа входного слова окажется в некотором состоянии ''q'''.
▲Принято полагать, что конечный автомат начинает работу в состоянии «''q<sub>0</sub>''», последовательно считывая по одному символу входного слова (цепочки входных символов). Считанный символ — переводит автомат в новое [[состояние]], в соответствии с функцией переходов.
Читая входную цепочку символов «''x''» и делая переходы из [[Состояние|состояния]] в [[состояние]] — автомат, после прочтения последнего символа входного слова, окажется в некотором состоянии: «''q'''». Если это состояние является заключительным, то говорят, что автомат допустил слово «''x''».
*Конечные Приавтоматы широко используются на практике, например, в [[синтаксический анализатор|синтаксических]] и [[лексический анализатор|лексических анализаторах]], [[Тестирование программного обеспечения|тестировании программного обеспечения]] [[Тестирование на основе модели|на основе моделей]]. ▼=== Применение КА на практике ===
Конечные автоматы широко используются на практике, — например:
* В [[синтаксический анализатор|синтаксических]] и [[лексический анализатор|лексических анализаторах]];
▲* При [[Тестирование программного обеспечения|тестировании программного обеспечения]] [[Тестирование на основе модели|на основе моделей]].
== Другие способы описания ==
# «'''[[Диаграмма Мура|Диаграмма состояний]]'''» (или, — иногда, — «''' граф переходов'''») — графическое представление [[Пространство состояний (теория управления)|множества состояний]] и функции переходов. Представляет собой размеченный ориентированный [[граф (математика)|граф]], вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а ''метки дуг'' — символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния ''q<sub>1</sub>'' в ''q<sub>2</sub>'' может быть осуществлен по одному из ''нескольких'' символов, то все они должны быть надписаны над дугой диаграммы.
# «'''Таблица переходов'''» — табличное представление функции ''δ''. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается состояние, в которое должен перейти автомат, если в данном состоянии он считал данный входной символ.
== Детерминированность ==
Конечные автоматы подразделяются на детерминированные и недетерминированные.
Подразделение конечных автоматов:
[[Файл:ДКА.jpg|thumb|300px|right|Детерминированный конечный автомат]]
* Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором нет дуг с меткой ''ε'' (предложение, не содержащее ни одного символа), и из любого состояния по любому символу возможен переход в точности в одно состояние.
* «Детерминированный» конечный автомат («'''ДКА'''»; см. иллюстрацию):
* «Недетерминированный » конечный автомат ( «'''НКА '''») — является обобщением «детерминированного ». Недетерминированность автоматов достигается двумя способами: ▼** Не имеет дуг с меткой ''ε'' (предложение, не содержащее ''ни одного'' символа);
** Из любого состояния, по любому символу — возможен переход в точности ''в одно'' состояние;
▲* «Недетерминированный» конечный автомат («'''НКА'''») — является обобщением «детерминированного». Недетерминированность автоматов достигается двумя способами:
{| align="center" class="standard"
== Разработка моделей с использованием конечных автоматов ==
Конечные автоматы позволяют построить модели систем параллельной обработки;, однако, чтобы изменить число параллельных процессов в такой модели — требуется внести существенные изменения в саму модель. Кроме того, попытка разработки сложной модели на конечном автомате приведётприведет к быстрому росту числа состояний автомата, что в итоге сделает разработку такой модели крайне утомительным занятием. Как было отмечено выше, последнюю проблему можно решить, если использовать недетерминированный автомат.
== Что может «делать» конечный автомат и последовательностная машина? ==
Ответ даётсядается в различных терминах в зависимости от того, является ли автомат (соответственно П-машина) автономным или нет<ref>''Айзерман М. А., Гусев Л. А., Розоноэр Л. И., Смирнова И. М., Таль А. А.'' Логика. Автоматы. Алгоритмы. Гос. изд. физ.-мат. литературы 1963, 556 стр.</ref>. Автономный конечный автомат, начиная с некоторого такта, может лишь генерировать периодическую последовательность состояний '''х''' (соответственно П-машина — последовательность выходных символов '''y'''). Если эта последовательность состоит лишь из одного символа, то это означает, что за конечное число тактов автомат достигает равновесного состояния. Если же эта последовательность содержит несколько символов, это означает, что автомат последовательно проходит состояния, соответствующие этим символам, а затем работа автомата неограниченно долго периодически повторяется. Более того, какова бы ни была периодическая последовательность состояний конечной длины, всегда может быть построен автономный конечный автомат, который, начиная уже со второго такта, генерирует эту последовательность. Ничего иного, кроме периодического повторения одного и того же состояния или конечной последовательности состояний, автономный автомат «делать» не может. Однако в связи с тем, что последовательное выполнение заданного цикла операций типично для многих областей современной техники, динамические системы, которые в приемлемой идеализации можно рассматривать как автономный автомат, имеют широкое применение.
Классическим примером могут служить автоматы-куклы, выполнявшие сложные последовательности действий, например: пишущие на бумаге определенный текст, играющие На рояле заранее установленные пьесы т. д.
| 