Verzia z 21:46, 15. január 2009 upraviť Bubamara (diskusia \| príspevky) 53 099 editací d Verzia používateľa 213.151.217.140 (diskusia) bola vrátená, bola obnovená verzia od Izmaelt ← Predchádzajúca úprava		Verzia z 13:15, 20. december 2009 upraviť vrátiť Pokus9999 (diskusia \| príspevky) 3 929 editací rozsirenie Ďalšia úprava →
Riadok 1: '''Konečný automat''' je [[automat (teória automatov)\|automat]] (výpočtový model), ktorého [[množina]] stavov je konečná. Konečné automaty sú jedným zo základných prostriedkov na popis [[regulárny jazyk\|regulárnych jazykov]]. Konečné automaty tiež majú aplikácie napríklad pri [[vyhľadávanie v texte\|vyhľadávaní v texte]] alebo matematickom popise [[pamäť (počítač)\|pamäťových obvodov]]. ~~'''Konečný automat''' je [[automat]], ktorého [[množina]] stavov, vstupov a výstupov je konečná.~~ Existuje viacero druhov konečných automatov. Základné dva modely sú [[deterministický konečný automat]] (DKA) a [[nedeterministický konečný automat]] (NKA). Napriek tomu, že NKA dovoľujú podstatne viac, popisná sila oboch modelov je rovnaká. Popísaných tiež bolo množstvo zovšeobecnení týchto základných modelov. == Deterministický konečný automat == === Definícia DKA === '''[[Deterministický konečný automat]]''' je pätica <math>(\Sigma, K, q_0, \delta, F)</math>, kde: <math>\Sigma</math> je vstupná [[abeceda (teória automatov)\|abeceda]] (neprázdna konečná množina symbolov). <math>K</math> je konečná množina stavov. <math>q_0</math> je počiatočný stav, pričom platí <math>q_0 \in K</math>. <math>\delta</math> je prechodová funkcia: <math>\delta: K \times \Sigma \rightarrow K</math>, čiže funkcia, ktorá na základe stavu a symbolu zo vstupnej abecedy vráti nový stav <math>F</math> je množina akceptačných stavov, je to ľubovoľná (môže byť aj prázdna) podmnožina <math>K</math>. Hovoríme, že DKA akceptuje slovo <math>w</math>, ak výpočet na tomto slove skončí v niektorom z akceptačných stavov. === Konfigurácia DKA === Konfigurácia deterministického konečného automatu je dvojica <math>(q,w) \in K \times \Sigma^{\ast}</math>, kde ''q'' je aktuálny stav automatu a ''w'' je dosiaľ neprečítaná časť vstupného slova. === Krok výpočtu DKA === Krok výpočtu deterministického konečného automatu je relácia <math>\vdash_A</math> na konfiguráciach DKA definovaná nasledovne: <math>(q,av) \vdash_A (p,v) \iff p = \delta(q,a) </math>. Pod výpočtom na deterministickom konečnom automate rozumieme ľubovoľnú postupnosť na seba nadväzujúcich výpočtových krokov. === Jazyk akceptovaný pomocou DKA === Jazyk akceptovaný deterministickým konečným automatom ''A'' definujeme nasledovne: :<math>L(A) = \{w\ \|\ \exists p \in F: (q_0,w) \vdash_{A}^{\ast} (p,\varepsilon)\}. </math> Je to teda množina všetkých slov, na ktorých existuje v automate ''A'' výpočet končiaci v akceptačnom stave (takému výpočtu sa tiež hovorí akceptačný výpočet). == Nedeterministický konečný automat == === Definícia NKA === '''[[Nedeterministický konečný automat]]''' je pätica <math>(\Sigma, K, q_0, \delta, F)</math>, kde: <math>\Sigma</math> je vstupná [[abeceda (teória automatov)\|abeceda]] (neprázdna konečná množina symbolov). <math>K</math> je konečná množina stavov. <math>q_0</math> je počiatočný stav, pričom platí <math>q_0 \in K</math>. <math>\delta</math> je prechodová funkcia: <math>\delta: K \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^K</math>, čiže funkcia, ktorá na základe stavu a symbolu zo vstupnej abecedy množinu nových stavov <math>F</math> je množina akceptačných stavov, je to ľubovoľná (môže byť aj prázdna) podmnožina <math>K</math>. Hovoríme, že DKA akceptuje slovo <math>w</math>, ak výpočet na tomto slove skončí v niektorom z akceptačných stavov. Existujú teda dva podstatné rozdiely medzi NKA a DKA: * NKA povoľujú prechody na <math>\varepsilon</math> * Nový stav nie je pre každý prechod určený jednoznačne. Prechodová funkcia vracia celú množinu stavov (pri výpočte sa môže postupovať do ľubovoľného z nich), ktorá môže byť dokonca prázdna. === Konfigurácia NKA === Konfigurácia nedeterministického konečného automatu sa definuje analogicky, ako pri deterministických konečných automatoch. Je to dvojica <math>(q,w) \in K \times \Sigma^{\ast}</math>, kde ''q'' je aktuálny stav automatu a ''w'' je dosiaľ neprečítaná časť vstupného slova. === Krok výpočtu NKA === Krok výpočtu je relácia \vdash_{A} na konfiguráciach NKA ''A'' definovaná nasledovne: :<math> (q,aw) \vdash_A (p,w) \iff p \in \delta(p,a) </math>. === Jazyk akceptovaný pomocou NKA === Jazyk akceptovaný nedeterministickým konečným automatom ''A'' je množina :<math>L(A) = \{w\ \|\ \exists p \in F: (q_0,w) \vdash_{A}^{\ast} (p,\varepsilon)\}. </math> == Ekvivalencia DKA a NKA == V skutočnosti, napriek rozdielnej definícii oboch výpočtových modelov, je ich výpočtová sila rovnaká. Je dokázané, že ku každému nedeterministickému automatu ''A'' existuje deterministický konečný automat ''B'' taký, že ''L(B) = L(A)''. Opačná inklúzia je zrejmá z faktu, že deterministický automat je špeciálny prípad nedeterministického. == Externé odkazy == * {{filit\|fva/automat_konecny.html}} [[Kategória:~~Psychológia~~Formálne jazyky a automaty]] [[bg:Краен автомат]] [[ca:Autòmat finit]] [[cs:Konečný automat]] [[de:Endlicher Automat]] [[en:Finite-state machine]] [[es:Autómata finito]] [[fa:ماشین‌های حالات متناهی]] [[fr:Automate fini]] [[gl:Autómata finito]] [[hr:Konačni automat]] [[it:Automa a stati finiti]] [[he:אוטומט סופי]] [[lv:Galīgs automāts]] [[lt:Baigtinis automatas]] [[mk:Конечен автомат]] [[nl:Eindigetoestandsautomaat]] [[ja:有限オートマトン]] [[pl:Automat skończony]] [[pt:Máquina de estados finitos]] [[ro:Automat finit]] [[ru:Конечный автомат]] [[sr:Коначан аутомат]] [[sh:Konačni automat]] [[fi:Äärellinen automaatti]] [[sv:Ändlig automat]] [[th:เครื่องสถานะจำกัด]] [[tr:Sonlu Durum Makinası]] [[uk:Автомат скінченний]] [[zh:有限状态自动机]]

Konečný automat: Rozdiel medzi revíziami