Коначан аутомат
Из Википедије, слободне енциклопедије
Коначни аутомат је модел понашања који се састоји од коначног скупа стања, прелаза између стања, и има придружених акција.
[уреди] Концепти и речник
Стање аутомата складишти информацију о прошлости, то јест рефлектује промену улаза од почетка рада до тренутне фазе израчунавања. Прелаз означава промену стања, и описан је условом за који је неопходно да буде испуњен да би дошло до прелаза. Акција је опис активности која се спроводи у датом моменту.
Коначни аутомат се састоји од:
- коначног скупа U улазних симбола
- коначног скупа I излазних симбола
- коначног скупа S стања
- функције прелаза стања f:SxU -> S
- функције излаза g: SxU -> I
- почетног стања система σ*
Оваква коначна машина се означава са М=(U, I, S, f, g, σ*).
Коначни аутомат је таква коначна машина код које је I = {0,1}, где је излаз одређен следећим стањем машине.
| Теорија аутомата: формални језици и формалне граматике | |||
|---|---|---|---|
| Хијерархија Чомског |
Граматике | Језици | Минимални аутомат |
| Тип-0 | Без ограничења | Рекурзивно пребројиви | Тјурингова машина |
| % | (без уобичајеног имена) | Рекурзивни | Одлучивач |
| Тип-1 | Контекст сензитивна | Контекст сензитивни | Линеарно-ограничени |
| % | Индексирана | Индексиран | Угњеждени стек |
| Тип-2 | Контекст-слободна | Контекст-слободни | Недетерминистички потисни |
| % | Детерминистичка контекст-слободна | Детерминистички контекст-слободни | Детерминистички потисни |
| Тип-3 | Регуларна | Регуларан | Коначни |
| Свака категорија језика или граматика је прави подскуп категорије директно изнад ње. | |||
 |
Овај незавршени чланак Коначан аутомат везан је за математику. Користећи правила Википедије, проширите га. |
 |
Овај незавршени чланак Коначан аутомат је везан за технологије. Користећи правила Википедије, проширите га. |
