Limity konečných automatů
L = {anbn | n > 0} = {e, ah. aabb, aaabbb, aaaabbbb...}
aaaaabbbbb
IB102 Automaty a gramatiky, 4.10.2010
1
Předpokládejme, že existuje automat M přijímající jazyk L. Necht M má k stavU.
Uvažme vypoCet M na slove anbn kde n> k.
aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbb
Protože n > k, musí existovat (z Dirichletova principu) stav p takový, že při Čtení iniciainí posloupnosti SýmbolU a projde automat stavem p (alespoň) dvakrat.
IB102 Automaty a gramatiky, 4.10.2010
2
aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb
Platí
/\ S\ S\
ô(qo,x)= p ô(p,y)= p ô(p,z)= r G F
Pak ale
ô(q0,xz)   =   ô(ô(qo,x),z)   =   ô(p,z)   = r G F
aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb
IB102 Automaty a gramatiky, 4.10.2010
3
Analogicky můžeme "vsunout" slovo y
S\        S\        S\        S\ S\
8(qQ,xyyyz)  =  ô(ô(ô(ô(ô(qo,x),y ),y ),y ),z)
/\   /\   /\ /\
č(č(č(č(p,y ),y ),y ),z)
/\   /\ /\
S(S(S(p,y ),y ),z)
5(5(p,y ),z)
S(p,z) r e F
IB102 Automaty a gramatiky, 4.10.2010
4
Lemma 1. [o vkládání, pumping lemma] Necht L je regulárníjazyk. Pak existuje n G N takove,
Ze libovolne slovo w G L delky alespoň n lze psát ve tvaru
w = xyz, kde \xy| < n, y = e a xy1 z G L pro kaZde i G N0.
DUkaz. Necht FA M = (Q, S, 5, q0,F) rozpoznava jazyk L. PoloZme n = card(Q).
Pro libovolne slovo w G L delky alespoň n platí, ze automat M projde pri akceptovaní slova w (alespoň) dvakrat stejným stavem.
Slovo w se tedy mUzeme rozdelit na tri Časti: w = xyz, kde y = e a
S\ S\ S\
ô(q0, x) = p, y) = p a z) = r G F. Je zrejme, ze ke zopakovaní nejakeho stavu dojde nejpozdeji po zpracovaní prvních n znakU a tedy dostavame \xy\ < n.
Dale 5(p,yl) = p pro libovolne i G N0, proto take 5(q0,xylz) = r, tj. xy 'z G L (M) pro kazde i G N0. □
IB102 Automaty a gramatiky, 4.10.2010
5
L je regulární ==>  3n G N .
Vw G L . (|w| > n =^>
3 x, y, z . (w = xyz A y = e A |xy| < n A Vi > 0 . xy*z G L))
Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární
Necht pro jázyk L plátí:
• 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\ < n
á y =e
• existuje alespoň jedno i G No takové, že xylz 0 L. Pák z Lemmá o vkládán í plyne, Ze L nen í regulárn í.
IB102 Automáty á grámátiky, 4.10.2010
6
Příklad důkazu ne-regularity pomocí Lemmatu o vkládaní
L = (ucmuR | u G (a, 6}*, m > 0}
IB102 Automaty a gramatiky, 4.10.2010
7
MyhilI-Nerodova věta Motivace I
L = {w G {a, b}* j #a(w) > 3}
IB102 Automaty a gramatiky, 4. 10. 2010
B
Pravá kongruence
Definice 2.20.  Necht S je abeceda a ~ je ekvivalence na S*.
Ekvivalence ~ je pravá kongruence (zprava invariantní), pokud pro
každe u,v,w G S* platí
u ~ v =^> uw ^ vw
Index ekvivalence ~ je pocet tríd rozkladu S*/^.
Je-li techto tríd nekonecne mnoho, klademe index ^ roven oo.
Tvrzení 2.21.    Ekvivalence ^ na S* je prava kongruence prave když
pro každe u, v G S*, a G S platí u ^ v =>* ua ^ va.
(Implikace =^> je triviální, implikace <^= se snadno ukaze indukcí
k delce zprava přiřetezeneho slova w.)
IB102 Automaty a gramatiky, 4.10.2010
9
Příklad
S = {a, b}
u — v u a v začínají stejným symbolem (počet tríd ekvivalence 3)
—: u — v        #a(u) = #a(v) (počet tríd ekvivalence nekonečný)
—: u — v       u a v mají stejne předposlední písmeno
IB102 Automaty a gramatiky, 4.10.2010
10
Myhill-Nerodova věta Motivace II
IB102 Automaty a gramatiky, 4.10.2010
11
Prefixová ekvivalence
Definice 2.25. Necht L je libovolný (ne nutne reguiarní) jažyk nad abecedou E. Na množine E* definujeme relaci ~L žvanou prefixová ekvivalence pro L takto:
u rsjL v Mw e E* : uw e L <é^> vw e L
IB102 Automaty a gramatiky, 4. 10. 2010
12
Príklad
L = {w G {a, b}* | #a(w) > 3} ma . . . tr ídy ekvivalence
L = {anbn | n > 0}
ma . . . tr íd ekvivalence
IB102 Automaty a gramatiky, 4.10.2010
13
Myhill-Nerodova věta
Věta 2.28.    Necht L je jazyk nad E. Pak tato tvrzení jsou ekvivalentní:
1. L je rozpoznatelný koneCnym automatem.
2. L je sjednocen ím nekterych tr íd rozkladu urCeneho pravou kongruenc í na E* s konecnym indexem.
3. Relace ~L ma konecny index. Důkaz.
1 2
2 3
3 1
□
IB102 Automaty a gramatiky, 4.10.2010
14
1 2
Jestliže L je rozpoznatelný konečným automatem
pak L je sjednocením  nekterých tříd  rozkladu  určeneho pravou
kongruencí na S* s konečným indexem.
• pro daný L rozpoznavaný automatem M zkonstruujeme relaci poZadovaných vlastností
• M = (Q, S, ô, q0, F), 5 je totalní
• na S* definujme binarní relaci ^ předpisem
u ~ v 5(q0, u) = 5(q0, v)
• ukazeme, ze ^ ma pozadovane vlastnosti
IB102 Automatý a gramatiký, 4.10.2010
15
u ~ v ô(q0, u) = 5(q0, v)
— ^ je ekvivalence (je reflexivn í, symetricka, tranzitivn í)
— ^ ma koneCny index
třídy rozkladu odpovídají stavUm automatu
— ~ je prava kongruence:
Necht u ~ v a a G S. Pak 5(q0,ua) = 5(5(q0,u),a) = 5(5(q0,v),a) = 5(q0,va) a tedy ua ~ va.
— L je sjednocen ím tech tříd rozkladu urceneho relac í ktere odpov ídaj í koncovym stavum automatu M I
IB102 Automaty a gramatiky, 4. 10. 2010
16
2 3
Necht L je sjednocen ím nekterých tříd rozkladu určeneho pravou
kongruenc í R na S* s konecným indexem.
Pak prefixova ekvivalence — L ma konecný index.
• uRv =>* u —L v pro vsechna u,v G S* (tj. R C—L)
• kaZda trída ekvivalence relace R je cela obsaZena v nejake tríde ekvivalence —L
• index ekvivalence —L je mens í nebo roven indexu ekvivalence R
• R ma konecný index =^ —L ma konecný index ■
IB102 Automatý a gramatiký, 4. 10. 2010
17
3 1
Necht prefixová ekvivalence ~L má konečný index. Pak jazýk L je rozpoznatelný konečným automatem.
Zkonstruujeme automat M = (Q,       g0, F) prij ímaj íc í L:
• Q = S*
Stavy jsou třídy rozkladu S* určeného ekvivalencí ~L. (Konečnost!)
• F = {[v] | v G L}
• Qo = [e]
• 5 je definováná pomoc í reprezentántU: ô ([u], a) = [ua] Definice ô je korektní, protože nezávisí na volbě reprezentanta.
IB102 Automáty á grámátiky, 4. 10. 2010
18
Dukaz korektnosti, tj. L = L (M)
• 5([£],v) = [v] pro kazde v G E* (indukcí k delce slova v)
• v G L (M) <=^> S([e],v) G F [v ] G F v G L ■
IB102 Automaty a gramatiky, 4. 10. 2010
19
PouZit í Myhill-Nerodovy vety I
L = {anbn | n > 0}
Necht i = j. Pak a1 ^L aj, protože albl G L ale ajb1 G L.
Žadne že slov a, a2 , a3 ,a4,a5 , a6,... nepadnou do stejne třídy ekvivalence relace
rsjL nema konecny index
L nen í regularn í   (-3 =>* -1)
IB102 Automaty a gramatiky, 4. 10. 2010
20
Použití Myhill-Nerodovy vety II
L = {w G{a,b}* | #a(w) > 3}
Tr ídý ekvivalence relace —L:   T = {w G {a,b}* | #a(w) = 0}
T2 = {w G{a,b}* | #a(w) = 1} T3 = {w G{a,b}* | #a(w) = 2} T4 = {w G{a,b}* | #a(w) > 3}
—L ma konecný index =^>
L je rozpoznatelný konecným automatem, tj. regulární   (3 =>* 1)
IB102 Automatý a gramatiký, 4. 10. 2010 21
PouZití Myhill-Nerodovy vety III
Veta 2.29.    a 2.31. Minimaln í konecny automat s totaln í
prechodovou funkc í akceptuj íc í jazyk L je urcen jednoznacne az na isomorfismus (tj. pňejmenovan í stavu). Pocet stavu tohoto automatu je roven indexu prefixove ekvivalence ~L.
IB102 Automaty a gramatiky, 4. 10. 2010
22