Back

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




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

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

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

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

                                     

1. Формална дефиниција

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

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

Нека је M ДКА такав да је = S, Σ, T, s, A и X = x 0 x 1. x n ниска знакова над азбуком Σ. M прихвата низ знакова X ако постоје стања r 0, r 1., r n из S таква да важи:

  • r i+1 = T r i, x i, за i = 0., n-1
  • r 0 = s
  • r n ∈ {\displaystyle \in } A.

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

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

                                     

2. Пример

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

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

  • s = S 1,
  • A = { S 1 }
  • S = { S 1, S 2 },
  • T је дефинисана преко дијаграма прелаза стања
  • Σ = {0, 1},

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

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

                                     

3. Предности и недостаци

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

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

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

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

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

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



                                     
  • Introduction to the Theory of Computation, PWS Publishing Co. Kozen, D.C. 1997 Automata and Computability, Springer. Meyer, A.R., Ritchie, D.M. 1967 The complexity
  • Индексиран језик Hopcroft, John Ullman, Jeffrey 1979 Introduction to automata theory, languages, and computation. Addison - Wesley. стр. 390 - ISBN 978 - 0 - 201 - 02988 - 8
  • Complexity Zoo Sipser, M. 1996 Introduction to the Theory of Computation, PWS Publishing Co. Kozen, D.C. 1997 Automata and Computability, Springer.
  • сложености. Она садржи све проблеме одлучивања који могу да се реше помоћу детерминистичке Тјурингове машине коришћењем полиномне количине времена рачунарске
  • су још увек довољно уређене да могу да их парсирају линеарно ограничени аутомати Појам контекстно - сензитивне граматике је увео Ноам Чомски током педесетих
  • Алфред Ахо они су описани индексираним граматикама а могу да их препознају аутомати са угњежденим стеком.. Индексирани језици представљају прави подскуп скупа
  • КС - језика: Језик је контекстно слободан ако и само ако постоји потисни аутомат који га прихвата. Унија, производ конкатенација два КС - језика је КС - језик
  • Класа сложености P је скуп свих проблема одлуке који могу бити решени детерминистичком Тјуринговим машином у полиномном времену. Ова класа одговара интуитивној

Users also searched:

...