Limity konečných automatu
L = {anbn | n > 0} = {e, ab, aabb. aaabbb. aaaabbbb...}
aaaaabbbbb
IB102 Automaty a gramatiky, 2.10.2017
1/22
Předpokládejme, že existuje automat M přijímající jazyk L Nechť M má k stavů.
Uvažme výpočet M 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, 2.10.2017
2/22
aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb
Platí 8(q0,x)=p 8(p,y)=p S{p1z) = reF Pak ale  S(q0,xz) = S(S(q0,x),z) = S(p,z) = r e F
aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb
IB102 Automaty a gramatiky, 2.10.2017 3/22
Analogicky můžeme „vsunout" slovo y:
Hqo,xyyyz) = ^(KH^(Qo,x),y),y),y),z)
= 8{8{8{5{p,yly\y),z)
= 6(S(5(p,y),y),z)
= S($(p,y),z)
= 8(p,z)
= re F
IB102 Automaty a gramatiky, 2.10.2017
4/22
Lemma, [o vkládání, pumping lemma]
Nechť /_je regulární jazyk.
Pak existuje n g N takové, že libovolné slovo w e L délky alespoň n lze psát ve tvaru w = xyz, kde \xy\ < n, y ^ e a xy'z e L pro každé / g N0.
Důkaz. Nechť DFA M = (Q, Z, 5, Qo> O rozpoznává jazyk L Položme n = card(Q).
Pro libovolné slovo 1/1/ g /- délky alespoň n platí, že automat M projde při akceptování slova w (alespoň) dvakrát stejným stavem.
Slovo w tedy můžeme rozdělit na tři části: w = xyz, kde y^ea $(q0, x) = p, 5(p, y) = p a 5(p, z) = r g 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,y') = p pro libovolné / g N0, proto také ô(q0,xy'z) = r,
tj. xy'z g L(A^) pro každé / g N0. □
IB102 Automaty a gramatiky, 2.10.2017
5/22
/_je regulární
3A7GN.
Vi/i/ g L . (
i/l/l > A7
3x, y, z . ( w = xyz A y/e A V/>0.xy'ze/_))
xy| < n A
Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární.
Nechť pro jazyk L platí:
■ pro libovolné n g N
■ existuje takové slovo w e 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| < n a y ^ e,
■ existuje alespoň jedno / g N0 takové, že xy'z 0 L Pak z Lemma o vkládání plyne, že L není regulární.
IB102 Automaty a gramatiky, 2.10.2017
6/22
Príklad důkazu ne-regularity pomocí Lemmatu o vkládání
L = {ucmuR | u e {a, Ď}*, m > 0}
IB102 Automaty a gramatiky, 2.10.2017
7/22
Myhillova-Nerodova věta Motivace I
Každý DFA (Q, Z, S, q0, F) s totální přechodovou funkcí definuje ekvivalenci ~ na Z*:
u ~ v        S(qo, u) = S(q0, v)
L = {we{a,b}*\#a(w)>3}
IB102 Automaty a gramatiky, 2.10.2017 8/22
Pravá kongruence
Definice 2.20. Nechť Z je abeceda a ~ je ekvivalence na Z*. Ekvivalence ~ je pravá kongruence (zprava invariantní), pokud pro
každé u, v, w e Z* platí:
u ~ v =4> uw ~ vw
Tvrzení 2.21. Ekvivalence ~ na Z* je pravá kongruence právě když pro každé u,v£ Z*, a g Z platí i/ ~ v =4> L/a ~ va. (Implikace =4> ye triviální, implikace     se snadno ukáže indukcí k délce zprava přiřetězeného slova w.)
Index ekvivalence ~ je počet tříd rozkladu Z*/~-
Je-li těchto tříd nekonečně mnoho, klademe index ~ roven oc.
IB102 Automaty a gramatiky, 2.10.2017
9/22
Příklad
Jsou tyto relace na slovech nad abecedou Z = {a, b} pravé kongruence?
u ~ v <=^> u a v začínají stejným symbolem nebo u = v = s index ~ je ...
u~ v ^ #a(i/) = #a(v) index ^ je ...
l/ ~ y <=^> l/ai/ mají stejné předposlední písmeno nebo \u\,\v\ < 1 index ^ je ...
IB102 Automaty a gramatiky, 2.10.2017
10/22
Myhillova-Nerodova věta
Pravá kongruence ~ na Z* s konečným indexem jednoznačně (až na pojmenování stavů) určuje DFA (Q, Z, 5, q0,0) s totální prechodovú funkcí a bez nedosažitelných stavů slpňující:
u ~ v       S(q0, u) = í(q0j v) L/ ~ y <==^> u 3. v začínají stejným symbolem nebo u = v = e
IB102 Automaty a gramatiky, 2.10.2017
11/22
Prefixová ekvivalence
Definice 2.25. Nechť L je libovolný (ne nutně regulární) jazyk nad abecedou Z. Na množině Z* definujeme relaci ~L zvanou prefixová ekvivalence pro L takto:
de f
u ~. v <^> Vi/l/ g Z* : uw g L <^> vw e L
Věta. ~L je pravá kongruence.
IB102 Automaty a gramatiky, 2.10.2017
12/22
Příklad
L = {we{a,b}*\#a(w)>3} index ~L je ...
L = {anbn | n > 0} index ~,_ je ...
IB102 Automaty a gramatiky, 2.10.2017
Myhillova-Nerodova věta
Věta 2.28. Nechť L je jazyk nad Z. Pak tato tvrzení jsou ekvivalentní
□ L\e rozpoznatelný deterministickým konečným automatem.
H /_je sjednocením některých tříd rozkladu určeného pravou kongruencí na Z* s konečným indexem.
B Relace ~L má konečný index. Důkaz.
1 2 3 1
IB102 Automaty a gramatiky, 2.10.2017
1 2
Jestliže /_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 Z* s konečným indexem.
■ pro daný L rozpoznávaný automatem M zkonstruujeme relaci požadovaných vlastností
■ M = (Q? z, 5, g0j O'  Je totální
■ na Z* definujme binární relaci ~ předpisem
def    ^ ^
u~v S(qo,u) = 6(q0,v)
■ ukážeme, že ~ má požadované vlastnosti
IB102 Automaty a gramatiky, 2.10.2017
15/22
u~v S(q0,u) = S(q0jv)
■ ~ je ekvivalence (je reflexivní, symetrická, tranzitivní)
■ ~ má konečný index
třídy rozkladu odpovídají stavům automatu
■ ^ je pravá kongruence: Nechť íi^i/aaGl. Pak
5(cfe, i/a) = 5(5(cfe, i/), a) = 5(5(qb, v), a) = <5(g0, va) a tedy ua
■ L je sjednocením těch tříd rozkladu určeného relací ~, které odpovídají koncovým stavům automatu M
IB102 Automaty a gramatiky, 2.10.2017
2^3
Nechť /_je sjednocením některých tříd rozkladu určeného pravou
kongruencí R na Z* s konečným indexem.
Pak prefixová ekvivalence ~L má konečný index.
■ uRv =4> u ~Lv pro všechna íí,i/gF (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 =4> ~L má konečný index □
IB102 Automaty a gramatiky, 2.10.2017
17/22
3 1
Nechť prefixová ekvivalence ~L má konečný index.
Pak jazyk L je rozpoznatelný deterministickým konečným automatem.
Zkonstruujeme automat M = (Q, Z, 5, g0j F) přijímající /_:
■ Q = E*/„L
Stavy jsou třídy rozkladu Z* určeného ekvivalencí ~L. (Konečnost!)
■ Qo = [e]
■ S je definována pomocí reprezentantů: S([u],á) = [L/a] Definice S je korektní, protože nezávisí na volbě reprezentanta.
m F = {[v]\veL}
IB102 Automaty a gramatiky, 2.10.2017
18/22
Důkaz korektnosti, tj. L = L{M)
■ s([e], v) = [v] pro každé i/gP (indukcí k délce slova v) m v e L(M)       5([e], v) e F <=^> [v] e F <=^> v e L
IB102 Automaty a gramatiky, 2.10.2017
Použití Myhillovy-Nerodovy věty k důkazu neregularity
L = {anbn | n > 0}
Nechť / ^ j. Pak af </>L aJ, protože étí e L ale alb' £ L.
Žádné dvě ze slov a1, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace ~L.
/_ nemá konečný index       Z_ není regulární (-i3 =>
IB102 Automaty a gramatiky, 2.10.2017 20/22
Použití Myhillovy-Nerodovy věty k důkazu regularity
L = {we{a,b}*\#a{w)>3}
Třídy ekvivalence relace ~L:  T-i = {w e {a, b}* \ #a(w) = 0}
T2 = {we{a,b}*\#a(w) = ^ T3 = {we{a,b}*\#a(w) = 2} T4 = {we{a,b}*\#a(w)>3}
~L má konečný index =>■ L je rozpoznatelný deterministickým konečným automatem, tj. regulární (3 1)
IB102 Automaty a gramatiky, 2.10.2017
21/22
Další použití Myhillovy-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, 2.10.2017
22/22