Краен автомат

от Уикипедия, свободната енциклопедия

Табела за ремонт

Тази статия се нуждае от подобрение.

Необходимо е: препратки. Ако желаете да помогнете на Уикипедия, просто щракнете на редактиране и нанесете нужните корекции.


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

[редактиране] Описание

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

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

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

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

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

Два крайни автомата са еквивалентни, когато разпознават един и същи език. От всички еквивалентни автомати, разпознаващи даден език, този с най-малък брой състояния се нарича минимален.

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

Множеството на регулярните езици е равно на множеството на езиците, разпознавани от крайни автомати, т.е. всеки език, разпознаван от краен автомат, е регулярен (теорема на Клини (Kleene)). Това означава, че всеки регулярен израз може да се представи като краен автомат и обратното.

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