Konečné automaty deterministické a nedeterministické

Deterministický konečný automat

Definice

• Deterministický konečný automat $M$ je uspořádaná pětice $M=(Q,\Sigma ,\delta ,q_0,F)$, kde:
  • $Q$ je neprázdná konečná množina stavů
  • $\Sigma$ je konečná množina vstupních symbolů, nazývaná také vstupní abeceda
  • $\delta$ je přechodová funkce ve stavu $\delta :Q\times \Sigma \to Q$
  • $q_0\in Q$ je počáteční stav
  • $F\subseteq Q$ je množina koncových/akceptujících stavů

• Takto definovaný automat je deterministický, protože se v každém kroku výpočtu nachází právě v jednom stavu

• Abychom mohli definovat jazyk přijímaný daným DFA M, zavedeme rozšířenou přechodovou funkci $\hat{\delta }:Q\times E^{\ast }\to Q$, definovanou induktivně vzhledem k délce slova ze ${\Sigma }^{\ast }$:

  • $\hat{\delta }(q,ϵ)=q$, pro každý stav $q\in Q$
  • $\hat{\delta }(q,wa)=\delta (\hat{\delta }(q,w)a)$

• Jazyk přijímaný DFA M, označovaný $L(M)$, je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových stavů: $L(M)=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }(q_0,w)\in F\}$

• Jazyk, který je rozpoznatelný DFA, nazveme regulární

Příklad DFA M a jeho další možné reprezentace

• Nechť $\mathcal{M}=(\{q_0,q_1,q_2\},\{a,b\},\delta ,q_0,\{q_2\})$ je $FA$, kde $\delta (q_0,a)=q_1\delta (q_0,b)=q_2$ $\delta (q_1,a)=q_2\delta (q_1,b)=q_0$ $\delta (q_2,a)=q_0\delta (q_2,b)=q_1$ Pak $L(\mathcal{M})=\{w\in \{a,b{\}}^{\ast }\mid ({\#}_a(w)-{\#}_b(w))\text{ mod }3=2\}$.
• Automat M je možné reprezentovat pomocí tabulky přechodové funkce:
  • Stavy automatu jsou vypsány v záhlaví řádků, vstupní symboly v záhlaví sloupců, přechodová funkce je určena obsahem vnitřních polí tabulky, počáteční stav je označen znakem $\to$ a koncové stavy znakem $\leftarrow$.
• Ještě přehlednější(a proto nejčastěji používaná) je reprezentace pomocí přechodového grafu, který pro automat $M$ vypadá takto:
  • Stavy odpovídají uzlům, přechodová funkce je znázorněna ohodnocenými hranami, vstupní abeceda je tvořena symboly, kterými jsou hrany ohodnoceny, počáteční stav je označen šipkou a koncové stavy jsou dvojitě zakroužkovány
• Nakonec ještě zmiňme reprezentaci výpočetním stromem. Kočen stromu odpovídá počátečnímu stavu. Z každého uzlu, který není listem vychází právě tolik hran ohodnocených symboly vstupní abecedy, kolik má odpovídající stav následníků (je-li tedy totální, pak právě tolik hran, kolik symbolů má vstupní abeceda). Jestliže nějaký stav odpovídá více uzlům, pak hrany vycházejí jen z jednoho z těchto uzlů.
• Výpočetním stromem lze reprezentovat jen ty automaty, kde každý stav je tzv. dosažitelný z počátečního stavu
• Výpočetní strom pro daný automat není určen jednoznačně - může se lišit dle toho, zda jej konstruujeme způsobem, který odpovídá například procházení do hloubky, nebo do šířky, či dalšími možnostmi.

Konstrukce konečných automatů

• Základním trikem, který dokáže zjednodušit návrh konečného automatu, je zavedení jisté pomocní struktury na stavech. Informaci, která je spojená s daným stavem, je účelné zachytit v jeho označení.

Příklad

• Máme za úkol sestrojit automat rozpoznávající jazyk $L=\{w\in \{a,b{\}}^{\ast }\mid w\text{ obsahuje podslovo abaa}\}$

Konečný nedeterministický automat

• Jediný rozdíl je v tom, že nedeterministický automat nemusí mít pro daný stav a vstupní symbol určen následující stav jednoznačně. Slovo $w$ bude akceptování, pokud alespoň jeden z možných výpočtů nad slovem $w$ skončí v koncovém stavu.

Definice

• Nedeterministický konečný automat $M$ je uspořádaná pětice $M=(Q,\Sigma ,\delta ,q_0,F)$
  • $Q$ je neprázdná konečná množina stavů
  • $\Sigma$ je konečná množina vstupních symbolů, nazývaná také vstupní abeceda
  • $\delta$ je přechodová funkce ve tvaru $\delta :Q\times \Sigma \to 2^Q$
  • $q_0\in Q$ je počáteční stav
  • $F\subseteq Q$ je množina koncových/akceptujících stavů

• Abychom mohli definovat jazyk přijímaný daným NFA M, zavedeme rozšířenou přechodovou funkci $\hat{\delta }:Q\times {\Sigma }^{\ast }\to 2^Q$, definovanou induktivně vzhledem k délce slova ze ${\Sigma }^{\ast }$:
  • $\hat{\delta }(q,ϵ)=\{q\}$, pro každý stav $q\in Q$
  • $\hat{\delta }(q,wa)={\cup }_{p\in \hat{\delta }(q,w)}\delta (p,a)$
• Jazyk přijímaný NFA M je definován takto: $L(M)=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }(q_0,w)\cap F\ne 0\}$
• Nedeterminismus je velmi silná popisný aparát, který často umožňuje zachytit strukturu jazyka elegantním a přirozeným způsobem.

Příklad

• $L=\{w\in \{a,b{\}}^{\ast }\mid w\text{ obsahuje podslovo abba nebo bab}\}$
• Navrhnout DFA, který rozpoznává $L$, není zcela triviální.
• Naopak nederministický automat lze zkonstruovat snadno

• Nedeterminismus lze dobře využít jako popisný prostředek, nemá však vliv na výpočetní sílu konečných automatů. Ke každému nedeterministickému konečnému automatu totiž ve skutečnosti existuje ekvivalentní deterministický automat, který lze dokonce algoritmicky zkonstruovat.

Navigace

Předchozí: Regulární jazyky (definice, uzávěrové vlastnosti) Následující: Regulární výrazy, automaty s e-přechody Celý okruh: 1. Teoretické základy informatiky