Конечный автомат

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

Существуют различные варианты определения конечного автомата. Например, конечный автомат определяться как пятёрка

\boldsymbol{M = (K , \Sigma , \pi , s , F)}

Где K — конечное множество состояний автомата, s \in Kначальное состояние автомата, F \subset K — множество заключительных (или допускающих) состояний, причём допустимо F=Ø, и F=K, Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом, \pi : K \times \Sigma \rightarrow K — функция переходов. Автомат начинает работу в состоянии s, считывая по одному символы входной строки. Считанный символ переводит автомат в новое состояние из K, в соответствии с функцией переходов.

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

Другие способы описания

Существует два удобных способа описания автоматов.

  1. Диаграмма переходов, которая представляет собой граф.
  2. Таблица переходов, дающая табличное представление функции δ. Из нее очевидны состояния и входной алфавит.

Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет - так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home