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