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

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

Основни поими

Автомат е математички модел на конечна машина (англиски: 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. Симболите понекогаш се нарекуваат и букви.

Збор

Конечен стринг формиран со конкатенација на одреден број на симболи.

Азбука

Конечно множество на симболи. Азбуката често се означува со $\Sigma$, што значи множество на букви во азбуката.

Јазик

Множество на зборови, формирани од симболи од дадена азбука. Може но не мора да е бесконечно.

Kleene closure

Јазикот може да се замисли како подмножество од сите можни зборови. Множеството од сите можни зборови, може пак да се замисли како множество на сите можни конкатенации на стрингови. Формално, ова множество на сите можни стрингови е наречено слободен моноид. Се означува со $\Sigma ^{*}$, а ѕвездичката над симболот е наречена Клине ѕвезда

Формален опис

Автоматот е претставен од 5-tuple $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$, каде:

• Q е множество на состојби.
• ∑ е конечно множество од симболи, кое ние ќе го наречеме азбука на јазикот кој автоматот го прифаќа.
• δ е преодна функција, која е

$\delta :Q\times \Sigma \rightarrow Q.$

(За недетерминистички автомати, празниот стринг е допуштен влез).

• q₀ е ѕвезда состојба, тоа е состојбата во која автоматот се наоѓа кога сѐ уште не почнала обработка на влезот (Очигледно, q₀∈ Q).
• F е мноѓество на Q (т.е. F⊆Q), наречено прифатени состојби.

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

• Visual Automata Simulator (англиски) Архивирано на 10 октомври 2007 г.
• JFLAP (англиски)
• Proyecto SEPa (шпански) Архивирано на 18 ноември 2019 г.
• Exorciser (германски)

Наводи

• 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.