Коначан аутомат

Из Википедије, слободне енциклопедије

Коначни аутомат је модел понашања који се састоји од коначног скупа стања, прелаза између стања, и има придружених акција.

Концепти и речник[уреди]

Стање аутомата складишти информацију о прошлости, то јест рефлектује промену улаза од почетка рада до тренутне фазе израчунавања. Прелаз означава промену стања, и описан је условом за који је неопходно да буде испуњен да би дошло до прелаза. Акција је опис активности која се спроводи у датом моменту.

Коначни аутомат се састоји од:

  • коначног скупа U улазних симбола
  • коначног скупа I излазних симбола
  • коначног скупа S стања
  • функције прелаза стања f:SxU -> S
  • функције излаза g: SxU -> I
  • почетног стања система σ*

Оваква коначна машина се означава са М=(U, I, S, f, g, σ*).
Коначни аутомат је таква коначна машина код које је I = {0,1}, где је излаз одређен следећим стањем машине.

Види још[уреди]

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Коначан аутомат
Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.