Konečné automaty
Definice 1. Deteministický konečný automat (Deterministic Finite Automaton, DFA) M je pětice (Q, S, 5, qo,F), kde
• Q je neprázdna konečná množina stavů.
• S je konečná vstupní abeceda.
• 5 : QxS^Qje parciální přechodová funkce.
• Qo £ Q Je počáteční (iniciální) stav.
• i7" ^ Q je množina koncových (akceptujících) stavů.
IB102 Automaty, gramatiky a složitost, 23. 9. 2013 1
Příklad a zápis tabulkou
IB102 Automaty, gramatiky a složitost, 23.9.2013
2
Zápis grafem
IB102 Automaty, gramatiky a složitost, 23.9.2013
3
Výpočet konečného automatu
Rozšírená přechodová funkce S: Q x S* —> Q je parciální funkce definovaná induktivně vzhledem k délce slova ze S*:
• S(q,e) = q pro každý stav q G Q.
S(q1 wa) —
S(S(q,w),a) je—li S(q,w) i S(S(q,w),a) definováno, _L jinak.
Slovo w je akceptováno automatem M právě když 5(go, w) G F Slovo ii; je zamítáno automatem M právě když S(qo,w) ý. F.
IB102 Automaty, gramatiky a složitost, 23.9.2013
Jazyk přijímaný (akceptovaný, rozpoznávaný) automatem Ai je
L(M) = {w G S* | ô(q0,w) G F}.
Jazyk, který je rozpoznatelný (nějakým) deterministickým konečným automatem, nazveme regulárni.
Ekvivalenci deterministických podobně jako v případě gramatik: pokud L(M) = L(M').
konečných automatů definujeme automaty M a M1 jsou ekvivalentní,
IB102 Automaty, gramatiky a složitost, 23.9.2013
5
Parcialita přechodové funkce
Přechodová funkce ô zavedena jako parciální.
Parcialita přechodové funkce nemá podstatný vliv na výpočetní
konečných automatů.
Lemma 1. Ke každému DFA Ai existuje ekvivalentní DFA s totální přechodovou funkcí.
Idea důkazu
a
IB102 Automaty, gramatiky a složitost, 23.9.2013
Důkaz. Necht M = (Q,X,ô,q0,F). Necht automat M1 je definován předpisem
M! = (QU{p},X,ô',q0,F), kdepČQ a
6'(q, a) =
S(q,a) je-li S(q,a) definováno, p jinak.
Zejména 5'(p, a) — p pro každé a G S.
Důkaz korektnosti:
• „A/ľ má totální přechodovou funkci - zřejmé z definice Aif.
• A4 a A4' jsou ekvivalentní - dokážeme.
IB102 Automaty, gramatiky a složitost, 23.9.2013
7
Indukcí k délce slova ověříme, že pro každé q G Q a w G £* platí
<5'(g,iy) =
5(q,w) je-li 5(q,w) definováno, p jinak.
Jelikož p £ F, platí L(M) = D
IB102 Automaty, gramatiky a složitost, 23.9.2013
8
Konstrukce konečných automatů
Máme za úkol sestrojit automat rozpoznávající jazyk
L — {w £ {a, 6}* | ii; obsahuje podslovo afraa}
Označení stavů automatu zvolíme tak, aby bylo patrné, jaká část požadovaného podslova abaa již byla automatem přečtena:
IB102 Automaty, gramatiky a složitost, 23.9.2013
9
Příklad
{w £ {a, 6}* | w obsahuje podslovo abaa
IB102 Automaty, gramatiky a složitost, 23.9.2013
A (w — b V w začíná i končí na a a mezi dvěma výskyty b je alespoň jedno a)}
10
Synchronní paralelní kompozice automatů
Pro dané automaty Mi a M2 umožňuje sestrojit automat rozpoznávající průnik (sjednocení, rozdíl) jazyků L(Mi) a L(M2)-
Necht Mi = (Qi,S,(Ji,^i,Fi), M2 = (Q2,£,<52,(72,F2) a přechodové funkce 61,62 jsou totální.
Definujeme DFA M3 = (Q3, S, S3, <?3, F3), kde
• Q3 = Qi x Q2 = {(p, g) I p g Qi, g g Q2}
• F3 = Fi x F2 = {(p, g) I p g Fi, q g F2}
• Qs = (<7i,42)
• č3((p,g),a) = (6i(p,a),62(q,a)) Tvrzení: L(M3) = L{Mi) n L(M2)
IB102 Automaty, gramatiky a složitost, 23.9.2013
11
Důkaz. Nejprve dokážeme toto tvrzení:
> 5i(qi,w) =p Aá2(92,^) = q
Důkaz se provede indukcí vzhledem k w .
• Základní krok \w
0:
Z definice 63((q1,q2),e) = (91,^2), S^q^e) = qlt 52(q2,e) = #2-Pro ii; = e je tedy ekvivalence platná.
• Indukční krok: Necht w = va, kde i; £ E*, a £ E. Platí:
S((tfi,02),wO = (p,q)
£((21,02),^) = (r,s) A <J3((r, s), a) = <í=>
v) = r A 52(92, ^)=5 Aíi(r,a)=|) A 52(s,a) = ? 5i(gi,i;a)=p A 52{q2,va) = q
IB102 Automaty, gramatiky a složitost, 23.9.2013
12
Nyní již lze snadno dokázat vlastní tvrzení věty:
w e L(Ms) ^=>
S3((qu q2),w) = (p, g) kde p e Fx a g e F2 5i(qi,w) = p Aá2(?2,^) = q
w e L(M1)rM(M2). □
Modifikace pro sjednocení, tj. L(Mz) = L(JWi) U L(AÍ2)-
DÚ: Modifikujte konstrukci tak, aby platilo L(Mz) = L(jVÍi)\L(jVÍ2).
IB102 Automaty, gramatiky a složitost, 23. 9. 2013 13
Automat pro komplement
K automatu M = (Q,       qo,F) s totální přechodovou funkcí
sestrojíme automat Ai rozpoznávající jazyk co-L(Ai) jako
M = (Q,X,S,q0,Q\F).
IB102 Automaty, gramatiky a složitost, 23.9.2013
14
Limity konečných automatů
L = {anbn | n > 0} = {e, afr, aafrfr, aaabbb, aaaabbbb...}
aaaaabbbbb
IB102 Automaty, gramatiky a složitost, 23.9.2013
15
Předpokládejme, že existuje automat Ai přijímající jazyk L. Necht Ai má k stavů.
Uvažme výpočet Ai na slově anbn kde n > k.
aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbb
Protože n > k, musí existovat (z Dirichletova principu) stav p takový, že při čtení iniciální posloupnosti symbolů a projde automat stavem p (alespoň) dvakrát.
IB102 Automaty, gramatiky a složitost, 23.9.2013
16
aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb
Platí
/\ S\ S\
S(q0,x)=p S(p,y)=p 5(p,z)=reF
Pak ale
aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb
IB102 Automaty, gramatiky a složitost, 23. 9. 2013 17
Analogicky můžeme "vsunout" slovo y
Š(q0,xyyyz)   =  5{5{5{Š(5(q0, x),y),y),y), z)
S\ S\ S\ S\
= 6(5(6(6(p,y),y),y),z)
y\ S\
= 8(S(S(p,y),y),z) = S(S(p,y),z) = 8(p,z) = r e F
IB102 Automaty, gramatiky a složitost, 23.9.2013
18
Lemma 2. [o vkládání, pumping lemma] Necht L je regulární jazyk. Pak existuje n G N takové,
že libovolné slovo w G L délky alespoň n lze psát ve tvaru
w = xyz, kde \xy\ < n, y ^ £ a xylz G L pro každé i G No-
Důkaz. Necht DFA Ai = (Q, S, 5, go? ^) rozpoznává jazyk L. Položme n = card(Q).
Pro libovolné slovo w <E L délky alespoň n platí, že automat Ai projde při akceptování slova w (alespoň) dvakrát stejným stavem.
Slovo w se tedy můžeme rozdělit na tři části: w = xyz, kde y ^ e a
/\ /\ /\
S(qo, x) — p, 5(p, y) — p a z) — r ^ F. Je zřejmé, že ke zopakování nějakého stavu dojde nejpozději po zpracování prvních n znaků a tedy dostáváme \xy\ < n.
Dále ô(p,yl) = p pro libovolné i G No, proto také S(qo,xylz) = r, tj. xy*z e L(M) pro každé i G N0. □
IB102 Automaty, gramatiky a složitost, 23.9.2013
19
L je regulární
3n G N . \/w G L . (
> n
3 x, y, z . ( ii; =        A y ^ e A Vi > O . 2^2 G L))
^2/
< n A
Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární
Necht pro jazyk L platí:
• pro libovolné n G N
• existuje takové slovo w G L délky alespoň n, pro které platí, že
• při libovolném rozdělení slova w na takové tři části    y, z, že \xy\ < n zy^e
• existuje alespoň jedno i G No takové, že xylz ^ L.
Pak z Lemma o vkládání plyne, že L není regulární.
IB102 Automaty, gramatiky a složitost, 23.9.2013
20
Příklad důkazu ne-regularity pomocí Lemmatu o vkládání
L = {ucmuR \u e {a, fc}*,m > 0}
IB102 Automaty, gramatiky a složitost, 23.9.2013
21
Myhill-Nerodova věta Motivace I
L={fflG{fl,ř)}*|#»>3}
IB102 Automaty, gramatiky a složitost, 23. 9. 2013 22
Pravá kongruence
Definice 2.20.   Necht S je abeceda a ^ je ekvivalence na S*.
Ekvivalence ^ je pravá kongruence (zprava invariantní), pokud pro
každé u,v,w G S* platí
u ~ v      uw ~ vw
Index ekvivalence ^ je počet tříd rozkladu S*/^.
Je-li těchto tříd nekonečně mnoho, klademe index ^ roven oo.
Tvrzení 2.21.    Ekvivalence ^ na E* je pravá kongruence právě když pro každé u, v G E*, a G S platí u ~ v      ua ~ va. (Implikace        je triviální, implikace <<= se snadno ukáže indukcí k délce zprava přiřetězeného slova w.)
IB102 Automaty, gramatiky a složitost, 23.9.2013
23
Příklad
£ = {a, b}
~: u ~ v       u a v začínají stejným symbolem ~ má . . . třídy ekvivalence
~:U~v #a(V) = #aO)
~ má . . . tříd ekvivalence
~: u ~ v       wav mají stejné předposlední písmeno
IB102 Automaty, gramatiky a složitost, 23.9.2013
24
Myhill-Nerodova věta Motivace II
IB102 Automaty, gramatiky a složitost, 23.9.2013
25
Prefixová ekvivalence
Definice 2.25. Necht L je libovolný (ne nutně regulární) jazyk nad abecedou S. Na množině S* definujeme relaci rsji zvanou prefixová ekvivalence pro L takto:
u ~L v \/w G E* : uw G L        vw G L
IB102 Automaty, gramatiky a složitost, 23.9.2013
26
Příklad
L = {we{a,b}*\#a(w)>3} ~L má . . . třídy ekvivalence
L = {anbn | n > 0}
má . . . tříd ekvivalence
IB102 Automaty, gramatiky a složitost, 23.9.2013
27
Myhill-Nerodova věta
Věta 2.28.    Necht L je jazyk nad E. Pak tato tvrzení jsou ekvivalentní:
1. L je rozpoznatelný deterministickým konečným automatem.
2. L je sjednocením některých tříd rozkladu určeného pravou kongruencí na E* s konečným indexem.
3. Relace ~L má konečný index. Důkaz.
1^2 2^3 3^1
□
IB102 Automaty, gramatiky a složitost, 23.9.2013
28
1
> 2
Jestliže L je rozpoznatelný deterministickým konečným automatem pak L je sjednocením  některých tříd  rozkladu  určeného pravou kongruencí na S* s konečným indexem.
• pro daný L rozpoznávaný automatem M zkonstruujeme relaci požadovaných vlastností
• M = (Q, S, S, q0, F), 5 je totálni
• na S* definujme binární relaci ~ předpisem
u ~ v
.dej
> ô(q0,u) = ô(q0,v)
• ukážeme, že ~ má požadované vlastnosti
IB102 Automaty, gramatiky a složitost, 23.9.2013
29
u ~ v 4=^> ô(qo, u) = <5(go, v)
— ~ je ekvivalence (je reflexivní, symetrická, tranzitivní)
- ~ má konečný index
třídy rozkladu odpovídají stavům automatu
- ^ je pravá kongruence:
Necht u ~ v a a G S. Pak 5(qo,ua) = 5(5(go, a) = ô(ô(qo,v),a) = ô(qo,va) a tedy im ^ va.
— L je sjednocením těch tříd rozkladu určeného relací ^, které odpovídají koncovým stavům automatu Ai ■
IB102 Automaty, gramatiky a složitost, 23.9.2013
30
Necht L je sjednocením některých tříd rozkladu určeného pravou
kongruencii? na E* s konečným indexem.
Pak prefixová ekvivalence ~L má konečný index.
• uRv      u ~L v pro všechna u, v G E* (tj. R C^L)
• každá třída ekvivalence relace R je celá obsažena v nějaké třídě ekvivalence ~L
• index ekvivalence ~L je menší nebo roven indexu ekvivalence R
• R má konečný index       ~L má konečný index ■
IB102 Automaty, gramatiky a složitost, 23.9.2013
31
Necht prefixová ekvivalence ~L má konečný index.
Pak jazyk L je rozpoznatelný deterministickým konečným automatem
Zkonstruujeme automat Ai = (Q,E55, qo,F) přijímající L:
Stavy jsou třídy rozkladu S* určeného ekvivalencí ~L. (Konečnost!)
F = {[v] \ veL}
£
5 je definována pomocí reprezentantů: ô([u],a) = [ua] Definice ô je korektní, protože nezávisí na volbě reprezentanta
IB102 Automaty, gramatiky a složitost, 23.9.2013
32
Důkaz korektnosti, tj. L = L(Ai)
S([e]^v) = [v] pro každé v £ S* (indukcí k délce slova v)
v e L(M) 5([e],v)eF
v
e F       v e L
IB102 Automaty, gramatiky a složitost, 23.9.2013
Použití Myhill-Nerodovy věty k důkazu neregularity
L = {anbn | n > 0}
Necht i    jm Pak a1 ^L a3\ protože albl G L ale a?bl ^ L.
Žádné ze slov a1, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace
rSJ L
nemá konečný index
L není regulární   (-«3 =>* ->1)
IB102 Automaty, gramatiky a složitost, 23.9.2013
34
Použití Myhill-Nerodovy věty k důkazu regularity
L = {we{a,b}*\#a(w)>3}
Třídy ekvivalence relace ~L:   Ti = {w G {a, 6}* | #a(^) = 0}
T2 = {w G {a,6}* | #aH = 1} T3 = {we{a,b}*\#a(w) = 2} T± = {w e {a,b}* \ #a(w) >3}
rsji má konečný index =>
L je rozpoznatelný deterministickým konečným automatem, tj. regulární   (3 =^> 1)
IB102 Automaty, gramatiky a složitost, 23.9.2013
35
Další použití Myhill-Nerodovy věty
Věta 2.29. a 2.31. Minimální deterministický konečný automat s totální přechodovou funkcí akceptující jazyk L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů). Počet stavů tohoto automatu je roven indexu prefixové ekvivalence ~L.
IB102 Automaty, gramatiky a složitost, 23.9.2013
36