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

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

Формально конечный автомат определяется как пятёрка:

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

где

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

Автомат начинает работу в состоянии s, считывая по одному символы входной строки. Считанный символ переводит автомат в новое состояние из K, в соответствии с функцией переходов. Процесс продолжается до тех пор, пока не будет достигнуто одно из состояний F.

ВидыПравить

Конечный автомат M называется обратимым, если существует конечный автомат M1, такой, что по описанию автомата M, его начальному состоянию и произвольному выходному слову автомата M автомат M1 однозначно определяет входное слово.[1]

Зеркальный автомат — это автомат, в графе состояний которого направление стрелок, помеченных буквами входного алфавита, изменено на обратное, а входящие состояния заменены на допускающие, а допускающие на входящие состояния.[2]

СсылкиПравить