Myhill-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, 15.12.2014 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é t/,i/Gr,3Gl 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.)
IB102 Automaty, gramatiky a složitost, 15.12.2014
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 ...
u~ v ^ #a(u) = #a(v) index ~ je ...
u ~ v u a v mají stejné předposlední písmeno nebo \u\,\v\ < 1 index ~ je ...
IB102 Automaty, gramatiky a složitost, 15.12.2014
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(q0, u) = č(<7o, v) u ~ v <=^> l/ a v začínají stejným symbolem nebo u=v = e
IB102 Automaty, gramatiky a složitost, 15.12.2014
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 51* : uw g L <^> vw e L
Věta. ~L je pravá kongruence.
IB102 Automaty, gramatiky a složitost, 15.12.2014
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, 15.12.2014
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, 15.12.2014
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, <7o, F), 5 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, 15.12.2014
8/19
u~v S(qo,u) = S(qo,v)
■ ~ je ekvivalence (je reflexivní, symetrická, tranzitivní)
■ ~ má konečný index
řř/c/y rozkladu odpovídají stavům automatu
■ ~ je pravá kongruence: Nechť t/~/aaeL Pak
5(qb, i/a) = 5(5(qb,    a) = v), a) = č(cfo, va) a tedy ua
■ Z. 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, 15.12.2014
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 íí^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, 15.12.2014
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, 51, 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 = ŕ]
■ 5 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, 15.12.2014
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, 15.12.2014
Použití Myhill-Nerodovy věty k důkazu neregularity
L = {anbn | n > 0}
Nechť / ^ y. Pak a7' /L a', protože a'Ď7 g L ale ä tí 0 L.
Žádné 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 ==> -"1)
IB102 Automaty, gramatiky a složitost, 15.12.2014
13/19
Použití Myhill-Nerodovy věty k důkazu regularity
L = {we{a,b}*\#a{w)>3}
Třídy ekvivalence relace ~t:  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, 15.12.2014
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, 15.12.2014
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, 15.12.2014
Příklad 3.8 a)
Dokažte, že neexistuje D FA 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, 15.12.2014
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, 15.12.2014
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 ~/_/ 7^ ~.
IB102 Automaty, gramatiky a složitost, 15.12.2014
19/19
Eliminace ekvivalentních stavů
Nechť M = (Q, Z, 5, g0, 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        \/w g Z* : (<5(p, w) e F        <5(<7, w) g F).
IB102 Automaty, gramatiky a složitost, 29.9.2014