Краен автомат: Разлика между версии

форматиране: 2x нов ред, 5 интервала, тире (ползвайки Advisor)
м (без right/дясно в картинки (x3))
(форматиране: 2x нов ред, 5 интервала, тире (ползвайки Advisor))
'''Крайните автомати''' са математически модели на много прости [[Сметачна машина|сметачни машини]], които намират приложение най-вече в [[Теоретична информатика|теоретичната информатика]] и по-специално в изучаването на [[формални езици|формалните езици]] и [[изкуствен интелект|изкуствения интелект]]. Те представляват абстрактни машини с крайна постоянна памет и краен брой вътрешни състояния.
 
== Описание ==
Крайните автомати четат редица от символи (от ''входна азбука''), наречена ''входна дума'', и извеждат също редица от символи (от ''изходна азбука''), наречена ''изходна дума''. Множеството от всички входни думи се нарича език, разпознаван от автомата.
 
В зависимост от програмата си, крайният автомат притежава определен краен брой състояния, в които може да се намира. ''Начално състояние'' е състоянието, в което се намира автомата при започване на програмата.
 
Работата на крайните автомати се състои от определен брой стъпки, като на всяка стъпка се чете следващият символ на входната дума. В зависимост от прочетения символ и състоянието, в което се намира, автоматът извежда редица от изходни символи и преминава в ново състояние.
За да получим състоянията и преходите на детерминирания краен автомат, съставяме следната таблица:
{| border="1" cellspacing="0"
!
! a
! b
 
== ω-автомати ==
Друг вид крайни автомати са т.нар. '''Омега-автомати''' (ω-автомати), при които входната дума се състои от безкраен брой символи. При този модел разпознаването на дадена дума се описва чрез множеството от състояния, които се посещават безкраен брой пъти.
 
== Автомат с ε-преходи ==
Това е автомат в който някои от преходите са с празни (ε) етикети, т.е. преминаването през даден преход не променя думата. За да елиминираме ε-преходите, първо трябва да наситим автомата с ε-преходи и след това да ги заместим със съответните преходи с букви. Това действие се използва например в конкатенацията на два автомата.
 
== Запълнен автомат ==
Например ако вземем трансдуктора от картинката, за думата bbaa ще получим 0110.
 
Има два вида трансдуктори – [[автомат на Мили]] и [[автомат на Мур]].
 
== Регулярни езици ==
== Забележки ==
<references />
 
 
[[Категория:Теоретична информатика]]