Myhill-Nerodova věta Motivace I
Každý DFA (Q, Z, S, q0, F) s totální přechodovou funkcí definuje ekvivalenci ~ na Z*:
í; ~ v        S(qo, u) = S(q0, v)
L = {we{a,b}*\#a(w)>3}
IB102 Automaty, gramatiky a složitost, 21.12.2015 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 e Z*, a e 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, 21.12.2015
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 = e index ~ je ...
index ~ je ...
u ~ v <=^> 1/ a v mají stejné předposlední písmeno nebo \u\,\v\ < 1 index ~ je ...
IB102 Automaty, gramatiky a složitost, 21.12.2015
3/19
Myhill-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(qo, u) = S(qo, v) u ~ v <=^> u a v začínají stejným symbolem nebo u=v = e
IB102 Automaty, gramatiky a složitost, 21.12.2015
4/19
Prefixová ekvivalence
Definice 2.25. Nechť Z. 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 ~L v <^> Mw g Z* : uw g L <^> vw e L
Věta. ~L je pravá kongruence.
IB102 Automaty, gramatiky a složitost, 21.12.2015
5/19
Příklad
L = {we{a,b}*\#a(w)>3} index ~t je ...
L = {anbn | n > 0} index ~t je ...
IB102 Automaty, gramatiky a složitost, 21.12.2015
Myhill-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, 21.12.2015
1 2
Jestliže /.je rozpoznatelný deterministickým konečným automatem pak /.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, g0, O'  Je totální
■ na Z* definujme binární relaci ~ předpisem
u~v S(qo,u) = 6(q0,v)
■ ukážeme, že ~ má požadované vlastnosti
IB102 Automaty, gramatiky a složitost, 21.12.2015
8/19
u~v S(qo,u) = S(qo,v)
■ ~ je ekvivalence (je reflexivní, symetrická, tranzitivní)
■ ~ má konečný index
řr/c/y rozkladu odpovídají stavům automatu
■ ~ je pravá kongruence: Nechť t/~i/aael. Pak
5(0o, i/a) = 5(5(Qo, a), a) = 5(5(cfo, v), a) = č(cfo, 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, 21.12.2015
2^3
Nechť Z. 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, 21.12.2015
10/19
3 1
Nechť prefixová ekvivalence ~L má konečný index.
Pak jazyk /.je rozpoznatelný deterministickým konečným automatem.
Zkonstruujeme automat M = (Q, Z, S, q0, F) přijímající Ľ m Q = Z%L
Stavy jsou třídy rozkladu Z* určeného ekvivalencí ~L. (Konečnost!) ■ Qo = [e]
m 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, gramatiky a složitost, 21.12.2015
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, 21.12.2015
Použití Myhill-Nerodovy věty k důkazu neregularity
L = {anbn \n>0}
Nechť / ^ j. Pak a' /L a!, protože a'b' e L ale alb1 & L
Žádné dvě ze slov a1, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace ~L.
~L nemá konečný index =4> Z. není regulární (-i3 =4> -il)
IB102 Automaty, gramatiky a složitost, 21.12.2015 13/19
Použití Myhill-Nerodovy věty k důkazu regularity
L = {we{a,b}*\#a{w)>3}
Třídy ekvivalence relace ~t:  7-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, 21.12.2015
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 /.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, 21.12.2015
15/19
Příklad
Dokažte, že jazyk L = {a1 tí \ i ^ y, i J > 0} není regulární.
IB102 Automaty, gramatiky a složitost, 21.12.2015
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, b}* \\w\> 4}.
IB102 Automaty, gramatiky a složitost, 21.12.2015
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, 21.12.2015
18/19
Příklad 3.13
Nechť Z = {a, b}. Uvažte následující relace na množině Z*:
a) u ~ v   <=^>   #a(^) niod 4 = #a(v) mod 4
b) l/ ~ v   <=^>   #a(^) niod 4 = #a(v) mod 4
nebo u i v končí na stejné písmeno
c) u ~ v <=^>   #a(^) niod 4 = #a(v) niod 4
a u i v končí na stejné písmeno (nebo u = 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 ~/_/ ^ ~.
IB102 Automaty, gramatiky a složitost, 21.12.2015
19/19
Eliminace ekvivalentních stavů
Nechť M = (Q, Z, S, 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(q, w) e F).
IB102 Automaty, gramatiky a složitost, 12.10.2015