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

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

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

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

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

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


SU idioma es muy larrrrgoooo y no lo entiendo lol les estoy dañando su tarea lol LOS ESTOY TROLEAMDO XDDD

Речник[уреди]

Автоматот се заснива на овие основни коцепти: симболи, зборови, азбуки и стрингови. 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.
(За недетерминистички автомати, празниот стринг е допуштен влез).
  • q0 е ѕвезда состојба, тоа е состојбата во која автоматот се наоѓа кога сѐ уште не почнало процесирање на влезот (Очигледно, q0∈ Q).
  • F е мноѓество на Q (т.е. F⊆Q), наречено прифатени состојби.

Given an input letter a\in\Sigma, one may write the transition function as \delta_a:Q\rightarrow Q, usig the simple trick of currying, that is, writing \delta(q,a)=\delta_a(q) for all q\in Q. This way, the transition function can be seen in simpler terms: its just something that "acts" on a state in Q, yeilding another state. One may then consider the result of function composition repeatedly applied to the various functions \delta_a, \delta_b, and so on. Repeated function composition forms a monoid. For the transition functions, this monoid is known as the transition monoid, or sometimes the transformation semigroup.

Given pair of letters a,b\in \Sigma, one may define a new function \widehat\delta, by insisting that \widehat\delta_{ab}=\delta_a \circ \delta_b, where \circ denotes function composition. Clearly, this can process can be recursively continued, and so one has a recursive definition of a function \widehat\delta_w that is defined for all words w\in\Sigma^*, so that one has a map

\widehat\delta:Q \times \Sigma^{\star} \rightarrow Q.

The construction can also be reversed: given a \widehat\delta, one can reconstruct a \delta, and so the two descriptions are equivalent.

The triple \langle Q, \Sigma, \delta \rangle is known as a semiautomaton. Semiautomatons underlay automatons, in that they are just automatons, where one has ignored the starting state and the set of accept states. The additional notions of a start state and an accept state allow automatons to do something th semiautomatons cannot: they can recognize a formal language. The language L accepted by a deterministic finite automaton \langle Q, \Sigma, \delta, q_0, F\rangle is:

L= \{ w \in \Sigma^{\star}\,|\;\widehat\delta(q_0,w)\in F\}

That is, the language accepted by an automaton is the set of all words w, over the alphabet \Sigma, that, when given as input to the automaton, will will result in its ending in some state from F. Languages that are accepted by automata are called recognizable languages.

When the set of states Q is finite, then the automaton is known as a finite state automaton, and the set of all recognizable languages are the regular languages. In fact, there is a strong equivalence: for every regular langage, there is a finite state automaton, and vice versa.

As noted above, the set Q need not be finite or countable; it may be taken to be a general topological space, in which case one obtans topological automata. Another possible generalization is the metric automata or geometric automata. In this case, the acceptance of a langage is altered: instead of a set inclusion of the final state in \widehat\delta(q_0,w)\in F, the acceptance criteria is replaced by a probability, given in terms of the metric distance between the final state \widehat\delta(q_0,w) and the set F. Certain types of probablistic automata are metric automata, with the metric being a measure on a probability space.

Класи на конечни автомати[уреди]

Еве три вида на конечни автомати

Детерминистичка конечна машина (англиски Deterministic finite automata (DFA)]]
Од секоја состојба на автоматите од овој тип има транзиција за секој симбол од азбуката.
DFA
Nondeterministic finite automata (NFA) 
States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from q0 to a state in F labeled with the input word. If a transition is undefined, so that the automaton does not know how to keep on reading the input, the word is rejected.
NFA, equivalent to the DFA from the previous exemple
Nondeterministic finite automata, with ε transitions (FND-ε or ε-NFA) 
Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with \epsilon, then the NFA can be in any of the states reached by the \epsilon-transitions, directly or through other states with \epsilon-transitions. The set of states that can be reached by this method from a state q, is called the \epsilon-closure of q.

It can be shown, though, that all these automata can accept the same languages. You can always construct some DFA M' that accepts the same language as a given NFA M.

Проширување на конечните автомати[уреди]

Фамилијата на јазици прифатена од страна на погоре опишаните автомати е наречеан фамилија на регуларни јазици. Помоќните автомати можат да прифатат покомлексни јазици. Таквии автомати се:

Pushdown автомат (PDA) 
Овие машини се идентични со DFA (или NFA), со таа разлика што тие имаат и меморија во форма на стек. Преодната функција \delta сега исто така зависи и од симболите на врвот од стекот, и ќе специфицира како стекот ќе биде променет при секоја транзиција. Не детерминистичките pushdawn автомати прифаќаат контексно слободни јазици.
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 languages.
Тјурингови машини 
These are the most powerful computational machines. They possess an infinite memory in the form of a tape, and a head which can read and change the tape, and move in either direction along the tape. Turing machines are equivalent to algorithms, and are the theoretical basis for modern computers. Turing machines decide recursive languages and recognize the recursively enumerable languages.

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

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

  • 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 Регуларни Регуларни Конечен
Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа.