Википедия

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

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
викификация, оформление, дополнение, уточнение
Строка 1:
'''Коне́чный автома́т''' (КА) — [[абстрактный автомат]], число возможных внутренних состояний которого [[конечное множество|конечно]]. <!--РезультатПереход из состояния в другое состояние работыКА автоматапроизводит определяетсяот повнешнего еговоздействия конечномуили состояниюсамопроизвольно.-->
 
Примерами физической реализации КА могут служить любые цифровые системы, например, компьютеры или некоторые логические узлы компьютеров — [[триггер]]ы и другие устройства. Комбинационная последовательная логика не может являться КА, так как не имеет внутренних состояний.
 
С абстрактной точки зрения КА изучает раздел [[Дискретная математика|дискретной математики]] — ''теория конечных автоматов''.
 
КонечныеТеория автоматыконечных широкоавтоматов используютсяпрактически нашироко практикеиспользуется, например, в [[синтаксический анализатор|синтаксических]] и [[лексический анализатор|лексических анализаторах]], [[Тестирование программного обеспечения|тестировании программного обеспечения]] [[Тестирование на основе модели|на основе моделей]].▼
 
== Формальное описание конечного автомата ==
=== Общее описание ===
Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки элементов некоторых [[Множество (математика)|множеств]]:
: <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\colon Q \times ( V \cup \{ \varepsilon \} ) \rightarrow Q</math>, такое, что <math>\delta(q,a) = \{ r\colon q \,\,\underset{a}{\to}\,\, r \}</math>, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (''ε'').▼
 
▲: <math>M = (V, Q, q_0, F, \delta) ,</math>,
Принято полагать, что конечный автомат начинает работу в состоянии <math>q_0</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\colon Q \times ( V \cup \{ \varepsilon \} ) \rightarrow Q</math>, такое, что <math>\delta(q,a) = \{ r\colon q \,\,\underset{a}{\to}\,\, r \}</math>, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка символов) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (''ε'')символов, обычно обозначаемой буквой <math>\varepsilon.</math>
 
▲ПринятоПри анализе КА принято полагать, что конечный автомат начинает работу в некотором начальном состоянии <math>q_0</math>, последовательно считываяполучает по одному символу из входного слова (цепочки входных символов). Считанный символ переводитможет перевести автомат в новое состояние или не перевести в новое состояние в соответствии с функцией переходов.
 
ЧитаяПолучая входную цепочку символов <math>x</math> и делая переходы из состояния в состояние, автомат после прочтенияполучения последнего символа{{пояснить}}<!--Как автомат может знать, что слово закончилось?-->. входного слова окажется в некотором состоянии <math>q'</math>.
 
Если это состояние является заключительным, то говорят, что автомат допустил слово <math>x</math>{{пояснить}}<!-- Что такое заключительное состояние? Как автомат может знать, что слово закончилось?-->.
 
=== Другие способы задания функционирования КА ===
▲Конечные автоматы широко используются на практике, например, в [[синтаксический анализатор|синтаксических]] и [[лексический анализатор|лексических анализаторах]], [[Тестирование программного обеспечения|тестировании программного обеспечения]] [[Тестирование на основе модели|на основе моделей]].
{| class="wikitable" style="float:right; margin-left:1em; clear:right"
|+
! rowspan="2" |Исходное
состояние
! colspan="3" |Следующее состояние
|-
!Входной
символ a
!Входной
символ b
!Любой
другой
 
символ
== Другие способы описания ==
|-
|p0
|p1
|p0
|p0
|-
|p1
|p1
|p2
|p1
|-
|p2
|p3
|p4
|p2
|-
|p3
|p3
|p3
|p3
|-
|p4
|p4
|p4
|p4
|-
|p5
|p3
|p5
|p5
|}
# '''[[Диаграмма Мура|Диаграмма состояний]]''' (или иногда''' граф переходов''') — графическое представление множества состояний и функции переходов. Представляет собой размеченный ориентированный [[граф (математика)|граф]], вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а ''метки дуг'' — символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния ''q<sub>1</sub>'' в ''q<sub>2</sub>'' может быть осуществлен по одному из ''нескольких'' символов, то все они должны быть надписаны над дугой диаграммы.
# '''Таблица переходов''' — табличное представление функции ''δ''. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается состояние, в которое должен перейти автомат, если в данном состоянии он считал данный входной символ. Пример таблицы переходов для автомата, заданного в виде графа по рисунку 1 приведена справа.
 
== Детерминированность ==
{|align="right" cellpadding="0" cellspacing="0" style="margin-right:1em"
|-valign="top"
|[[Файл:ДКА.jpg|мини|Рисунок 1. Пример графа переходов детерминированного КА.]]
|[[Файл:НКА с e.jpg|мини|Рисунок 2. Пример графа переходов недетерминированного КА с самопроизвольными переходами]]
|}
[[Файл:НКА без e.jpg|мини|Рисунок 3. Недетерминированный автоматКА с переходами из одного состояния помеченнымив однимразные состояния ипри темодинаковом жевходном символомвоздействии]]▼
Конечные автоматы подразделяются на [[Детерминированный конечный автомат|детерминированные]] и [[Недетерминированный конечный автомат|недетерминированные]].
* Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором нет дуг с меткой ''ε'' (предложение, не содержащее ни одного символа), и из любого состояния по любому символу возможен переход не более, чем в одно состояние.
* Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов может достигаться двумя способами: либо могут существовать переходы, помеченныеиз состояние в состояние вызываемые пустой цепочкой εсимволов, т. е. самопроизвольные переходы без внешних воздействий, либо из одного состояния могутКА выходитьможет несколькопереходит переходов,в помеченныхразные однимсостояния под воздействием одного и темтого же символомсимвола.
<gallery mode="packed" heights="250px">
Файл:ДКА.jpg|Детерминированный конечный автомат
Файл:НКА с e.jpg|Недетерминированный автомат с пустыми переходами
▲Файл:НКА без e.jpg|Недетерминированный автомат с переходами из одного состояния помеченными одним и тем же символом
</gallery>
 
Если рассмотреть случай, когда автомат формально задан следующим образом: <math>M = (V, Q, S, F, \delta)</math>, где <math>S</math> — множество ''начальных состояний'' автомата, такое, что <math>S \subseteq Q</math>, то появляется третий признак недетерминированности — наличие нескольких начальных (стартовых) состояний у автомата <math>M</math>.
 
''Теорема о детерминизации''{{источник}} утверждает, что для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их языки совпадают{{пояснить}}). Однако поскольку количество состояний в эквивалентном ДКА в худшем случае растёт [[Экспоненциальный рост|экспоненциально]] с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, [[конечный автомат с выходом|конечные автоматы с выходом]] в общем случае не поддаются детерминизации.
 
В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА{{источник}}.
 
== Автоматы и регулярные языки ==
Строка 45 ⟶ 98 :
== Минимизация автоматов ==
{{Основная статья|Минимизация ДКА}}
Для любого регулярного языка существует единственный с точностью до [[Изоморфизм|изоморфизмаизоморфизм]]а автомат, принимающий этот язык и обладающий при этом наименьшим возможным числом состояний. Минимальный автомат для языка, заданного детерминированным конечным автоматом может быть осуществлена за полиномиальное время, что позволяет оптимизировать расход памяти, требуемый для работы с автоматом, а также решать такие задачи, как проверка эквивалентности двух автоматов за полиномиальное время.
 
== Специализированные языки программирования ==
* Язык последовательных функциональных схем [[SFC]] (Sequential Function Chart) — [[графический язык программирования]], широко используется для программирования промышленных логических контроллеров ([[Программируемый логический контроллер|ПЛК]]).
В графическом языке SFC программа описывается в виде схематической последовательности шагов, объединенныхобъединённых переходами.
 
== Разработка моделей с использованием конечных автоматов ==
Конечные автоматы позволяют построить модели систем параллельной обработки, однако, чтобы изменить число параллельных процессов в такой модели требуется внести существенные изменения в саму модель. Кроме того, попытка разработки сложной модели нареализованной конечномконечным автоматеавтоматом приведетприводит к быстрому росту числа состояний автомата, что в итоге сделает разработку такой модели крайне утомительным занятиемтрудоёмкой. Как было отмечено выше, последнюю проблему можно решить, если использовать недетерминированный автомат.
 
== Что может «делать» конечный автомат и последовательностная машина? ==
Ответ дается в различных терминах в зависимости от того, является ли автомат (соответственно П-машина) автономным или нет<ref>''Айзерман М. А., Гусев Л. А., Розоноэр Л. И., Смирнова И. М., Таль А. А.'' Логика. Автоматы. Алгоритмы. Гос. изд. физ.-мат. литературы 1963, 556 стр.</ref>. Автономный конечный автомат, начиная с некоторого такта, может лишь генерировать периодическую последовательность состояний '''х''' (соответственно П-машина — последовательность выходных символов '''y'''). Если эта последовательность состоит лишь из одного символа, то это означает, что за конечное число тактов автомат достигает равновесного состояния. Если же эта последовательность содержит несколько символов, это означает, что автомат последовательно проходит состояния, соответствующие этим символам, а затем работа автомата неограниченно долго периодически повторяется. Более того, какова бы ни была периодическая последовательность состояний конечной длины, всегда может быть построен автономный конечный автомат, который, начиная уже со второго такта, генерирует эту последовательность. Ничего иного, кроме периодического повторения одного и того же состояния или конечной последовательности состояний, автономный автомат «делать» не может. Однако в связи с тем, что последовательное выполнение заданного цикла операций типично для многих областей современной техники, динамические системы, которые в приемлемой идеализации можно рассматривать как автономный автомат, имеют широкое применение.
 
Классическим примером могут служить автоматы-куклы, выполнявшие сложные последовательности действий, например: пишущие на бумаге определенныйопределённый текст, играющие на рояле заранее установленные пьесы т. д.
 
Современным примером служат многие станки-автоматы, автоматические линии и системы автоматического управления циклическими производствами. Если автомат не автономен, то есть состояние входа изменяется от такта к такту, то ответ на вопрос, что может «делать» и что не может «делать» конечный автомат, можно дать в разных терминах. Например, ответ можно сформулировать на языке представления событий. Действительно, неавтономный конечный автомат или последовательностная машина лишь преобразуют входные последовательности символов в последовательности состояний или выходных символов, и сказать, что может и что не может «делать» конечный автомат, значит выяснить, какие преобразования последовательностей возможны в конечном автомате, а какие невозможны. Но так как количество состояний (соответственно выходных символов) конечно, этот вопрос эквивалентен такому вопросу: при каких входных последовательностях возникает каждое из возможных состояний (или каждый из выходных символов). Этот последний вопрос в терминах, принятых в теории конечных автоматов, формулируется так: какие события могут и какие не могут быть представлены в конечном автомате каждым из возможных состояний (или каждым из выходных символов).
Строка 81 ⟶ 134 :
* [[Секвенциальная логика]] (Последовательностная логика)
* [[Таблица принятия решений]]
* [[Суффиксный автомат]]
 
== Литература ==
Строка 90 ⟶ 143 :
|издательство=МГТУ
|год=2006
|страницы=460-587460—587
|isbn=5-7038-2886-4}}
* {{книга
Строка 107 ⟶ 160 :
* Теория автоматов / ''Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко'' // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109—188. — URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
* [http://robot-develop.org/archives/1440#more-1440 Применение конечных автоматов для решения задач автоматизации]
* [[Глушков, Виктор Михайлович|''Глушков В. М.'']]. Синтез цифровых автоматов.  — М.: [[Физматлит|ГИФМЛ]], 1962.  — 476 с.
 
== Ссылки ==
Источник — https://ru.wikipedia.org/wiki/Конечный_автомат