Limity konečných automatů
L = {anbn | n > 0} = {e, afr, aafrfr, aaabbb, aaaabbbb...}
aaaaabbbbb
IB102 Automaty a gramatiky, 3.10. 2011
1
Předpokládejme, že existuje automat Ai přijímající jazyk L. Necht Ai má k stavů.
Uvažme výpočet Ai 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, 3.10. 2011
2
aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb
Platí
/\ S\ S\
S(q0,x)=p S(p,y)=p 5(p,z)=reF
Pak ale
aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb
IB102 Automaty a gramatiky, 3.10. 2011 3
Analogicky můžeme "vsunout" slovo y
Š(q0,xyyyz)   =  5{5{5{Š(5(q0, x),y),y),y), z)
S\ S\ S\ S\
= 6(5(6(6(p,y),y),y),z)
y\ S\
= 8(S(S(p,y),y),z) = S(S(p,y),z) = 8(p,z) = r e F
IB102 Automaty a gramatiky, 3.10.2011
4
Lemma 1. [o vkládání, pumping lemma] Necht L je regulárníjazyk. Pak existuje n G N takové,
že libovolné slovo w G L délky alespoň n lze psát ve tvaru
w = xyz, kde \xy\ < n, y ^ £ a        G L pro každé i G No-
Důkaz. Necht FA M = (Q, S, 5, go? F) rozpoznáva jazyk L. Položme n = card(Q).
Pro libovolné slovo w G L délky alespoň n platí, že automat Ai 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 ^ e a
/\ /\ /\
S(qo, x) — p, 5(p, y) = p a 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,yl) = p pro libovolné i G No, proto také S(qo,xylz) = r, tj. xy*z e L(M) pro každé i G N0. □
IB102 Automaty a gramatiky, 3.10. 2011
5
L je regulární
3n G N . \/w G L . (
> n
3 x, y, z . ( ii; =        A y ^ £ A Vi > O . 2^2 G L))
^2/
< n
Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární
Necht pro jazyk L platí:
• pro libovolné n G N
• existuje takové slovo w G 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\ < a y ŕ e
• existuje alespoň jedno i G No takové, že xylz ^ L. Pak z Lemma o vkládání plyne, že L není regulární.
IB102 Automaty a gramatiky, 3.10. 2011
Příklad důkazu ne-regularity pomocí Lemmatu o vkládání
L = {ucmuR \u e {a, fc}*,m > 0}
IB102 Automaty a gramatiky, 3.10. 2011
7
Myhill-Nerodova věta Motivace I
L={fflG{fl,ř)}*|#»>3}
IB102 Automaty a gramatiky, 3.10. 2011
8
Pravá kongruence
Definice 2.20.   Necht S je abeceda a ^ je ekvivalence na S*.
Ekvivalence ^ je pravá kongruence (zprava invariantní), pokud pro
každé u,v,w £ S* platí
u ~ v      uw ~ vw
Index ekvivalence ^ je počet tříd rozkladu S*/^.
Je-li těchto tříd nekonečně mnoho, klademe index ^ roven oo.
Tvrzení 2.21.    Ekvivalence ^ na E* je pravá kongruence právě když pro každé u, v £ E*ř a G S 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, 3.10. 2011
9
Příklad
£ = {a, b}
~: u ~ v       u a v začínají stejným symbolem ~ má . . . třídy ekvivalence
~:U~v #a(V) = #aO)
~ má . . . tříd ekvivalence
~: u ~ v       wav mají stejné předposlední písmeno
IB102 Automaty a gramatiky, 3.10. 2011
10
Myhill-Nerodova věta Motivace II
IB102 Automaty a gramatiky, 3.10. 2011
11
Prefixová ekvivalence
Definice 2.25. Necht L je libovolný (ne nutně regulární) jazyk nad abecedou S. Na množině S* definujeme relaci ~L zvanou prefixová ekvivalence pro L takto:
u ~L v \/w G S* : uw G L <^=^> vw G L
IB102 Automaty a gramatiky, 3.10. 2011
12
Příklad
L = {we{a,b}*\#a(w)>3} ~L má . . . třídy ekvivalence
L = {anbn | n > 0}
má . . . tříd ekvivalence
IB102 Automaty a gramatiky, 3.10. 2011
13
Myhill-Nerodova věta
Věta 2.28.    Necht L je jazyk nad E. 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 E* s konečným indexem.
3. Relace ~L má konečný index. Důkaz.
1^2 2^3 3^1
□
IB102 Automaty a gramatiky, 3.10. 2011
14
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* s konečným indexem.
• pro daný L rozpoznávaný automatem A4 zkonstruujeme relaci požadovaných vlastností
• M = (Q, S, ô, q0, F), S je totálni
• na S* definujme binární relaci ~ předpisem
u~v S(qo,u) = ô(qo,v)
• ukážeme, že ~ má požadované vlastnosti
IB102 Automaty a gramatiky, 3.10. 2011
15
u ~ v 4=^> ô(qo, u) = <5(go, v)
— ~ je ekvivalence (je reflexivní, symetrická, tranzitivní)
- ~ má konečný index
třídy rozkladu odpovídají stavům automatu
- ^ je pravá kongruence:
Necht u ~ v a a G S. Pak 5(qo,ua) = 5(5(go, a) = ô(ô(qo,v),a) = ô(qo,va) a tedy im ^ va.
— L je sjednocením těch tříd rozkladu určeného relací ^, které odpovídají koncovým stavům automatu Ai ■
IB102 Automaty a gramatiky, 3.10. 2011
16
Necht L je sjednocením některých tříd rozkladu určeného pravou
kongruencii? na E* s konečným indexem.
Pak prefixová ekvivalence ~L má konečný index.
• uRv      u ~L v pro všechna u, v G E* (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       ~L má konečný index ■
IB102 Automaty a gramatiky, 3.10. 2011
17
Necht prefixová ekvivalence ~L má konečný index. Pak jazyk L je rozpoznatelný konečným automatem.
Zkonstruujeme automat Ai = (Q,E55, qo,F) přijímající L
Stavy jsou třídy rozkladu S* určeného ekvivalencí ~L. (Konečnost!)
F = {[v] \ veL}
£
5 je definována pomocí reprezentantů: ô([u],a) = [ua] Definice ô je korektní, protože nezávisí na volbě reprezentanta
IB102 Automaty a gramatiky, 3.10. 2011
18
Důkaz korektnosti, tj. L = L(Ai)
S([e]^v) = [v] pro každé v £ S* (indukcí k délce slova v)
v e L(M) 5([e],v)eF
v
e F       v e L
IB102 Automaty a gramatiky, 3.10. 2011
Použití Myhill-Nerodovy věty k důkazu neregularity
L = {anbn | n > 0}
Necht i ^ j. Pak é ^L aj, protože       £ L ale ajbl ^ L.
Žádné ze slov a, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace
L
nemá konečný index
L není regulární   (^3 =^> -il)
IB102 Automaty a gramatiky, 3.10. 2011
20
Použití Myhill-Nerodovy věty k důkazu regularity
L = {we{a,b}*\#a(w)>3}
Třídy ekvivalence relace ~L:   Ti = {w G {a, 6}* | #a(^) = 0}
T2 = {w G {a,6}* I #aH = 1} T3 = {we{a,b}*\#a(w) = 2} T± = {w e {a,b}* \ #a(w) >3}
rsji má konečný index =>
L je rozpoznatelný konečným automatem, tj. regulární   (3 =^> 1)
IB102 Automaty a gramatiky, 3.10. 2011
21
Další použití Myhill-Nerodovy věty
Věta 2.29.    a 2.31. Minimální 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, 3.10. 2011
22