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

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

 

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

 

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

 

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

; [[Симбол]] : An arbitrary datum which has some meaning to or effect on the machine. Симболите понекогаш се нарекуваат и [[букви]].

; [[Kleene closure]] : Јазикот може да се замисли како подмножество од сите можни зборови. Множеството од сите можни зборови, може пак да се замисли како множество на сите можни конкатенации на стрингови. Формално, ова множество на сите можни стрингови е наречено [[слободен моноид]]. Се означува со <math>\Sigma^*</math>, а ѕвездичката над симболот е наречена [[Клине ѕвезда]]

 

'''Автоматот''' е претставен од [[N-tuple|5-tuple]] <math>\langle Q, \Sigma, \delta, q_0, F\rangle</math>, каде:

::<math>\delta:Q \times \Sigma \rightarrow Q.</math>

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

 

Given an input letter <math>a\in\Sigma</math>, one may write the transition function as <math>\delta_a:Q\rightarrow Q</math>, usig the simple trick of [[currying]], that is, writing <math>\delta(q,a)=\delta_a(q)</math> for all <math>q\in Q</math>. 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 <math>\delta_a</math>, <math>\delta_b</math>, 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''.

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 <math>\widehat\delta(q_0,w)\in F</math>, the acceptance criteria is replaced by a probability, given in terms of the [[metric distance]] between the final state <math>\widehat\delta(q_0,w)</math> and the set <math>F</math>. Certain types of probablistic automata are metric automata, with the metric being a [[measure (mathematics)|measure]] on a [[probability space]].

 

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

;[[детерминистичка конечна машина|Детерминистичка конечна машина]] ([[англиски јазик|англиски]] Deterministic finite automata (DFA)]]: Од секоја состојба на автоматите од овој тип има транзиција за секој симбол од азбуката.

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

 

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

 

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

 

{{Formal languages and grammars}}

[[es:Teoría de autómatas]]

[[fr:Théorie des automates]]

[[he:תורת האוטומטים]]

[[hu:Absztrakt automata]]

[[ja:オートマトン]]

[[pt:Teoria de Autômatos]]

[[sk:Teória automatov]]

[[th:ทฤษฎีออโตมาตา]]