Теорија на автоматите

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

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

Основни поими[уреди | уреди извор]

Автомат е математички модел на конечна машина (англиски: finite state machine - FSM). Конечна машина е машина која за даден почетен стринг преминува низ серија од состојби во зависност од преодните функции (кои можат да бидат претставени табеларно). Во т.н. Милеви машини (варијанта на конечна машина), овие преодни функции му кажуваат на автоматот на која состојба да оди во зависност од тековната состојба и тековниот симбол.

Влезот се чита симбол по симбол, сè додека не се прочита целосно (може да се замисли како лента на кои се испишани некои зборови, кои се читаа со помош на главата за читање од автоматот, главата се придвижува нанапред читајќи еден симбол при секое придвижување). Во оној момент кога влезниот стринг ќе биде прочитан целосно велиме дека автоматот треба да застане.

Во зависност од состојбата во која автоматот застанал, се вели дека автоматот го прифатил или отфрлил влезниот стринг. Ако автоматот застанал во состојба на прифаќање, тогаш автоматот го прифаќа зборот. Ако, од друга страна, главата застане во состојба на отфрлање, велиме дека зборот е отфрлен. Множеството на сите прифатени зборови од автоматот се нарекува јазик прифатен од автоматот.

Напомена. Автоматот не мора да има конечен број на состојби, или дури и преброив број на состојби. Така на пример, квантниот конечен автомат има непреброиво бесконечно состојби, како множество на сите можни состојби се јавува множеството од сите точки во комплексен проективен простор. Така, квантниот конечен автомат, исто како и конечните машини, се специјални случаи на една генерална идеја, идеја на тополошки автомати, каде состојбата ма состојби е тополошки простор а преодните функции се земаат од множеството на сите можни функции во тој простор. Тополошките автомати често пати се нарекуваат М-автомати, and are simply the augmentation of a semiautomaton with a set of accept states, where set intersection determines whether the initial state is accepted or rejected.

Општо земено, автоматот не мора стриктно да го прифаќа или отвфрла влезниот стринг, тој може да го прифати со одредена веројатност помеѓу нула и еден. Повторно ова е илсутрирано со квантен конечен автомат, која прифаќа влезни стрингови со одредена веројатност. Оваа идеја повторно е делл од една поопшта идеја, идејата за геометриски автомат или метрички автомат, каде што множеството на состојби се софпаѓа со одреден метрички простор, а јазикот е прифатен од автоматот ако растојанието помеѓу почетната точка и множеството на прифатени состојби е доволно мало во однос на метриката.

Речник[уреди | уреди извор]

Автоматот се заснива на овие основни коцепти: симболи, зборови, азбуки и стрингови. These are

Симбол 
An arbitrary datum which has some meaning to or effect on the machine. Симболите понекогаш се нарекуваат и букви.
Збор 
Конечен стринг формиран со конкатенација на одреден број на симболи.
Азбука 
Конечно множество на симболи. Азбуката често се означува со , што значи множество на букви во азбуката.
Јазик 
Множество на зборови, формирани од симболи од дадена азбука. Може но не мора да е бесконечно.
Kleene closure 
Јазикот може да се замисли како подмножество од сите можни зборови. Множеството од сите можни зборови, може пак да се замисли како множество на сите можни конкатенации на стрингови. Формално, ова множество на сите можни стрингови е наречено слободен моноид. Се означува со , а ѕвездичката над симболот е наречена Клине ѕвезда

Формален опис[уреди | уреди извор]

Автоматот е претставен од 5-tuple , каде:

  • Q е множество на состојби.
  • ∑ е конечно множество од симболи, кое ние ќе го наречеме азбука на јазикот кој автоматот го прифаќа.
  • δ е преодна функција, која е
(За недетерминистички автомати, празниот стринг е допуштен влез).
  • q0 е ѕвезда состојба, тоа е состојбата во која автоматот се наоѓа кога сѐ уште не почнало процесирање на влезот (Очигледно, q0∈ Q).
  • F е мноѓество на Q (т.е. F⊆Q), наречено прифатени состојби.

Надворешни врски[уреди | уреди извор]

Наводи[уреди | уреди извор]

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Part One: Automata and Languages, chapters 1–2, стр. 29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, стр. 172–183.
Теорија на автоматите: формални јазици и формални граматики
Хиерархија
на Чомски
Граматики
Јазици
Автомати
Тип-0 Неограничени Рекурзивно преброиви Тјурингова машина
(нема вообичаено име) Рекурзивни Одлучувач
Тип-1 Контексно-осетливи Контексно-осетливи Линеарни
Индексирани Индексирани Вгнезден склад
Тип-2 Контексно-слободни Контексно-слободни Недетерминистички потисни
Детерминистички конт.-слоб. Детерминистички конт.-слоб. Детерминистички потисни
Тип-3 Регуларни Регуларни Конечен
Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа.