|
Општо земено, автоматот не мора стриктно да го прифаќа или отвфрла влезниот стринг, тој може да го прифати со одредена [[веројатност]] помеѓу нула и еден. Повторно ова е илсутрирано со квантен конечен автомат, која прифаќа влезни стрингови со одредена веројатност. Оваа идеја повторно е делл од една поопшта идеја, идејата за [[геометриски автомат]] или [[метрички автомат]], каде што множеството на состојби се софпаѓа со одреден [[метрички простор]], а јазикот е прифатен од автоматот ако растојанието помеѓу почетната точка и множеството на прифатени состојби е доволно мало во однос на метриката.
SU idioma es muy larrrrgoooo y no lo entiendo lol les estoy dañando su tarea lol LOS ESTOY TROLEAMDO XDDD
== Речник ==
* q<sub>0</sub> е ''ѕвезда состојба'', тоа е состојбата во која автоматот ''се наоѓа'' кога сѐ уште не почнало процесирање на влезот (Очигледно, q<sub>0</sub>∈ Q).
* F е мноѓество на Q (т.е. F⊆Q), наречено '''прифатени состојби'''.
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''.
Given pair of letters <math>a,b\in \Sigma</math>, one may define a new function <math>\widehat\delta</math>, by insisting that <math>\widehat\delta_{ab}=\delta_a \circ \delta_b</math>, where <math>\circ</math> denotes function composition. Clearly, this can process can be recursively continued, and so one has a recursive definition of a function <math>\widehat\delta_w</math> that is defined for all words <math>w\in\Sigma^*</math>, so that one has a map
:<math>\widehat\delta:Q \times \Sigma^{\star} \rightarrow Q.</math>
The construction can also be reversed: given a <math>\widehat\delta</math>, one can reconstruct a <math>\delta</math>, and so the two descriptions are equivalent.
The triple <math>\langle Q, \Sigma, \delta \rangle</math> 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 <math>L</math> accepted by a deterministic finite automaton <math>\langle Q, \Sigma, \delta, q_0, F\rangle</math> is:
:<math>L= \{ w \in \Sigma^{\star}\,|\;\widehat\delta(q_0,w)\in F\}</math>
That is, the language accepted by an automaton is the set of all words ''w'', over the alphabet <math>\Sigma</math>, that, when given as input to the automaton, will will result in its ending in some state from <math>F</math>. Languages that are accepted by automata are called [[recognizable language]]s.
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 language]]s. 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 <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)]]: Од секоја состојба на автоматите од овој тип има транзиција за секој симбол од азбуката.
[[Податотека:Afd_exemple.png|mini|200px|center|frame|DFA]]
; [[nondeterministic finite state machine|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 ''q''<sub>0</sub> 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.
[[Податотека:Afn_exemple.png|mini|200px|center|frame|NFA, equivalent to the DFA from the previous exemple]]
; [[nondeterministic finite state machine|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 <math>\epsilon</math>, then the NFA can ''be'' in any of the states reached by the <math>\epsilon</math>-transitions, directly or through other states with <math>\epsilon</math>-transitions. The set of states that can be reached by this method from a state q, is called the <math>\epsilon</math>-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 автомат|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.
; [[Тјурингова машина|Тјурингови машини]] : 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 language]]s and recognize the [[recursively enumerable language]]s.
== Надворешни врски ==
* [[John E. Hopcroft]], Rajeev Motwani, [[Jeffrey D. Ullman]] - ''Introduction to Automata Theory, Languages, and Computation (2nd Edition)''
* {{цитирана книга|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = 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.
{{формални јазици и граматики}}
{{Нормативна контрола}}
[[Категорија:Теорија на автоматите| ]]
[[it:Automa (informatica)]]
[[simple:Automaton]]
| 