Детерминистички коначни аутомат

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

У теорији израчунавања, детерминистички коначни аутомат (ДКА) je коначни аутомат у коме за сваки пар стања и улазног знака постоји један и само један прелаз у следеће стање. Детерминистички коначни аутомати препознају само скуп регуларних језика.

ДКА прима ниску знакова са улаза. За сваки улазни знак обавља прелаз у стање одређено функцијом прелаза. Када је прочитана цела ниска, прихватиће је или одбацити у зависности од тога да ли је у том тренутку ДКА у прихватајућем или неприхватајућем стању.


Формална дефиниција[уреди]

ДКА је уређена 5-торка (S, Σ, T, s, A), која се састоји од:

  • коначног скупа стања (S)
  • коначног скупа знакова званог улазна азбука (Σ)
  • функције прелаза (T : S × Σ → S)
  • почетног (иницијалног) стања (s \in S)
  • скупа прихватљивих стања (A подскуп од S)

Нека је M ДКА такав да је = (S, Σ, T, s, A) и X = x0x1 ... xn ниска знакова над азбуком Σ. M прихвата низ знакова X ако постоје стања r0, r1, ..., rn из S таква да важи:

  1. r0 = s
  2. ri+1 = T(ri, xi), за i = 0, ..., n-1
  3. rn \in A.

Као што је показано у првом услову, почетно стање аутомата је s. У другом услову се каже да ће за сваки знак улазног низа X аутомат прећи у следеће стање које је једнозначно одређено функцијом T. Трећи услов каже да ће аутомат прихватити низ X ако читањем последњег знака низа X аутомат прелази у неко од завршних стања. У супротном, каже се да ће аутомат одбити ову реч. Скуп речи које овај ДКА прихвата формира језик за који кажемо да је језик који препознаје овај ДКА.

ДКА без листе прихватајућих (завршних) стања и без почетног стања познат је као полуаутомат.


Пример[уреди]

Следећи пример је пример ДКА M са бинарном азбуком, који препознаје ниске нула и јединица у којима се 0 појављује паран број пута.

M = (S, Σ, T, s, A) где је:

0
1
S1 S2 S1
S2 S1 S2

Ако је аутомат у стању S1 то значи да је до сада прочитао са улаза паран број нула, а ако је у стању S2 значи да је прочитао непаран број нула. Кад год се на улазу појави 1 стање аутомата остаје непромењено. Када се прочита цела ниска са улаза стање у коме је у том тренутку аутомат ће нам показати да ли је та ниска прихваћена или не. Ако ниска садржи паран број нула онда ће аутомат M по завршетку рада бити у прихватајућем стању S1. Дакле, улаз ће бити прихваћен.

Језик аутомата M је регуларни језик који је описан следећим регуларним изразом: (1*(0(1)*0)*)*

Предности и недостаци[уреди]

ДКА су један од најпрактичнијих модела израчунавања, с обзиром на то да је за израчунавање потребно линеарно време, константан меморијски простор и постоји онлајн алгоритам који их симулира. За два дата ДКА постоје ефикасани алгоритми којима се проналази ДКА који препознаје њихову:

  • унију,
  • пресек,
  • резлику.

Такође постоје и ефикасни алгоритми за проналажење:

  • да ли ДКА пепознаје било коју ниску,
  • да ли препознаје све ниске,
  • да ли два ДКА препознају исти језик,
  • за конкретан језик ДКА са минималним бројем стања који га препознаје.

ДКА су по моћи израчунавања еквивалентни недетерминистичким коначним аутоматима.

Са друге стране, коначни аутомати су ограничене моћи у погледу језика који могу препознати. Многи једноставни језици, укључујући било који проблем који захтева већи меморијски простор од константног, не могу бити препознати помоћу ДКА. Класични пример језика кога не препознаје ДКА је језик заграда, језик који се састоји од правилно упарених отворених и затворених заграда, као што је (()(())). Општије, било који језик који се састоји од ниски облика anbn – коначан број а-ова за којим следи исти тај број b-ова, не може бити препознат помоћу ДКА. Овде је реч о рекурзији чија дубина није ограничена. За сваки следећи ниво рекурзије би било потребно ново стање.


Такође видети[уреди]

Литература[уреди]

  • Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Поглавље 1.1: Finite Automata, pp.31-47. Потпоглавље "Decidable Problems Concerning Regular Languages" poglavlja 4.1: Decidable Languages, pp.152-155.4.4 DFA can accept only regular language
Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.