Limity konečných automatů
L = {anbn | n > 0} = {e, afr, aafrfr, aaabbb, aaaabbbb...}
aaaaabbbbb
IB102 Automaty a gramatiky, 1.10.2012
1
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 a gramatiky, 1.10.2012
2
aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb
Platí
/\ S\ S\
S(q0,x)=p S(p,y)=p S(p,z)=reF
Pak ale
aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb
IB102 Automaty a gramatiky, 1.10. 2012 3
Analogicky můžeme "vsunout" slovo y
S\ S\ S\ S\
ó(q0,xyyyz)  = S(ó(ó(ó(5(q0,x),y),y),y)
/\         S\         S\ S\
= S(5(5(6(p,y),y),y),z)
S\ S\ S\
= 5(5(5(p,y),y),z)
= S(p,z) = r e F
IB102 Automaty a gramatiky, 1.10.2012
Lemma 1. [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        G L pro každé i G No-
Důkaz. Necht DFA Ai = (Q, S, 5, go? F) rozpoznává jazyk L. Položme n = card(Q).
Pro libovolné slovo w G 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 S(p,yl) = p pro libovolné i G No, proto také 5(qo,xy'lz) = r, tj. xyiz G L(jVÍ) pro každé i G Nq. □
IB102 Automaty a gramatiky, 1.10.2012
5
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
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 x,y,z, že \xy\ < a y ŕ 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 a gramatiky, 1.10.2012
Příklad důkazu ne-regularity pomocí Lemmatu o vkládání
L = {ucmuR \ue {a, 6}*, m > 0}
IB102 Automaty a gramatiky, 1.10.2012
7
Myhill-Nerodova věta Motivace I
L = {we{a,b}*\#a(w)>3}
IB102 Automaty a gramatiky, 1.10.2012
8
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 £ E* 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 £ 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 a gramatiky, 1.10.2012
9
Příklad
£ = {a, b}
~: u ~ v       u a v začínají stejným symbolem ~ má . . . třídy ekvivalence
~: u ~ v        #fl(w) = #aO) ^ má . . . tříd ekvivalence
~: u ~ v       wav mají stejné předposlední písmeno
IB102 Automaty a gramatiky, 1.10.2012
10
Myhill-Nerodova věta Motivace II
IB102 Automaty a gramatiky, 1.10.2012
11
Prefixová ekvivalence
Definice 2.25. Necht L je libovolný (ne nutně regulární) jazyk nad abecedou S. Na množině S* definujeme relaci rsj l zvanou prefixová ekvivalence pro L takto:
u ~L v \/w G E* : uw G L        vw G L
IB102 Automaty a gramatiky, 1.10.2012
12
Příklad
L = {w £ {a, &}* | #a(w) > 3}
má . . . třídy ekvivalence
L = {anbn | n > 0}
ma
tříd ekvivalence
IB102 Automaty a gramatiky, 1.10.2012
13
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 a gramatiky, 1.10.2012
14
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 E* s konečným indexem.
• pro daný L rozpoznávaný automatem A4 zkonstruujeme relaci požadovaných vlastností
• M = (Q, E, ô, q0, F), ô je totální
• na E* definujme binární relaci ^ předpisem
u ~ v 4=^> ô(qo, u) = 5(go5 v)
• ukážeme, že ^ má požadované vlastnosti
IB102 Automaty a gramatiky, 1.10.2012
15
u ~ v <Ä> ô(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) = S(S(qo,v),a) = 5(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 a gramatiky, 1.10.2012
16
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 a gramatiky, 1.10.2012
17
Necht prefixová ekvivalence rsji 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}
qo =
£
S je definována pomocí reprezentantů: 5([u],a) = [ua] Definice S je korektní, protože nezávisí na volbě reprezentanta.
IB102 Automaty a gramatiky, 1.10.2012
18
Důkaz korektnosti, tj. L = L(M)
5{\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 a gramatiky, 1.10.2012
Použití Myhill-Nerodovy věty k důkazu neregularity
L = {anbn | n > 0}
Necht i ^ j. Pak a1 ^L aj, protože ďb1 G L ale a-W ^ L.
Žádné ze slov a1, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace
nemá konečný index
L není regulární   (-i3 =^> -il)
IB102 Automaty a gramatiky, 1.10.2012
20
Použití Myhill-Nerodovy věty k důkazu regularity
L = {we{a,b}*\#a(w)>3}
Třídy ekvivalence relace ~L:   T\ = {w £ {a, 6}* | #a(^) = 0}
T2 = {w G {a,b}* | #aH = 1} T3 = {we{a,b}*\#a(w) = 2} T4 = {w e {a,b}* | #aH > 3}
^L má konečný index =>
L je rozpoznatelný deterministickým konečným automatem, tj. regulární   (3 =^> 1)
IB102 Automaty a gramatiky, 1.10.2012
21
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 a gramatiky, 1.10.2012
22