Теорија на автоматите: Разлика помеѓу преработките

Во [[теорија на информатиката|теоријата на информатиката]], '''теоријата на автоматите''' ги проучува [[апстрактна машина|апстрактните машини]] и проблемите кои тие можат да ги решат. Теоријата на автомати е тесноповрзана со [[теорија на формални јазици|теоријата на формални јазици]] поради тоа што [[автомат]]ите често пати се класифицирани според класата на [[формален јазик|формални јазици]] кои тие можат да ги препознаат.

 

; [[pushdown автомат|Pushdown автомат (PDA)]] : Овие машини се идентични со DFA (или NFA), со таа разлика што тие имаат и [[компјутерска меморија|меморија]] во форма на [[стек (податочна структура)|стек]]. Преодната функција <math>\delta</math> сега исто така зависи и од симболите на врвот од стекот, и ќе специфицира како стекот ќе биде променет при секоја транзиција. Не детерминистичките pushdawn автомати прифаќаат [[контексно слободен јазик|контексно слободни јазици]].

; [[linear bounded automata|Linear Bounded Automata (LBA)]]: An LBA is a limited Turing machine; instead of an infinite tape, the tape has an amount of space proportional to the size of the input string. LBAs accept the [[context-sensitive language]]s.

 

== Надворешни врски ==

== Наводи ==

* [[John E. Hopcroft]], Rajeev Motwani, [[Jeffrey D. Ullman]] - ''Introduction to Automata Theory, Languages, and Computation (2nd Edition)''

 

 

 

[[de:Automatentheorie]]