Limity konečných automatů
L = {an
bn
| n  0} = {, ab, aabb, aaabbb, aaaabbbb . . .}
a a a a a b b b b b
IB102 Automaty a gramatiky, 29. 9. 2008 1
Předpokládejme, že existuje automat M příjímající jazyk L.
Nechť M má k stavů.
Uvažme výpočet M na slově an
bn
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, 29. 9. 2008 2
aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb
Platí
^(q0, x) = p ^(p, y) = p ^(p, z) = r  F
Pak ale
^(q0, xz) = ^(^(q0, x), z) = ^(p, z) = r  F
aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb
IB102 Automaty a gramatiky, 29. 9. 2008 3
Analogicky můžeme "vsunout" slovo y
^(q0, xyyyz) = ^(^(^(^(^(q0, x), y), y), y), z)
= ^(^(^(^(p, y), y), y), z)
= ^(^(^(p, y), y), z)
= ^(^(p, y), z)
= ^(p, z)
= r  F
IB102 Automaty a gramatiky, 29. 9. 2008 4
Lemma 1. [o vkládání, pumping lemma] Nechť L je regulární jazyk.
Pak existuje n  N takové,
že libovolné slovo w  L délky alespoň n lze psát ve tvaru
w = xyz, kde |xy|  n, y =  a xyi
z  L pro každé i  N0.
Důkaz. Nechť FA M = (Q, , , q0, F) rozpoznává jazyk L.
Položme n = card(Q).
Pro libovolné slovo w  L délky alespoň n platí, že automat M 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 =  a
^(q0, x) = p, ^(p, y) = p a ^(p, 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 ^(p, yi
) = p pro libovolné i  N0, proto také ^(q0, xyi
z) = r,
tj. xyi
z  L(M) pro každé i  N0. 2
IB102 Automaty a gramatiky, 29. 9. 2008 5
L je regulární = n  N .
w  L . |w|  n =
 x, y, z . ( w = xyz  y =   |xy|  n 
i  0 . xyi
z  L )
Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární
Nechť pro jazyk L platí:
* pro libovolné n  N
* existuje takové slovo w  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 = 
* existuje alespoň jedno i  N0 takové, že xyi
z  L.
Pak z Lemma o vkládání plyne, že L není regulární.
IB102 Automaty a gramatiky, 29. 9. 2008 6
Příklad důkazu ne-regularity
pomocí Lemmatu o vkládání
L = {ucm
uR
| u  {a, b}
, m > 0}
IB102 Automaty a gramatiky, 29. 9. 2008 7
Myhill-Nerodova věta
Motivace I
L = {w  {a, b}
| #a(w)  3}
IB102 Automaty a gramatiky, 29. 9. 2008 8
Pravá kongruence
Definice 2.20. Nechť  je abeceda a  je ekvivalence na 
.
Ekvivalence  je pravá kongruence (zprava invariantní), pokud pro
každé u, v, w  
platí
u  v = uw  vw
Index ekvivalence  je počet tříd rozkladu 
/.
Je-li těchto tříd nekonečně mnoho, klademe index  roven .
Tvrzení 2.21. Ekvivalence  na 
je pravá kongruence právě když
pro každé u, v  
, a   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, 29. 9. 2008 9
Příklad
 = {a, b}
: u  v  u a v začínají stejným symbolem
(počet tříd ekvivalence 3)
: u  v  #a(u) = #a(v)
(počet tříd ekvivalence nekonečný)
: u  v  u a v mají stejné předposlední písmeno
IB102 Automaty a gramatiky, 29. 9. 2008 10
Myhill-Nerodova věta
Motivace II
IB102 Automaty a gramatiky, 29. 9. 2008 11
Myhill-Nerodova věta
Motivace III
IB102 Automaty a gramatiky, 29. 9. 2008 12
Prefixová ekvivalence
Definice 2.25. Nechť L je libovolný (ne nutně regulární) jazyk nad
abecedou . Na množině 
definujeme relaci L zvanou prefixová
ekvivalence pro L takto:
u L v
def
 w  
: uw  L  vw  L
IB102 Automaty a gramatiky, 29. 9. 2008 13
Příklad
L = {w  {a, b}
| #a(w)  3}
L má . . . třídy ekvivalence
L = {an
bn
| n  0}
L má . . . tříd ekvivalence
IB102 Automaty a gramatiky, 29. 9. 2008 14
Myhill-Nerodova věta
Věta 2.28. Nechť L je jazyk nad .
Pak tato tvrzení jsou ekvivalentní:
1. L je rozpoznatelný konečným automatem.
2. L je sjednocením některých tříd rozkladu určeného pravou kongruencí
na 
s konečným indexem.
3. Relace L má konečný index.
Důkaz.
1 = 2
2 = 3
3 = 1
2
IB102 Automaty a gramatiky, 29. 9. 2008 15
1 = 2
Jestliže L je rozpoznatelný konečným automatem
pak L je sjednocením některých tříd rozkladu určeného pravou
kongruencí na 
s konečným indexem.
* pro daný L rozpoznáváný automatem M zkonstruujeme relaci
požadovaných vlastností
* M = (Q, , , q0, F),  je totální
* na 
definujme binární relaci  předpisem
u  v
def
 ^(q0, u) = ^(q0, v)
* ukážeme, že  má požadované vlastnosti
IB102 Automaty a gramatiky, 29. 9. 2008 16
u  v
def
 ^(q0, u) = ^(q0, v)
­  je ekvivalence (je reflexivní, symetrická, tranzitivní)
­  má konečný index
třídy rozkladu odpovídají stavům automatu
­  je pravá kongruence:
Nechť u  v a a  . Pak ^(q0, ua) = (^(q0, u), a) =
(^(q0, v), a) = ^(q0, va) a tedy ua  va.
­ 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, 29. 9. 2008 17
2 = 3
Nechť L je sjednocením některých tříd rozkladu určeného pravou
kongruencí R na 
s konečným indexem.
Pak prefixová ekvivalence L má konečný index.
* uRv = u L v pro všechna u, v  
(tj. R 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, 29. 9. 2008 18
3 = 1
Nechť prefixová ekvivalence L má konečný index.
Pak jazyk L je rozpoznatelný konečným automatem.
Zkonstruujeme automat M = (Q, , , q0, F) přijímající L:
* Q = 
/L
Stavy jsou třídy rozkladu 
určeného ekvivalencí L. (Konečnost!)
* F = {[v] | v  L}
* q0 = []
*  je definována pomocí reprezentantů: ([u], a) = [ua]
Definice  je korektní, protože nezávisí na volbě reprezentanta.
IB102 Automaty a gramatiky, 29. 9. 2008 19
Důkaz korektnosti, tj. L = L(M)
* ^([], v) = [v] pro každé v  
(indukcí k délce slova v)
* v  L(M)  ^([], v)  F  [v]  F  v  L
IB102 Automaty a gramatiky, 29. 9. 2008 20
Použití Myhill-Nerodovy věty I
L = {w  {a, b}
| #a(w)  3}
Třídy ekvivalence relace L: T1 = {w  {a, b}
| #a(w) = 0}
T2 = {w  {a, b}
| #a(w) = 1}
T3 = {w  {a, b}
| #a(w) = 2}
T4 = {w  {a, b}
| #a(w)  3}
L má konečný index =
L je rozpoznatelný konečným automatem, tj. regulární (3 = 1)
IB102 Automaty a gramatiky, 29. 9. 2008 21
Použití Myhill-Nerodovy věty II
L = {an
bn
| n  0}
Nechť i = j. Pak ai
L aj
, protože ai
bi
 L ale aj
bi
 L.
Žádné ze slov a, a2
, a3
, a4
, a5
, a6
, . . . nepadnou do stejné třídy
ekvivalence relace L.
L nemá konečný index =
L není regulární (3 = 1)
IB102 Automaty a gramatiky, 29. 9. 2008 22
Použití Myhill-Nerodovy věty III
Věta 2.29. a 2.31. Minimální konečný automat akceptující jazyk
L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů).
Počet stavů minimálního automatu rozpoznávajícího jazyk L je roven
indexu prefixové ekvivalence L.
IB102 Automaty a gramatiky, 29. 9. 2008 23