AP9, IN9 Konečné automaty

Zadání

definice, konstrukce konečného automatu, minimalizace konečného automatu, převod nedeterministického konečného automatu na deterministický automat

Definice konečného automatu

Definice 2.1. 1)

Konečný automat M je pětice (Q, Sigma, delta, q0, F), kde
  • Q je neprázdná konečná množina stavů,
  • Sigma je konečná množina vstupních symbolů (vstupní abeceda),
  • delta: Q x Sigma → Q je parciální přechodová funkce (v případě nedeterministického konečného automatu je definována jako totální zobrazení delta: Q x Sigma → 2Q),
  • q0 in Q je počáteční stav,
  • F ⊆ Q je množina koncových stavů

Rozšířená přechodová funkce deterministického konečného automatu:

Abychom mohli definovat jazyk akceptovaný automatem, je třeba zavézt rozšířenou přechodovou funkci

hat{delta}: Q x Sigma* → Q definována induktivně vzhledem k délce slova ze Sigma*:

  • hat{delta}(q, epsilon) = q pro každý stav q in Q
  • hat{delta}(q, wa) =
    • delta(hat{delta}(q, w), a) je-li hat{delta}(q, w) i delta(hat{delta}(q, w), a) definováno
    • ortho jinak

Jazyk akceptovaný konečným automatem 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.
L(M) = {w in Sigma* | hat{delta}(q0,w) in F}

Rozšířená přechodová funkce nedeterministického konečného automatu:

hat{delta}: Q x Sigma* → 2Q, definována induktivně vzhledem k délce slova ze Sigma*:

  • hat{delta}(q, epsilon) = {q}
  • hat{delta}(q, wa) = bigcup{p in hat{delta}(q,w)}{}{delta(p,a)}

Jazyk akceptovaný nedeterministickým konečným automatem 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.
L(M) = {w in Sigma* | hat{delta}(q0,w) inter F != varnothing}

Konstrukce konečného automatu

Mějme například jazyk L = {w in {a, b}* | w obsahuje podslovo abaa}.

  • konstrukce konečného automatu, který rozpoznává daný jazyk, je obecně netriviální úkol. Pro zjednodušení proto volíme označení stavů tak, aby bylo patrné, jaká část podslova abaa již byla automatem přečtena.

Konečný automat akceptující jazyk L je možné reprezentovat:

Uspořádanou pěticí

M = ({lbrace}q_ε, q_a, q_ab, q_aba, q_abaa{rbrace}, {lbrace}a, b{rbrace}, delta, q_ε, {lbrace}q_abaa{rbrace}) kde přechodová funkce delta vypadá následovně:

delta(q_epsilon, a) = q_a delta(q_ab, b) = q_epsilon
delta(q_epsilon, b) = q_epsilon delta(q_aba, a) = q_abaa
delta(q_a, a) = q_a delta(q_aba, b) = q_ab
delta(q_a, b) = q_ab delta(q_abaa, a) = q_abaa
delta(q_ab, a) = q_aba delta(q_abaa, b) = q_abaa

Tabulkou

a b
q_epsilon q_a q_epsilon
q_a q_a q_ab
q_ab q_aba q_epsilon
q_aba q_abaa q_ab
q_abaa q_abaa q_abaa

Přechodovým grafem

Přechodový graf

Výpočetním stromem

  • není určen jednoznačně. Může se lišit podle toho, jakým způsobem jej konstruujeme.
  • Příklad výpočetního stromu pro automat M:

Výpočetní strom

Synchronní paralelní kompozice

Pro dané automaty M1 a M2 umožňuje sestrojit automat rozpoznávající průnik, sjednocení či rozdíl jazyků L(M1) a L(M2).
Nechť M1 = (Q1, Sigma, delta1, q1, F1), M2 = (Q2, Sigma, delta2, q2, F2) a přechodové funkce delta1, delta2 jsou totální.
Definujeme konečný automat M3 = (Q3, Sigma, delta3, q3, F3), kde

  • Q3 = Q1 x Q2 = {(p,q) | p in Q1, q in Q2}
  • F3 = F1 x F2 = {(p,q) | p in F1, q in F2}
  • q3 = (q1, q2)
  • delta3( (p,q),a) = (delta1(p,a),delta2(q,a) )

Potom L(M3) = L(M1) inter L(M2)

Podobně pro sjednocení a rozdíl - zmení sa len množina koncových stavov

  • F3 = (F1 x Q2) union (Q1 x F2) = {(p,q) | p in F1q in F2} pre zjednotenie
  • F3 = F1 - F2 = {(p,q) | p in F1q notin F2} pre rozdiel
Příklad průniku

Synchronní paralelní kompozice

Automat pro komplement

K automatu M = (Q, Sigma, delta, q0, F) s totální přechodovou funkcí sestrojíme automat overline{M} rozpoznávající jazyk co–L(M) jako overline{M} = (Q, Sigma, delta, q0, Q – F).

Poznámka: přechodovou funkci ztotálníme tak, že přidáme nový nekoncový stav („černá díra“), do kterého „nasměrujeme chybějící šipky“.

Minimalizace konečného automatu

Minimální konečný automat = automat s nejmenším počtem stavů, který rozpoznává daný regulární jazyk L.
Existence minimálního konečného automatu souvisí s Myhill–Nerodovou větou (viz otázka AP8,IN8 Regulární jazyky), kterou můžeme přeformulovat takto:

Věta 2.29 Myhill–Nerodova, 2. varianta2)

Počet stavů libovolného minimálního automatu rozpoznávajícího jazyk L je roven indexu prefixové ekvivalence ~L. (Takový konečný automat existuje právě když index ~L je konečný.)

Důsledek M-N věty

Minimální konečný automat akceptující jazyk L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů).

Minimalizace konečného automatu probíhá tak, že nejprve jsou odstraněny nedosažitelné stavy a poté jsou ztotožněny jazykově ekvivalentní stavy.

Odstranění nedosažitelných stavů

Definice - dosažitelné a nedosažitelné stavy

Nechť M = (Q, Sigma, delta, q0, F) je konečný automat. Stav q in Q nazveme dosažitelný, pokud existuje w in Sigma* takové, že hat{delta}(q0, w) = q. Stav je nedosažitelný, pokud není dosažitelný.

Algoritmus pro eliminaci nedosažitelných stavů konečného automatu

Vstup: Konečný automat M = (Q, Sigma, delta, q0, F)
Výstup: Ekvivalentní automat M' bez nedosažitelných stavů.

Algoritmus

i := 0
Si := {q0}
repeat Si+1 := Si union {q | existsp in Si, a in Sigma: delta(p, a) = q}
i := i + 1
until Si = Si–1 Q' := Si M' = (Q', Sigma, delta|Q', q0, F inter Q')

Poznámka: Zápis delta|Q' znamená, že funkce delta je omezena na množinu Q'.
Intuitivně: Množina Si je množina stavů dosažitelná v automatu v maximálně i krocích.

Ztotožnění jazykově ekvivalentních stavů

Nechť M = (Q, Sigma, delta, q0, F) je konečný automat bez nedosažitelných stavů, jehož přechodová funkce je totální.

Definice - jazykově ekvivalentní stavy

Stavy p, q nazveme jazykově ekvivalentní, psáno pq, pokud
pq doubleleftright forallw in Sigma* : (hat{delta}(p, w) in F doubleleftright hat{delta}(q, w) in F).

Definice - Redukt

Reduktem automatu M = (Q, Sigma, delta, q0, F) nazveme konečný automat M/ = (Q/, Sigma, eta, [q0], F/), kde:
  • Stavy jsou třídy rozkladu Q/ (třída obsahující stav q je [q]).
  • Přechodová funkce eta je funkce splňující:

forallp,q in Q, foralla in Sigma: delta(q, a) = p doubleright eta([q], a) = [p].

  • Počáteční stav je třída rozkladu Q/ obsahující stav q0.
  • Koncové stavy jsou právě ty třídy rozkladu Q/, které obsahují alespoň jeden koncový stav.

Věta

Nechť M = (Q, Sigma, delta, q0, F) je konečný automat bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/).

Definice

Pro každé i in bbN0 definujeme binární relaci ≡i na Q předpisem
pi q doubleleftright forallw in Sigma*.|w| <= i : (hat{delta}(p, w) in F doubleleftright hat{delta}(q, w) in F)
  • pi q právě když p a q nelze „rozlišit“ žádným slovem délky <= i
  • pq právě když pi q pro každé i in bbN0. (≡ = bigcap{i=0}{infty}{≡}i)
  1. 0 = {(p, q) | p in F doubleleftright q in F}
  2. i+1 = {(p, q) | pi q wedge foralla in Sigma : delta(p, a) ≡i delta(q, a)}

Algoritmus konstrukce minimálního automatu

Vstup: Konečný automat M = (Q, Sigma, delta, q0, F) bez nedosažitelných stavů s totální přechodovou funkcí
Výstup: Redukt M/.

Algoritmus

i := 0
0 := {(p, q) | p in F doubleleftright q in F}
repeati+1 := {(p, q) | pi q wedge foralla in Sigma : delta(p, a) ≡i delta(q, a)}
i := i + 1
untili = ≡i–1 ≡ = ≡i M/ := (Q/, Sigma, eta, [q0], F/)
Příklad

Konstrukce minimálního automatu

  • První tabulka obsahuje nedostupné stavy (stav 7).
  • Druhá tabulka ukazuje přechodovou funkci po úpravě na totální, přidáním nového stavu N a nasměrováním všech nedefinovaných přechodů do něj.
  • Ostatní čtyři tabulky reprezentují postupnou minimalizaci automatu.

Praktické vysvětlení algoritmu

Na začátku tabulku přechodové funkce rozdělíme do dvou částí(tříd), do druhé části zaznamenáme výstupní stavy, do první části ty ostatní. Obě části označíme římskými číslicemi. Postupně procházíme stavy automatu který chceme minimalizovat, a pro jednotlivé prvky abecedy zjišťujeme, ve které části tabulky se nachází stav do kterého se při přechodu dostaneme. Číslo této části zapíšeme do tabulky k prvku abecedy u zpracovávaného stavu. (tabulka 3)

Tabulku opět rozdělíme, do částí(tříd) které označíme římskými číslicemi, v každé necháme stavy ze kterých se pod všemi prvky abecedy dostaneme do stejných částí tabulky. Aplikujeme předchozí krok.(tabulka 4,5)

Tento postup aplikujeme dokud každá část tabulky neobsahuje jen stavy přecházející do stejných tříd. Ve výsledné tabulce nezapisujeme názvy stavů, ale jen označení tříd s jejich přechody(tabulka 6).

Převod NFA na DFA

Věta

Pro každý NFA M = (Q, Sigma, delta, q0, F) existuje ekvivalentní DFA.

Algoritmus transformace NFA na DFA

Vstup: NFA M = (Q, Sigma, delta, q0, F).
Výstup: Ekvivalentní DFA M' = (Q', Sigma, delta', {q0}, F') bez nedosažitelných stavů a s totální přechodovou funkcí.

Algoritmus

Q' := { {q0} }; delta' := varnothing; F' := varnothing; Done := varnothing;
while (Q'Done) <>varnothing do M := libovolný prvek množiny Q'Done if M inter F <>varnothing then F' := F' union {M} fi foreach a in Sigma do N := bigcup{p in M}{}{delta(p,a)} Q' := Q' union {N}
delta' := delta' union {( (M, a),N)} od Done := Done union {M}
od M' = (Q', Sigma, delta', {q0}, F')

Příklad

Mějme nedeterministický konečný automat :

a b
→ 1 1,2 1,7
2 - 3
3 - 4
4 5 -
← 5 5 5
6 - 5
7 6 -


Převod nedeterministického automatu na deterministický provedeme pomocí algoritmu následovně:

Praktické vysvětlení algoritmu

Začínáme vstupním stavem, který napíšeme do tabulky (1). Zjistíme množinu stavů, do kterých se dostaneme pomocí prvků abecedy. (pro a 1,2, pro b 1,7). Poté vždy vytvoříme (pokud ještě neexistuje) nový stav pojmenovaný jako sjednocení stavů (pro a 12, pro b 17) a zaznamenáme do tabulky. Vezmeme poté následující nezpracovaný stav v nově tvořené tabulce (12) a zjistíme do jaké množiny stavů se lze dostat ze stavů 1 a 2 a provedeme jejich sjednocení (pro a 1,2 , pro b 1,3,7) poté opět zaznamenáme případný nový stav. Od této chvíle pokračujeme obdobně.

Algoritmus končí, ve chvíli kdy není možné nalézt žádný nový stav. Vstupní stavy zůstávají stejné, koncové stavy jsou ty, které obsahují některý z původních koncových stavů.

Takto vytvořený automat nemusí být minimální, ale je bez nedosažitelných stavů, s totální přechodovou funkcí.

a b
→ 1 12 17
12 12 137
17 126 17
137 126 147
126 12 1357
147 1256 17
← 1357 1256 1457
← 1256 125 1357
← 1457 1256 157
← 125 125 1357
← 157 1256 157

Využití

Konečné automaty se používají např. k lexikální analýze.

Literatura

Vypracoval

Lukáš Hala, 173454@mail.muni.cz
Pokud si myslíte, že tady něco chybí, přebývá nebo že je něco blbě, tak to prosím upravte ;-)

FIXME Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.

1)
viz skripta Automaty a formální jazyky I, str. 11
2)
viz skripta Automaty a formální jazyky I, str. 26

Diskuze

, 2008/06/04 18:50

Ahoj, bylo by dobre, dat obrazky sem na wiki, ted se tahaji od tebe z webu, v budoucnu by pak mohli chybet.

, 2008/06/04 20:03

done

, 2008/06/04 23:09

Ok.
A díky za doplnění příkladu a praktických vysvětlení algoritmů ;-)

, 2008/06/10 12:03

Nemyslím, že výpočetní strom je vhodná reprezentace automatu. Spíš reprezentuje výpočet automatu nad daným slovem.

, 2008/06/16 23:32

Podle mě nereprezentuje jenom výpočet nad daným slovem, ale nad jakýmkoliv slovem z jazyka. Například když dojdu po slově abb do stavu qe, tak můžu pokračovat zase od kořene qe (nebo od kteréhokoliv jiného stavu qe).
A když spojíš stejně pojmenované stavy, tak dostaneš přechodový graf. Na původním obrázku mi chyběli dva spodní koncové stavy, tak to asi bylo trochu matoucí. Teď už je to snad jasnější.
A že můžeme konečný automat reprezentovat výpočetní stavem potvrzují i skripta na straně 12.

(kdybych náhodou psal nesmysly, tak mě někdo opravte :-) )

, 2008/06/11 17:14

Ahoj, v casti o minimalizacii, pri definicii reduktu je uvedene, ze stavy su triedy rozkladu <em>M</em>/, ma tam byt zrejme Q namiesto M…

, 2008/06/16 22:57

Díky, opraveno.

, 2008/06/19 16:53

Myslím si, že v definici 2.1 je slovo totální v zavádějícím kontextu. Takhle to vypadá, jako by Q x Sigma → Q byla parciální a Q x Sigma → 2^Q byla totální a přitom imho je rozdíl v tom, jestli má nebo nemá definovanou hodnotu pro každý parametr. To jestli má obor hodnot Q nebo 2^Q rozlišuje imho jen DFA od NFA…

Jinak řečeno parciální je třeba pro FA ({q0,q1},{a,b},delta,q0,{q1}) delta definovaná jako d(q0,a)=q1, zatímco totální by byla třeba: d(q0,a)=q1,d(q0,b)=qx,d(q1,a)=qx,d(q1,b)=qx a qx by se přidal jako nový stav „černá díra“. A v obou případech by to byl DFA a navíc by byly ekvivalentní.

Pletu se nebo je to tak ;-)? Díky ;-).

, 2008/06/19 19:24

Jo, je to tak. Trochu jsem to přepsal, aby to nebylo zavádějící ;-)

, 2008/06/21 16:58

Při převodu NFA na DFA jsou koncové stavy všechy, které vznikly sjednocením množiny stavů ve které byl aspoň jeden stav koncový?

, 2008/06/22 11:12

viz prakticke vysvetleni algoritmu: „Algoritmus končí, ve chvíli kdy není možné nalézt žádný nový stav. Vstupní stavy zůstávají stejné, koncové stavy jsou ty, které obsahují některý z původních koncových stavů.“

, 2009/02/03 00:43

jestli to jeste nekdo cte, tak me se u statnic zeptal p. Strejcek na redukci epsilon pravidel

You could leave a comment if you were logged in.
home/inf/ap9.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0