Крайните автомати са математически модели на много прости сметачни машини, които намират приложение най-вече в теоретичната информатика. Представляват абстрактни машини с крайна постоянна памет и краен брой вътрешни състояния.

Описание

Един краен автомат чете редица от символи (от входна азбука), наречена входна дума, и извежда също редица от символи (от изходна азбука), наречена изходна дума.

В зависимост от програмата си, крайният автомат притежава определен краен брой състояния, в които може да се намира. В началото се намира в едно специално състояние, наречено начално състояние.

Работата на един краен автомат се състои от определен брой стъпки, като на всяка стъпка той чете следващия символ на входната дума. В зависимост от прочетения символ и състоянието, в което се намира, автоматът извежда редица от изходни символи и преминава в ново състояние.

Крайните автомати биват детерминирани и недетерминирани. При детерминираните съществува само една възможност за прехода в ново състояние, докато при недетерминираните са възможни няколко различни прехода.

Съществува опростен вид, означаван като краен разпознавател, който не извежда изходни символи, а само спира след прочитането на входната дума или в разпознаващо състояние, или в неразпознаващо такова. В първия случай се казва, че автоматът разпознава думата, т.е. думата принадлежи на езика, разпознаван от автомата.

Друг вид крайни автомати са т.нар. Омега-автомати (ω-автомати), при които входната дума се състои от безкраен брой символи. При този модел разпознаването на дадена дума се описва чрез множеството от състояния, които се посещават безкраен брой пъти.

Множеството на регулярните езици е равно на множеството на езиците, разпознавани от крайни автомати, т.е. всеки език, разпознаван от краен автомат, е регулярен.

Крайният автомат може да се представи като насочен граф.

Изчислителни модели

Konečný automat | Endlicher Automat | Finite state machine | Autómata finito | Äärellinen automaatti | Automate fini | אוטומט סופי | Automa a stati finiti | 有限オートマトン | Eindige toestandsautomaat | Máquina de estado finito | Automat finit | Конечный автомат | Ändlig automat | 有限状态自动机