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, gramatiky a složitost, 12.12.2016 1/19
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
Index ekvivalence ~ je počet tříd rozkladu Z*/~-
Je-li těchto tříd nekonečně mnoho, klademe index ~ roven oc.
Tvrzení 2.21. Ekvivalence ~ na Z* je pravá kongruence právě když pro každé u, v g Z*, a g Z platí i/ ~ v =4> ua ~ va. (Implikace =4> 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, 12.12.2016
2/19
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, gramatiky a složitost, 12.12.2016
3/19
Myhillova-Nerodova věta Motivace II
Pravá kongruence ~ na Z* s konečným indexem jednoznačně (až na pojmenování stavů) určuje DFA (Q, Z, 5, g0j O) s totální prechodovú funkcí a bez nedosažitelných stavů slpňující:
u ~ v        S(q0, u) = 5(q0j v) l/ ~ y       u & v začínají stejným symbolem nebo u = v = e
IB102 Automaty, gramatiky a složitost, 12.12.2016
4/19
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, gramatiky a složitost, 12.12.2016
5/19
Příklad
L = {we{a,b}*\#a(w)>3} index ~,_ je ...
L = {anbn | n > 0} index ~,_ je ...
IB102 Automaty, gramatiky a složitost, 12.12.2016
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, gramatiky a složitost, 12.12.2016
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
clof     ^ ^
u~v S(qo,u) = 6(q0,v)
■ ukážeme, že ~ má požadované vlastnosti
IB102 Automaty, gramatiky a složitost, 12.12.2016
8/19
u~v S(q0,u) = S(qo,v)
■ ~ je ekvivalence (je reflexivní, symetrická, tranzitivní)
■ ~ má konečný index
třídy rozkladu odpovídají stavům automatu
■ ~ je pravá kongruence: Nechť í/^i/aaGl. Pak
5(cfe, i/a) = 5(ô(q0, u), a) = ô(ô(q0l v), a) = 5(q0, 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, gramatiky a složitost, 12.12.2016
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, gramatiky a složitost, 12.12.2016
10/19
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]
m S\e definována pomocí reprezentantů: S([u],á) = [ua] Definice S je korektní, protože nezávisí na volbě reprezentanta.
m F = {[v]\veL}
IB102 Automaty, gramatiky a složitost, 12.12.2016
11/19
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, gramatiky a složitost, 12.12.2016
Použití Myhillovy-Nerodovy věty k důkazu neregularity
L = {anbn | n > 0}
Nechť / ^ j. Pak a1 ^L sž, protože étí e L ale atti č L
Žádné dvě ze slov a1, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace
~L nemá konečný index => /_ není regulární (-i3 => -«1)
IB102 Automaty, gramatiky a složitost, 12.12.2016 13/19
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, gramatiky a složitost, 12.12.2016
14/19
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, 12.12.2016
15/19
Příklad
Dokažte, že jazyk L = {a'ti | / ^ y, /,/ > 0} není regulární.
IB102 Automaty, gramatiky a složitost, 12.12.2016
Příklad 3.8 a)
Dokažte, že neexistuje DFA se 4 stavy (a s totální přechodovou funkcí) akceptující jazyk L = {w e {a, £>}* \\w\> 4}.
IB102 Automaty, gramatiky a složitost, 12.12.2016
17/19
Příklad 3.12
Určete relaci ~L a její index pro tyto jazyky:
a)L = {a}*.{b}*.{c}* b)L = {anbncn \n>0}
IB102 Automaty, gramatiky a složitost, 12.12.2016
18/19
Příklad 3.13
Nechť Z = {a, b}. Uvažte následující relace na množině Z*:
a) u ~ v   <=^>   #a(u) mod 4 = #a(v) mod 4
b) u ~ v   <=^>   #a(^) niod 4 = #a(v) mod 4
nebo l/ i v končí na stejné písmeno
c) u ~ v <=^>   #a(^) mod 4 = #a(v) mod 4
a a i v končí na stejné písmeno (nebo ív = v = e)
U každé relace určete, zdaje to ekvivalence. Pokud ano, určete její index a zda je pravou kongruencí. Pokud ano, nalezněte jazyk L takový, že ~L = ~. Nakonec nalezněte jazyk /_', který je sjednocením některých tříd rozkladu Z*/ ~, ale přitom ~L, -é ~.
IB102 Automaty, gramatiky a složitost, 12.12.2016
19/19
Eliminace ekvivalentních stavů
Nechť M = (0,51,5, q0l F) je DFA bez nedosažitelných stavů, jehož přechodová funkce je totální.
Definice 2.32. Stavy p, q nazveme jazykově ekvivalentní, psáno p pokud
p = q Mw G Z* : (<5(p, w) e F <5(g, w) e F).
IB102 Automaty, gramatiky a složitost, 3. 10. 2016