Jazyky, automaty a vyčíslitelnost

Organizace

U zkoušky chce jen základní myšlenku, ne přesné kroky.

Slova

Definice Abeceda je libovolná konečná množina Σ. Její prvky jsou písmena. Konečná posloupnost písmen je slovo. Je-li w slovo, jeho délku značíme |w|. Prázdné slovo značíme ε. Množinu všech slov značíme Σ*. Množinu všech neprázdných slov značíme Σ+≔Σ*∖{ε}. Libovolná množina L⊂Σ* je jazyk.
Konvence Konkrétní písmena budu značit 𝖺,𝖻,…, zatímco proměnné zastupující písmena budu značit a,b,….
Definice Nechť v=v1⋯vn,w=w1⋯wm jsou slova. Potom jejich zřetězení je slovo vw≔v1⋯vnw1⋯wm.
Definice Nechť K,L jsou jazyky. Potom jejich zřetězení je jazyk KL≔{vw|v∈K,w∈L}.
Definice Nechť K je jazyk. Definujme mocniny K0≔{ε},Kn+1≔KnK. Potom jeho iterace je K*≔⋃n∈ℕ0Kn a jeho pozitivní iterace je K*≔⋃n∈ℕ+Kn.
Definice Slovo u∈Σ* je prefix slova v∈Σ*, pokud existuje w∈Σ* takové, že v=uw.
Definice Slovo u∈Σ* je sufix slova v∈Σ*, pokud existuje w∈Σ* takové, že v=wu.
Definice Slovo u∈Σ* je faktor/podslovo slova v∈Σ*, pokud existují w1,w2∈Σ* taková, že v=w1uw2.

Konečné automaty

Definice Konečný automat je uspořádaná pětice 𝒜︀=(Q,Σ,E,I,F), kde Q je konečná množina stavů, I⊂Q je množina počátečních stavů, F⊂Q je množina koncových stavů, Σ je abeceda a E⊂Q×Σ×Q je množina přechodů. Přechod (p,a,q)∈E budeme značit p→aq.
Příklad Příkladem automatu je
𝒜︀𝖺𝖻=({p,q,r},{𝖺,𝖻},{(p,𝖺,p),(p,𝖻,p),(p,𝖺,q),(q,𝖻,r),(r,𝖺,r),(r,𝖻,r)},{p},{r})
V tom se ale nikdo nevyzná, takže budeme automat pojímat jako ohodnocený orientovaný graf, kde stavy jsou vrcholy a přechody jsou hrany ohodnocené písmenem. Počáteční stavy budeme značit šipkou, která vede z ničeho do stavu. Koncové stavy budeme značit šipkou, která vede ze stavu do ničeho. TBD: obrázek
Definice Výpočet konečného automatu 𝒜︀ je posloupnost přechodů c≔p0→a1p1→a2⋯→anpn. Výpočet je úspěšný, pokud p0∈I a pn∈F. Ohodnocení výpočtu je slovo w≔a1⋯an. Úsporně značíme p0→wpn.
Definice Slovo w∈Σ* je akceptované/rozeznávané automatem 𝒜︀, pokud existuje v 𝒜︀ úspěšný výpočet, jehož ohodnocení je w.
Definice Jazyk rozeznávaný/přijímaný automatem 𝒜︀ je L(𝒜︀)≔{w∈Σ*|𝒜︀akceptujew}.
Poznámka I když v definici automatu je všechno konečné, jazyk jím přijímaný nemusí být konečný.
Definice Konečné automaty 𝒜︀1,𝒜︀2 jsou ekvivalentní, pokud L(𝒜︀1)=L(𝒜︀2).
Příklad Jazyk rozeznávaný automatem 𝒜︀𝖺𝖻 z předchozího příkladu je L(𝒜︀𝖺𝖻)={u𝖺𝖻v|u,v∈𝒜︀*}.
Definice Jazyk K je rozeznávaný, pokud existuje konečný automat, který ho rozeznává. Množinu rozeznávaných jazyků nad abecedou Σ značíme RecΣ*.
Poznámka Ne každý jazyk je rozeznávaný. To můžeme vidět například z toho, že konečných automatů je spočetně mnoho, ale jazyků je nespočetně mnoho. Jinak řečeno, RecΣ*⊊𝒫︀(Σ*).
Příklad Příklady rozeznávaných jazyků:
Věta uzavřenost rozeznávaných jazyků na sjednocení Nechť K,L∈RecΣ*. Potom K∪L∈RecΣ*.
Důkaz Vezmeme automat (QK∪QL,Σ,EK∪EL,IK∪IL,FK∪FL), kde bereme QK,QL jako disjunktní. Že bude fungovat, je zřejmé.
Věta uzavřenost rozeznávaných jazyků na průnik Nechť K,L∈RecΣ*. Potom K∩L∈RecΣ*.
Důkaz Vezmeme automat (QK×QL,Σ,E,IK×IL,FK×FL), kde
E≔{((pK,pL),a,(qK,qL))|(pK,a,qK)∈EK∧(pL,a,qL)∈EL}.
Když chceme přijmout slovo, tak najdeme ohodnocení v obou původních automatech a sčupčíme je.
Příklad Mějme automat 𝒜︀𝖺𝖻 jako nahoře a 𝒜︀𝖻𝖺 definovaný analogicky. TBD: obrázek
Definice Konečný automat je úplný, pokud pro každé q∈Q,a∈Σ existuje přechod z q ohodnocený a.
Věta zúplnění automatu Ke každému konečnému automatu existuje ekvivalentní úplný automat.
Důkaz Přidáme tzv. chybový stav, do kterého se můžeme dostat kdykoli a už se z něj nedostaneme ven. Tedy vezmeme automat
(Q∪{☠},Σ,E∪{(q,a,☠)|q∈Q,a∈Σ},I,F).
Poznámka Máme-li dva úplné automaty, můžeme jejich sjednocení zkonstruovat také tak, že vezmeme stejný automat jako u průniku, akorát jako koncové stavy označíme i ty, které jsou koncové jen v jednom z původních automatů.
Definice Nechť u,v∈Σ*. Potom levý kvocient je
u−1v≔{wpokudv=uw,nedefinovánojinak.
Definice Nechť u∈Σ*,K⊂Σ*. Potom levý kvocient je
u−1K≔{w∈Σ⋅|uw∈K}.
Věta uzavřenost rozeznávaných jazyků na levý kvocient Nechť u∈Σ*,K∈RecΣ*. Potom u−1K∈RecΣ*.
Důkaz Vezmeme automat (QK,Σ,EK,Iu,FK), kde
Iu≔{q∈QK|∃i∈IK:i→uq}.
Důsledek Nechť K∈RecΣ*. Potom množina {u−1K|u∈Σ*} je konečná.
Důkaz Je jen konečně mnoho různých množin Iu, které mohou vzniknout.
Příklad Pomocí tohoto důsledku můžeme dokázat, že {𝖺n𝖻n|n∈ℕ0}∉Rec𝛴*, neboť tento jazyk zjevně má nekonečně mnoho různých levých kvocientů.
Definice Stav p∈Q konečného automatu je Automat je užitečný (anglicky trim), pokud má jen užitečné stavy.
Poznámka Pokud z automatu vezmeme jen užitečné stavy, dostaneme tím ekvivalentní užitečný automat s potenciálně méně stavy. K tomu lze použít standardní grafové algoritmy.
Poznámka Zúplněním automatu vznikne neužitečný automat, protože chybový stav není kodosažitelný.
Definice Nechť 𝒜︀=(Q,Σ,E,I,F) je konečný automat. Potom jeho transpozice je 𝒜︀𝖳≔(Q,Σ,ET,F,I), kde E𝖳≔{(q,a,p)|(p,a,q)∈E}.
Definice Zrcadlový obraz slova w=w1⋯wn∈Σ* je w←≔wn⋯w1. Zrcadlový obraz jazyka L⊂Σ* je L←≔{w←|w∈L}.
Věta Nechť 𝒜︀ je konečný automat. Potom L(𝒜︀𝖳)=L(𝒜︀)←.
Důkaz Triviální.
Věta Nechť L∈RecΣ*. Definujme
Pref(L)≔{w∈Σ*|∃v∈Σ*:wv∈L},
Suf(L)≔{w∈Σ*|∃u∈Σ*:uw∈L},
Fakt(L)≔{w∈Σ*|∃u,v∈Σ*:uwv∈L}.
Potom Pref(L),Suf(L),Fakt(L)∈RecΣ*.
Důkaz Vezměme užitečný automat (Q,Σ,E,I,F) pro jazyk L. Potom
  • pro rozeznání Pref(L) použijeme automat (Q,Σ,E,I,Q),
  • pro rozeznání Suf(L) použijeme automat (Q,Σ,E,Q,F),
  • pro rozeznání Fakt(L) použijeme automat (Q,Σ,E,Q,Q).
Je zřejmé, že automaty rozpoznají všechna slova, která rozpoznat mají. To, že nerozpoznají nic navíc, plyne z užitečnosti.
Věta Nechť 𝒜︀ je konečný automat. Potom L(𝒜︀)≠∅, právě když existuje dosažitelný koncový stav.
Důkaz Triviální.
Definice Stav p∈Q konečného automatu je dosažitelný ze stavu q∈Q, pokud existuje výpočet začínající v q a končící v p.
Věta Nechť 𝒜︀ je konečný automat. Potom |L(𝒜︀)|=∞, právě když existuje užitečný stav, který je dosažitelný sám ze sebe neprázdným slovem.
Důkaz
(⇐)
Nechť pro i∈I,p∈Q,t∈F existují výpočty i→up,p→vp,p→wt, kde |v|>0. Potom zjevně každé slovo ve tvaru uvnw,n∈ℕ0 je rozeznávané.
(⇒)
Jistě existuje w∈L(𝒜︀) takové, že |w|>|Q|. Při rozeznání tohoto slova se podle 🐦 holubníkového principu 🐦 musí nějaký vrchol objevit víckrát.
Věta třetí věta o vkládání Nechť L∈RecΣ*. Potom existuje N∈ℕ takové, že pokud f=uv1⋯vNw∈L,u,w∈Σ*,v1,…,vN∈Σ+, potom existují indexy 0≤j<k≤N takové, že
∀n∈ℕ0:uv1⋯vj(vj+1⋯vk)nvk+1⋯vNw∈L.
Důkaz Nechť 𝒜︀ je automat rozeznávající L, N je počet jeho stavů a uv1⋯vNw∈L. Vezměme úspěšný výpočet i→uq0→v1q1→v2⋯→vNqN→wt. V tomto výpočtu je q+1 stavů, takže podle 🐦 holubníkového principu 🐦 se musí nějaký opakovat: qj=qk. Smyčku mezi těmito stavy můžeme projet, kolikrát chceme, z čehož plyne tvrzení věty.
Důsledek druhá věta o vkládání Nechť L∈RecΣ*. Potom existuje N∈ℕ takové, že pokud f=g1hg2∈L,|h|≥N, potom můžeme rozložit h=uvw,u,w∈Σ*,v∈Σ+ tak, že ∀n∈ℕ0:g1uvnwg2∈L.
Poznámka v se nazývá iterovaný faktor nebo pumpovaný faktor.
Důsledek první věta o vkládání Nechť L∈RecΣ*. Potom existuje N∈ℕ takové, že pokud f∈L,|f|≥N, potom můžeme rozložit f=uvw,u,w∈Σ*,v∈Σ+ tak, že ∀n∈ℕ0:uvnw∈L.
Poznámka Anglicky se věta o vkládání nazývá “pumping lemma”, protože slova můžeme „nafukovat“ tím, že nakopírujeme nějaký jejich faktor.
Poznámka Je-li |L|<∞, potom stačí vzít N větší než délka nejdelšího slova v N a podmínka je vakuózně splněna.
Příklad Nechť L≔{𝖺n𝖻n|n∈ℕ0}. Dokážeme pomocí první věty o vkládání, že L∉Rec{𝖺,𝖻}*. Kdyby byl rozeznávaný, potom existuje N∈ℕ0 takové, že 𝖺N𝖻N=uvw,|v|>0 tak, že pro všechna n∈ℕ0 je uvnw∈L. Pokud v=𝖺k nebo v=𝖻k, potom po přifouknutí dostaneme nevyvážené slovo. Pokud v=𝖺k𝖻l,k,l>0, potom po přifouknutí dostaneme slovo ve špatném tvaru.
Poznámka Pomocí druhé věty o vkládání by to šlo o něco jednodušejí – stačilo by zvolit g1≔ε,g2≔𝖻N. Potom musí být v=𝖺k.
Poznámka Věty o vkládání jsou různě silné a žádná z nich nedává postačující podmínku pro to, aby byl jazyk rozeznatelný. Vezměme jazyk
U1≔{𝖺n𝖻n|n≥0}∪{u𝖻𝖺w|u,w∈{𝖺,𝖻}*}.
Potom U1 splní podmínku první věty o vkládání, ale nesplní podmínku druhé věty o vkládání. Dále mějme jazyk
U2≔{(𝖺𝖺𝖻)n(𝖺𝖻𝖻)n|n≥0}∪{uvw|v∈{𝖺𝖺𝖺,𝖺𝖺𝖻𝖻,𝖻𝖻𝖻},u,w∈{𝖺,𝖻}*}.
Potom U2 splní podmínku druhé věty o vkládání, ale nesplní podmínku třetí věty o vkládání. Existuje ještě hnusnější jazyk, který splňuje podmínku třetí věty o vkládání, ale není rozeznávaný.

Zatím jsme hrany ohodnocovali jen písmeny. Změnilo by se něco, kdybychom umožnili je ohodnocovat slovy? Hrana ohodnocená neprázdným slovem je zjevně ekvivalentní posloupnosti několika hran, které se nijak nevětví. Jediné, co by nám mohlo teorii rozbít, jsou tedy hrany s prázdným slovem. Ty v praxi bývají často užitečné, ovšem ukážeme si, že co se týče rozeznávání jazyků, jsou ekvivalentní.

Věta Nechť 𝒜︀ je konečný automat s ε-přechody, tedy může mít také hrany ve tvaru p→εq, které ze vstupu nic nesežerou. Potom existuje ekvivalentní konečný automat bez ε-přechodů.
Důkaz Nejprve v grafu provedeme tranzitivní uzávěr všech ε-přechodů, tedy pokud je nějaký stav p dosažitelný z q po ε-přechodech, potom přidáme přechod q→εp (pokud tam už není). K tomu lze použít Roy-Warshallův algoritmus z teorie grafů. Tím získáme nový automat 𝒜︀′. Zjevně L(𝒜︀)=L(𝒜︀′). Nyní vytvoříme nový automat ℬ tak, že okopírujeme všechny neepsilonové přechody z 𝒜︀′ a navíc pokud v 𝒜︀′ je p→aq→εr, potom přihodíme p→ar. Navíc do množiny počátečních stavů přidáme stavy, do kterých vede ε-přechod z počátečního stavu. Díky tranzitivní uzavřenosti 𝒜︀′ to stačí udělat jednou a platí L(𝒜︀′)=L(ℬ).
Příklad TBD: překreslit z fotky
Poznámka V důkazu jsme použili takzvaný dopředný uzávěr, který změnil množinu počátečních stavů, ale nezměnil množinu koncových stavů. Taky by se analogicky dal udělat zpětný uzávěr, tedy u konvigurace tvaru p→εq→ar bychom přihodili hranu p→ar, počáteční stavy nechali a navíc označili jako koncové ty stavy, z nichž vede ε-přechod do koncového stavu. Tím může vzniknout jiný automat než při dopředném přechodu.
Příklad Pokud bychom u předchozího příkladu použili zpětný přechod, vznikl by následující automat: TBD: překreslit z fotky
Definice Podřetězec slova w∈Σ* je vybraná posloupnost (s ostře rostoucími indexy) písmen z w.
Příklad Slovo 𝖻𝖻𝖺𝖺 je podřetězec slova 𝖺𝖻̲𝖺𝖺𝖻̲𝖺̲𝖻𝖺̲.
Věta uzavřenost rozeznávaných jazyků na podřetězce Množina podřetězců slov rozeznávaného jazyka je rozeznávaný jazyk.
Důkaz Vezmeme automat (Q,Σ,ES,I,F), kde
E∪{(p,ε,q)|∃a∈S:(p,a,q)∈E}.
Pokud se nám nelíbí ε-přechody, tak se jich následně můžeme zbavit standardním postupem.

Regulární jazyky

Definice Regulární operace s jazyky jsou sjednocení, zřetězení a iterace.
Definice Třída regulárních jazyků nad Σ je nejmenší množina M taková, že
Definice Regulární výraz nad abecedou Σ je výraz získaný induktivně z písmen abecedy Σ a symbolů 0,1,+,⋅,*,(,) takový, že Množinu regulárních jazyků značíme RegΣ*.
Definice Jazyk popsaný regulárním výrazem α je jazyk [α] definovaný jako
Poznámka Možná působí zbytečně, že si zavádíme nový způsob, jak značit jazyky, když už máme normální matematické značení. Smysl je v tom, že několik různých regulárních výrazů může značit stejný regulární jazyk, například [1⋅𝖺]=[0+𝖺]=[𝖺]={𝖺}. Při programování je často důležité si tento rozdíl uvědomit.
Věta Jazyk je regulární, právě když je popsaný nějakým regulárním výrazem.
Důkaz Kouknu a vidím.
Definice Konečný automat je standardní, pokud má jen jeden počáteční stav a do toho nevede žádný přechod.
Poznámka Jakýkoli automat můžeme snadno standardizovat tím, že přidáme počáteční stav a uděláme z něj ε-přechody do všech původních počátečních stavů. Poté musíme použít zpětný uzávěr, protože dopředný by nám to rozbil.
Definice Konečný automat je normální, pokud je standardní a navíc má jen jeden koncový stav a z toho nevede žádný přechod.
Poznámka Analogicky můžeme libovolný automat normalizovat.
Věta Kleeneova Jazyk je rozeznávaný konečným automatem, právě když je regulární. Jinými slovy, RecΣ*=RegΣ*.
Důkaz
(⇐)
Již umíme rozeznat jazyky [0]=∅, [1]={ε} a [a]={a}. Také jsme dokázali uzavřenost na sjednocení, takže pro jazyky [α],[β] umíme rozeznat [α+β]=[α]∪[β]. Stačí dokázat uzavřenost na zřetězení a iteraci. Automat pro zřetězení sestrojíme tak, že všechny koncové stavy prvního automatu propojíme ε-hranami se všemi počátečními stavy druhého automatu. V praxi se používají standardní automaty, aby to bylo jednodušší. Poté je lepší použít zpětný uzávěr, aby byl vzniklý automat pořád standardní. Pro uzavření na iteraci vezmeme standardní automat, z koncových stavů uděláme ε-hrany do počátečního, označíme ho jako jediný koncový a provedeme zpětný uzávěr. Výsledný automat bude opět standardní, protože zpětný uzávěr popřesouvá hrany zpátky tak, aby nevedly do počátečního stavu.
(⇒)
Existuje několik algoritmů, které pro daný automat dokážou nejít regulární výraz. Jedním je MNY algoritmus (McNaughton, Yamada), který je modifikací Floydova-Warshallova algoritmu z teorie grafů. My si ukážeme BMC algoritmus (Brzozowsky, McClusky). Trochu si rozšíříme definici automatu, aby přechody mohly být ohodnocené i jazyky. Mějme konečný automat 𝒜︀. Začneme tím, že ho znormalizujeme, čímž vznikne automat 𝒜︀′. Nyní provedeme n≔#Q kroků, kde v každém eliminujeme jeden stav. Nechť pi→Kiq,i∈k^ jsou přechody vedoucí do stavu q, q→Ljrj,j∈l^ jsou přechody vedoucí z něj a q→Mq je případná smyčka (je-li smyček víc, můžeme je sjednotit). Označme Ni,j ohodnocení hrany z pi do qj (opět je-li víc hran, můžeme je sjednotit). Potom po odstranění stavu q nahradíme tuto hranu hranou pi→Ni,j∪KiMLjqj. Když tohle provedeme se všemi stavy kromě počátečního a koncového, dostaneme se k tomu, že celý automat je redukovaný na jeden přechod. Ohodnocení tohoto přechodu vzniklo z písmen operacemi sjednocení a zřetězení, takže ho jistě dokážeme vyjádřit jako regulární výraz a ten bude popisovat jazyk rozeznávaný původním automatem.
Definice Nechť 𝒜︀ je konečný automat. Budoucnost stavu p∈Q je Lp≔{w∈Σ*|∃t∈F:p→wt}.
Poznámka
L(𝒜︀)=⋃i∈ILi.
Poznámka w∈Lp, právě když w=ε,p∈F nebo w=av,a∈Σ,v∈Σ*,p→aq,v∈Lq.
Poznámka Můžeme si vyjádřit:
Lp=⋃q∈QEp,qLq+δp,F,
kde Ep,q≔⋃{L|p→Lq} a δp,F≔{ε|p∈F}. S trochou halucinogenů vidíme, že tohle je soustava lineárních rovnic, kde Lp jsou proměnné.
Lemma Ardenovo Nechť K,L⊂Σ*,ε∉K. Potom K*L je jediným řešením rovnice X=KX∪L.
Důkaz Že je to řešení, dokážeme snadno. Nechť P⊂Σ* je nějaké jiné řešení, tedy P=KP∪L. Z toho plyne KP⊂P a L⊂P. Vynásobením druhé nerovnosti zleva K dostaneme KL⊂KP⊂P. Dalším vynásobením dostaneme K2L⊂KP⊂P. Opakováním dostaneme KnL⊂P pro všechna n∈ℕ0, tedy i K*L⊂P. Předpokládejme pro spor, že K*L⊊P, tedy existuje f∈P∖K*L. Vezměme nejkratší takové f. Jelikož P=KP∪L, f∈P a f∉L, musí být f∈KP, tedy f=gh,g∈K,h∈P. Speciálně g≠ε, tedy |h|<|f|, tekže podle předpokladu minimality f je h∈K*L. Potom ale i f∈K*L, což je spor.
Poznámka Ardenovo lemma můžeme využít k řešení předtím zmíněné lineární rovnice, což je další způsob, jak z automatu získat regulární výraz.

Deterministické konečné automaty

Definice Nechť 𝒜︀ je konečný automat. Přechodová funkce δ:Q×Σ*→𝒫︀(Q) je
δ(p,w)≔{q∈Q|p→wq}.
Definice Automat 𝒜︀ je deterministický, pokud |I|=1 a ∀p∈Q,a∈Σ:|δ(p,a)|≤1.
Věta Ke každému konečnému automatu 𝒜︀ existuje ekvivalentní deterministický automat 𝒟︀.
Důkaz Vezmeme si Q𝒟︀≔𝒫︀(Q), I𝒟︀≔{I}, F𝒟︀≔{U⊂Q|U∩F≠∅} a
E𝒟︀≔{P→aQ|Q=⋃p∈Pδ(p,a)}.
Potom
w∈L(𝒜︀)⟺∃i∈I:δ(i,w)∩F≠∅⟺δ𝒟︀(I,w)∩F≠∅⟺δ𝒟︀(I,w)∈F𝒟︀⟺w∈L(𝒟︀).
Definice Užitečnou část 𝒟︀ značíme 𝒜︀det.
Poznámka Při praktickém použití této konstrukce nevytvoříme celou potenční množinu hned, ale budeme ji vytvářet postupně podle toho, kam se dokážeme dostat. I tak ale může počet stavů vzrůst exponenciálně.
Definice Nechť L je jazyk. Potom označme L¯≔Σ*∖L.
Věta Nechť L∈RecΣ*. Potom L¯∈RecΣ*.
Důkaz Nechť 𝒜︀ je deterministický úplný automat pro jazyk L. Snadno dokážeme, že pro 𝒜︀¯≔(Q,Σ,δ,I,Q∖F) je L(𝒜︀¯)=L¯.
Věta Ekvivalence automatů je rozhodnutelná.
Důkaz Nechť L1,L2 jsou konečné automaty. Z předchozích tvrzení dokážeme sestrojit automat pro jazyk L1▵L2. U toho stačí ověřit, jestli rozeznává nějaké slovo, což půjde pomocí prohledání grafu.
Definice Nechť Σ,Δ jsou abecedy. Morfismus je zobrazení φ:Σ*→Δ* takové, že ∀u,v∈Σ*:φ(uv)=φ(u)φ(v).
Věta Nechť φ:Σ*→Δ* je morfismus. Potom φ(ε)=ε.
Důkaz φ(ε)=φ(εε)=φ(ε)φ(ε).
Věta Nechť φ:Σ*→Δ* je morfismus a L∈RecΣ*. Potom φ(L)∈RecΔ*.
Důkaz V automatu každou hranu p→aq nahradíme p→φ(a)q.
Poznámka Vopáčná implikace neplatí. Nechť L≔{𝖺n𝖻n|n≥0} a φ(w)≔𝖼|w|. Potom L∉Rec{𝖺,𝖻}*, ale φ(L)={𝖼n|nmod2=0}∈Rec{𝖼}*.
Věta Nechť φ:Σ*→Δ* je morfismus a L∈RecΔ*. Potom φ−1(L)∈RecΣ*.
Důkaz Vezměme deterministický konečný automat pro L. Přechody v novém automatu definujeme pomocí přechodové funkce
δφ−1(p,a)≔δ(p,φ(a)).
Indukcí snadno dokážeme, že ∀w∈Σ*:δφ−1(p,w)=δ(p,φ(w)). Z toho již plyne tvrzení věty.
Příklad Mějme morfismus φ:{0,1}*→{𝖺,𝖻}*,φ(0)≔𝖺𝖻,φ(1)≔ε a jazyk L≔{𝖺𝖻𝖺𝖻,𝖻𝖺𝖻𝖺}.

TBD: dokreslit obrázek

Když z výsledného automatu odstraníme zbytečné vrcholy, vidíme, že rozeznává jazyk φ−1(L)=[1*01*01*].
Definice Stavy p,q v deterministickém automatu jsou ekvivalentní, pokud ∀x∈Σ*:δ(p,x)∈F⟺δ(q,x)∈F neboli Lp=Lq.
Věta Ekvivalence stavů v deterministickém automatu je ekvivalence.
Důkaz Triviální.
Definice Mějme deterministický automat 𝒜︀. Potom definujeme redukovaný automat 𝒜︀/≡, jehož stavy jsou třídy ekvivalence stavů 𝒜︀ a přechodová funkce je δM([p],a)≔δ(p,a).
Důkaz správnosti definice Chceme dokázat, že je-li p≡q, potom δ(p,a)≡δ(q,a). Pro y∈Σ* máme
δ(δ(p,a),y)∈F⟺δ(p,ay)∈F⟺δ(q,ay)∈F⟺δ(δ(q,a),y)∈F.
Lemma Nechť 𝒜︀ je deterministický automat a p∈Q. Potom p∈F⟺[p]∈F/≡.
(⇒)
Plyne přímo z definice.
(⇐)
Stačí v definici ekvivalence zvolit x≔ε.
Lemma Nechť 𝒜︀ je deterministický automat a x∈Σ*,p∈Q. Potom δM([p],x)=[δ(p,x)].
Důkaz Indukcí. Pro x=ε je δM([p],ε)=[p]=[δ(p,ε)]. Platí-li tvrzení pro w∈Σ* a přidáme písmeno a∈Σ, potom
δM([p],wa)=δM(δM([p],w),a)=IPδM([δ(p,w)],a)=[δ(δ(p,w),a)]=[δ(p,wa)].
Věta Nechť 𝒜︀ je deterministický automat. Potom L(𝒜︀/≡)=L(𝒜︀).
Důkaz Pro x∈Σ* máme
x∈L(A/≡)⟺δM([i],x)∈F/≡⟺lemma[δ(i,x)]∈F/≡⟺lemmaδ(i,x)∈F⟺x∈L(𝒜︀).
Poznámka Tato redukce je v určitém smyslu nejlepší způsob, jak snížit počet stavů v deterministickém automatu tak, aby byl pořád deterministický.
Algoritmus Mooreův pro minimalizaci automatu Vezměme deterministický automat 𝒜︀. Definujeme posloupnost rozkladů Q, (Qi)i=0l. Vezmeme Q0≔{F,Q∖F}. Poté vytvoříme Qk+1 jako zjemnění Qk, kde pro p≡q(modQk) vezmeme
p≡q(modQk+1)⟺∀a∈Σ:δ(p,a)≡δ(q,a)(modQk).
Toto opakujeme, až bude Ql+1=Ql.
Důkaz Dokážeme, že tím vznikne stejný redukovaný automat, jako je popsaný výše, tedy ∀p,q∈Q:p≡q(modQl)⟺Lp=Lq. Předpokládejme pro spor, že tomu pro nějaká p,q tak není. Vezměme nejkratší možné w∈Lp▵Lq. Nechť w=ax,a∈Σ. Definujeme-li r≔δ(p,a),s≔δ(q,a). Potom r≡s(modQl) a x∈Lp▵Lq, což je spor s minimalitou w.
Definice Automat 𝒜︀ je kodeterministický, pokud 𝒜︀𝖳 je deterministický.
Věta Determinizace kodeterministického kodosažitelného automatu pro jazyk L je minimální deterministický automat pro jazyk L.
Důkaz Ne.
Příklad Definujme automat Cn≔(ℤn,{𝖺,𝖻},E,ℤn,{0}), kde
E≔{p→𝖺p+1|p∈ℤn}∪{p→𝖻p|p∈ℤn∖{0}}.
Potom v determinizaci tohoto automatu je každý stav dosažitelný, tedy 𝒜︀det má 2n stavů.

Myhillova-Nerodeova věta

Definice Nechť L∈RecΣ* je rozeznávaný deterministickým automatem 𝒜︀. Pro x,y∈Σ* definujeme ekvivalenci x≡𝒜︀y, pokud δ(i,x)=δ(i,y).
Věta Nechť L∈RecΣ* je rozeznávaný deterministickým automatem 𝒜︀. Potom ≡𝒜︀ je pravá kongruence, tedy ∀x,y∈Σ*,a∈Σ:x≡𝒜︀y⟹xa≡𝒜︀ya.
Důkaz
δ(i,xa)=δ(δ(i,x),a)=δ(δ(i,y),a)=δ(i,ya).
Věta Nechť L∈RecΣ* je rozeznávaný deterministickým automatem 𝒜︀. Potom relace ≡𝒜︀ zjemňuje L, tedy L je sjednocení nějakých tříd ekvivalence ≡𝒜︀.
Důkaz Nechť x≡𝒜︀y. Je-li δ(i,x)=δ(i,y)∈F, potom x,y∈L, jinak x,y∉L.
Věta Nechť L∈RecΣ* je rozeznávaný deterministickým automatem 𝒜︀. Potom relace ≡𝒜︀ má konečný index (počet tříd ekvivalence).
Důkaz Každá třída ekvivalence je charakterizovaná stavem, kterých je jenom konečně mnoho.
Definice Nechť L∈RecΣ* a relace ekvivalence ≡ je pravá kongruence, zjemňuje L a má konečný index. Potom ≡ je Myhillova-Nerodeova relace pro L.
Věta Nechť ≡ je Myhillova-Nerodeova relace pro L∈Σ*. Potom existuje deterministický automat 𝒜︀ rozeznávající L takový, že ≡𝒜︀=≡.
Poznámka Myhill a Nerode dokázali tuto větu nezávisle na sobě.
Důkaz Vezměme Q≔{[x]|x∈Σ*},i≔[ε],F≔{[x]|x∈L} a definujme přechodovou funkci jako δ([x],a)=[xa]. Z pravé kongruence plyne, že definice je korektní. Ze zjemnění plyne, že x∈L⟺[x]∈F. Z konečného indexu plyne, že automat je konečný.
Definice Nechť L⊂Σ*. Definujeme ekvivalenci ≡L na Σ*, kde x≡Ly, pokud ∀z∈Σ*:xz∈L⟺yz∈L.
Věta Nechť L⊂Σ*. Potom relace ≡L je pravá kongruence a zjemňuje L. Navíc je to nejhrubší ekvivalence, která má tyto dvě vlastnosti.
Důkaz Pravá kongruence je triviální. Zjemnění je ještě triviálnější. Nechť ≡ je jiná ekvivalence splňující tyto dvě vlastnosti. Chceme dokázat, že x≡y⟹x≡Ly. Nejprve snadno dokážeme indukcí, že x≡y⟹∀z∈Σ*:xz≡yz, a z toho už to plyne.
Věta Myhillova-Nerodeova Nechť L je jazyk. Potom následující tvrzení jsou ekvivalentní:
  1. L∈RecΣ*.
  2. Existuje Myhillova-Nerodeova relace pro L.
  3. Relace ≡L má konečný index.
Důkaz
(1) ⇒ (2)
Stačí vzít relaci ≡𝒜︀ pro nějaký automat 𝒜︀.
(2) ⇒ (3)
≡L je nejhrubší pravá kongruence zjemňující L, takže je speciálně hrubší než naše Myhillova-Nerodeova relace, tudíž má konečný index.
(3) ⇒ (1)
Již dokázáno.

Vylepšená věta o vkládání

Definice Nechť h∈ℕ. Jazyk L⊂Σ* splňuje vlastnost 𝔈h′, pokud pro každé f=uv1⋯vhw,u,w∈Σ*,vi∈Σ+ existují 0≤j<k≤h taková, že
uv1⋯vhw∈L⟺∀n∈ℕ0:uv1⋯vj(vj+1⋯vk)nvk+1⋯vhw∈L.
Definice Nechť h∈ℕ. Jazyk L⊂Σ* splňuje vlastnost 𝔈h, pokud pro každé f=uv1⋯vhw,u,w∈Σ*,vi∈Σ+ existují 0≤j<k≤h taková, že
uv1⋯vhw∈L⟺∀n∈ℕ0:uv1⋯vjvk+1⋯vhw∈L.
Věta Parikh-Erenfeucht-Rosenberg Nechť L⊂Σ*. Potom následující tvrzení jsou ekvivalentní:
  1. L∈RecΣ*.
  2. L a L¯ mají vlastnost 𝔈h′ pro nějaké h.
  3. L a L¯ mají vlastnost 𝔈h pro nějaké h.
Důkaz
(1) ⇒ (2)
Třetí věta o vkládání a uzavřenost na doplňky.
(2) ⇒ (3)
Triviální.
(3) ⇒ (1)
Ne.

Cvičení

Cvičení Nakreslete standardní automat pro jazyk L≔[(𝖺*𝖻+𝖻𝖻*𝖺)*].
Cvičení Nakreslete deterministický automat pro jazyk L≔[(𝖺+𝖻)*𝖺𝖻𝖺].

Bezkontextové jazyky

Definice Bezkontextová gramatika je čtveřice G=(N,T,P,S), kde N je konečná množina nonterminálů, T je konečná množina terminálů, N∩T=∅, S∈N je startovní znak a P⊂N×(N∪T)* je množina produkcí. Místo (A,α)∈P píšeme A→α∈P.
Definice Nechť G je gramatika a α,β,γ∈(N∪T)*,A∈N. Definujeme relaci ⇒, kde αAβ⇒αγβ, pokud A→γ∈P. Tranzitivní uzávěr této relace značíme ⇒*.
Definice Jazyk generovaný gramatikou G je
L(G)≔{w∈T*|S⇒*w}.
Příklad Mějme gramatiku s N≔{𝖲},T≔{𝖺,𝖻},S≔𝖲,P≔{𝖲→𝖺𝖲𝖻,𝖲→ε}. Potom jazyk generovaný G je {𝖺n𝖻n|n∈ℕ}.
Příklad Mějme gramatiku s N≔{𝖲},T≔{𝖺,𝖻},S≔𝖲,P≔{𝖲→𝖺𝖲𝖺,𝖲→𝖻𝖲𝖻,𝖲→ε,𝖲→𝖺,𝖲→𝖻}. Potom jazyk generovaný G je množina všech palindromů na {𝖺,𝖻}.
Definice Derivační strom v gramatice G je vrcholově ohodnocený kořenový strom, kde:
Příklad Mějme gramatiku:
𝖲→𝖺𝖠𝖲|𝖺,𝖠→𝖲𝖻𝖠|𝖲𝖲|𝖻𝖺.
V této gramatice můžeme odvodit 𝖲⇒*𝖺𝖺𝖻𝖻𝖺𝖺 několika různými způsoby, například
𝖲⇒𝖺𝖠𝖲⇒𝖺𝖲𝖻𝖠𝖲⇒𝖺𝖺𝖻𝖠𝖲⇒𝖺𝖺𝖻𝖻𝖺𝖲⇒𝖺𝖺𝖻𝖻𝖺𝖺,
𝖲⇒𝖺𝖠𝖲⇒𝖺𝖠𝖺⇒𝖺𝖲𝖻𝖠𝖺⇒𝖺𝖲𝖻𝖻𝖺𝖺⇒𝖺𝖺𝖻𝖻𝖺𝖺.
Obě tyto derivace ale mají stejný strom: TBD: obrázek
Příklad Mějme gramatiku
𝖲→𝖠𝖲|ε,𝖠→𝖠1|0𝖠1|01.
V této gramatice můžeme odvodit 𝖲⇒*00111 dvěma různými způsoby:
𝖲⇒𝖠𝖲⇒0𝖠1𝖲⇒0𝖠11𝖲⇒00111𝖲⇒00111,
𝖲⇒𝖠𝖲⇒𝖠1𝖲⇒0𝖠11𝖲⇒00111𝖲⇒00111.
Tyto dva způsoby mají různé stromy: TBD: obrázek
Definice Gramatika je jednoznačná, pokud pro každé slovo z L(G) existuje právě jeden strom.
Definice Symbol X∈N∪T v gramatice G je užitečný, pokud existuje derivace S⇒*αXβ⇒*w∈T*, kde α,β∈(N∪T)*. Symbol, který není užitečný, je zbytečný.
Lemma Pro každou bezkontextovou gramatiku G=(N,T,P,S),L(G)≠∅ existuje ekvivalentní gramatika G′=(N′,T,P′,S) taková, že ∀A∈N′,∃w∈T*:A⇒G′*w.
Důkaz Začneme s N′←∅. Následně budeme opakovaně nastavovat
N′←N′∪{A∈N|A→(w∈(T∪N′)*)∈P}
až do doby, kdy se N′ nezmění. Poté si necháme jen pravidla používající symboly, které pořád máme:
P′≔P∩(N′×(N′∪T)*).
Lemma Pro každou bezkontextovou gramatiku G=(N,T,P,S),L(G)≠∅ existuje ekvivalentní gramatika G″=(N″,T″,P″,S) taková, že ∀X∈N″∪T″,∃α,β∈(N″∪T″)*:S⇒*αXβ.
Důkaz Začneme s N″←{S},T″←∅. Následně budeme opakovaně přidávat do N″ a T″ nonterminály a terminály vyskytující se v pravé straně nějaké produkce, která má na levé straně něco z N″. Skončíme, když se N″ nezmění. Opět si necháme jen pravidla používající symboly, které pořád máme:
P″≔P∩(N″×(N″∪T″)*).
Příklad Mějme gramatiku
𝖲→𝖠𝖢|𝖺,𝖠→𝖺𝖻,𝖡→𝖠.
Po aplikaci prvního lemmatu nám zbyde
𝖲→𝖺,𝖠→𝖺𝖻,𝖡→𝖠.
Po následné aplikaci druhého lemmatu zůstane jen
𝖲→𝖺.
Tím, jsme se zbavili zbytečných symbolů. Kdybychom nejdřív aplikovali druhé lemma, dostali bychom
𝖲→𝖠𝖢|𝖺,𝖠→𝖺𝖻,
a po následné aplikaci prvního lemmatu
𝖲→𝖺,𝖠→𝖺𝖻.
Takže vidíme, že pravidla je nutné použít ve správněm pořadí.
Definice ε-pravidlo je pravidlo ve tvaru A→ε, kde A∈N.
Lemma Pro každou gramatiku G=(N,T,P,S) existuje gramatika G′=(N,T,P′,S) bez ε-pravidel taková, že L(G′)=L(G)∖{ε}.
Důkaz Budeme iterativně konstruovat množinu ℰ≔{A∈N|A⇒*ε}. Začneme s ℰ←{A∈N|A→ε∈P}. Potom budeme iterativně nastavovat
ℰ←ℰ∪{B∈N|B→(α∈ℰ+)∈P}.
Následně vytvoříme množinu P′ tak, že pro každé pravidlo A→X1⋯Xk∈P přidáme pravidla A→Y1⋯Yk taková, že
  • je-li Xi∉ℰ, potom Yi=Xi,
  • je-li Xi∈ℰ, potom Yi∈{Xi,ε},
  • Y1⋯Yk≠ε.
Příklad Mějme gramatiku
S→𝖺𝖻|𝖠𝖲|𝖺,B→𝖠𝖡|ε,A→𝖡𝖡|𝖲|𝖻.
Pro tuto gramatiku je 𝓔={𝖡,𝖠}. Z toho vytvoříme novou gramatiku
S→𝖺|𝖺𝖻|𝖠𝖲|𝖲,B→𝖠𝖡|𝖠|𝖡,A→𝖡𝖡|𝖻|𝖲|𝖻.
Definice Jednotkové pravidlo je pravidlo ve tvaru A→B, kde A,B∈N.
Lemma Pro každou gramatiku G=(N,T,P,S) existuje gramatika G′=(N′,T′,P′,S) bez jednotkových pravidel taková, že L(G′)=L(G)∖{ε}.
Důkaz Nejprve se pomocí předchozích tří lemmat zbavíme zbytečných symbolů a ε-pravidel. Poté do P′ dáme všechna pravidla ve tvaru A→α, kde A,B∈N,α∈(T∪N)(T∪N)+, A⇒*B a B→α∈P. Díky neexistenci ε-pravidel to je obyčejné prohledávání grafu.
Příklad Budeme-li pokračovat v příkladu z předchozího lemmatu, máme 𝖡⇒*𝖠,𝖠⇒*𝖡,𝖠⇒*𝖲, takže vzniklá gramatika bude
𝖲→𝖺|𝖺𝖡|𝖠𝖲,𝖡→𝖠𝖡|𝖡𝖡|𝖻,𝖠→𝖡𝖡|𝖠𝖡|𝖺|𝖺𝖡|𝖠𝖲|𝖻.
Definice Gramatika G je v Chomského normální formě (CNF), pokud všechna pravidla jsou tvaru A→BC nebo A→a, kde A,B,C∈N,a∈T.
Věta Pro každou gramatiku G exisuje CNF gramatika G′ taková, že L(G′)=L(G)∖{ε}.
Důkaz Pomocí předchozích lemmat se zbavíme zbytečných symbolů, ε-pravidel a jednotkových pravidel. Potom pro každé a∈T na pravé straně nějakého pravidla A→α,|α|≥2 zavedeme nový nonterminál Ca, přidáme pravidlo Ca→a a ve všech pravých stranách délky alespoň 2 nahradíme a na Ca. Tím se dostaneme k tomu, že všechny pravé strany jsou buď jeden terminál, nebo dva a více nonterminálů. Zbývá pro každé pravidlo tvaru A→B1⋯Bm,m≥3 zavést nové nonterminály D1,…,Dm−2 a pravidlo nahradíme pravidly A→B1D1,D1→B2D2,…,Dm−3→Bm−2Dm−2,Dm−2→Bm−2Bm.
Příklad Začněme (již po aplikaci lemmat) s gramatikou
𝖲→𝖻𝖠|𝖺𝖡,𝖠→𝖻𝖠𝖠|𝖺𝖲|𝖺,𝖡→𝖺𝖡𝖡|𝖻𝖲|𝖻.
Po prvním kroku z toho vznikne
𝖢𝖻→𝖻,𝖢𝖺→𝖺,𝖲→𝖢𝖻𝖠|𝖢𝖺𝖡,𝖠→𝖢𝖻𝖠𝖠|𝖢𝖺𝖲|𝖺,𝖡→𝖢𝖺𝖡𝖡|𝖢𝖻𝖲|𝖻.
Po druhém kroku z toho vznikne
𝖢𝖻→𝖻,𝖢𝖺→𝖺,𝖲→𝖢𝖻𝖠|𝖢𝖺𝖡,𝖠→𝖢𝖻𝖣1|𝖢𝖺𝖲|𝖺,𝖣1→𝖠𝖠,𝖡→𝖢𝖺𝖣2|𝖢𝖻𝖲|𝖻,𝖣2→𝖡𝖡.
Poznámka Existuje i Greibachové normální forma, která je ještě restriktivnější: každé pravidlo je ve tvaru A→aα, kde A∈N,a∈T,α∈N*.
Lemma Neobsahuje-li derivační strom gramatiky G v Chomského normální formě pro slovo u∈L(G) cestu z kořene delší než k, potom |u|≤2k−1.
Důkaz Triviálně indukcí.
Věta o vkládání pro bezkontextové jazyky Nechť L je bezkontextový jazyk. Potom existuje N∈ℕ takové, že pro všechna w∈L,|w|≥N existuje rozložení w=uv1xv2y, kde |v1xv2|≤N,|v1v2|≥1 a pro všechna n∈ℕ0 je uv1nxv2ny∈L.
Příklad Pomocí věty o vkládání můžeme snadno dokázat, že L≔{𝖺n𝖻n𝖼n|n∈ℕ0} není bezkontextový jazyk.
Důkaz Nechť G je gramatika v Chomského normální formě generující L∖{ε} a l je počet nonterminálů (jejichž množinu tentokrát nebudeme značit N, protože se to písmeno používá ve větě pro něco jiného). Zvolme N≔2l. Máme-li slovo délky alespoň N, potom podle lemmatu jeho derivační strom má výšku alespoň l+1, takže cesta z kořene do nějakého terminálu obsahuje alespoň l+1 nonterminálů. Podívejme se na posledních l+1 nonterminálových vrcholů této cesty. Podle 🐦 holubníkového principu 🐦 mají dva vrcholy z1,z2 stejné označení A, přičemž z1 je blíž ke kořeni. Vezměme za x slovo generované vrcholem z2, za v1,v2 zbylé kusy slova generovaného vrcholem z1 a za u,y zbylé kusy celého původního slova. Slovo pod vrcholem z1 je v1xv2, takže podle lemmatu je |v1xv2|≤2l=N. Jelikož z2 je vlastní podstrom z1, máme |v1v2|≥1. Zbývá ověřit ⛽ pumpovací podmínku ⛽. Z konstrukce je vidět, že S⇒*uAy,A⇒*v1Av2,A⇒*x. Pokud aplikujeme první derivaci, potom n-krát druhou derivaci a poté třetí derivaci, dostaneme slovo uv1nxv2ny.
Věta Třída bezkontextových jazyků je uzavřená na sjednocení, zřetězení a iteraci.
Důkaz Nechť K=L(GK),L=L(GL), přičemž bez újmy na obecnosti NK∩NL=∅. Pro sjednocení vytvoříme nový startovní symbol S∉NK∪NL a vezmeme gramatiku
GK∪L≔(NK∪NL∪{S},TK∪TL,PK∪PL∪{S→SL|SK},S).
Analogicky pro zřetězení vezmeme gramatiku
GKL≔(NK∪NL∪{S},TK∪TL,PK∪PL∪{S→SLSK},S).
A pro iteraci vezmeme gramatiku
GK*≔(NK∪{S},TK,PK∪{S→SKS,S→ε},S).
Důsledek Každý regulární jazyk je bezkontextový.
Věta Třída bezkontextových jazyků není uzavřená na průnik.
Důkaz Vezměme L≔{𝖺n𝖻n𝖼m|n,m∈ℕ0},K≔{𝖺m𝖻n𝖼n|n,m∈ℕ0}. Tyto jazyky jsou bezkontextové, protože jde o zřetězení dvou bezkontextových jazyků, ale o jejich průniku už jsme si dokázali, že není bezkontextový.
Důsledek Třída bezkontextových jazyků není uzavřená na doplněk.
Důkaz Kdyby pro spor byla, mohli bychom vyjádřit L∩K=L¯∪K¯¯, takže bychom měli uzavřenost i na průnik.
Věta Je-li L bezkontextový jazyk a K regulární jazyk, potom L∩K je bezkontextový jazyk.
Důkaz Až později.
Příklad Pomocí této věty můžeme dokázat, že jazyk čtverců L≔{w2|w∈{𝖺,𝖻}*} není bezkontextový. Vezměme K≔[𝖺+𝖻+𝖺+𝖻+]. Kdyby byl L bezkontextový, potom by byl bezkontextový i L∩K={𝖺n𝖻n𝖺n𝖻n|n∈ℕ}. O tom pomocí věty o vkládání můžeme dokázat, že není.

Zásobníkové automaty

Definice Zásobníkový automat je 𝒜︀=(Q,Σ,Γ,δ,q0,z0,F), kde Q je konečná množina stavů, Σ je vstupní abeceda, Γ je zásobníková abeceda, q0∈Q je počáteční stav, z0∈Γ je symbol na dně zásobníku, F⊂Q je množina koncových stavů a δ:Q×(Σ∪{ε})×Γ→𝒫︀(Q×Γ*) je přechodová funkce.
Poznámka Výpočet v zásobníkovém automatu probíhá tak, že má zásobník, na který si ukládá symboly z množiny Γ. Na počátku zásobník obsahuje symbol z0. V každém krohu přečte ze vstupu písmeno a, odebere z vrchu zásobníku symbol z. Je-li p aktuální stav a (q,γ)≔δ(p,a,z), potom přejde na stav q a na zásobník vloží γ. Píšeme p→a,z|γq.
Definice Konfigurace zásobníkového automatu je (q,w,β), kde q∈Q je aktuální stav, w∈Σ* je zbývající část vstupu a β∈Γ* je zásobník. Je-li (p,γ)=δ(q,a,z), potom existuje přechod mezi konfiguracemi (q,aw,βz)⇒𝒜︀(p,w,βγ). Tranzitivní uzávěr ⇒𝒜︀ značíme ⇒𝒜︀*.
Definice Nechť 𝒜︀ je zásobníkový automat. Potom jazyk rozeznávaný koncovým stavem je
LS(𝒜︀)≔{w∈Σ*|∃t∈F,β∈Γ*:(q0,w,z0)⇒𝒜︀*(t,ε,β)}.
Definice Nechť 𝒜︀ je zásobníkový automat. Potom jazyk rozeznávaný prázdným zásobníkem je
LZ(𝒜︀)≔{w∈Σ*|∃p∈Q:(q0,w,z0)⇒𝒜︀*(p,ε,ε)}.
Příklad Mějme jazyk
L≔{w𝖼w←|w∈{𝖺,𝖻}*}.
K rozeznání tohoto jazyka koncovým stavem můžeme použít zásobníkový automat:
Q≔{𝘲0,𝘲1,𝘲2},
Σ≔{𝖺,𝖻,𝖼},
Γ≔{𝗓0,𝖺,𝖻},
δ(𝘲0,𝖺,z)≔{(𝘲0,z𝖺)},
δ(𝘲0,𝖻,z)≔{(𝘲0,z𝖻)},
δ(𝘲0,𝖼,z)≔{(𝘲1,z)},
δ(𝘲1,𝖺,𝖺)≔{(𝘲1,ε)},
δ(𝘲1,𝖻,𝖻)≔{(𝘲1,ε)},
δ(𝘲1,ε,𝗓0)≔{(q2,𝗓0)},
q0≔𝘲0,
z0≔𝗓0,
F≔{𝘲2}.
Kdybychom se vykašlali na koncový stav 𝘲2 a místo toho přidali pravidlo δ(𝘲1,ε,𝗓0)≔{(𝘲1,ε)}, jazyk by byl rozeznávaný prázdným zásobníkem.
Věta Nechť 𝒜︀ je zásobníkový automat. Potom existuje zásobníkový automat 𝒜︀′ takový, že LZ(𝒜︀′)=LS(𝒜︀).
Důkaz Přidáme nový dnový symbol x0, dva nové stavy p0,pε a přechody p0→ε,x0|x0z0q0 a t→ε,z|εpε pro každé t∈F∪{pε},z∈Γ∪{x0}. Jelikož pravidla vedoucí do pε jsou jediná, která umí smazat symbol x0, zaručí nám to, že zásobník se nevyprázdní jinak než skončením v koncovém stavu.
Věta Nechť 𝒜︀ je zásobníkový automat. Potom existuje zásobníkový automat 𝒜︀″ takový, že LS(𝒜︀″)=LZ(𝒜︀).
Důkaz Přidáme nový dnový symbol x0, dva nové stavy p0,pK a přechody p0→ε,x0|x0z0q0 a q→ε,x0|εpK pro každé q∈Q. Jako množinu koncových stavů si vezmeme {pK}.
Věta Jazyk L je bezkontextový, právě když existuje zásobníkový automat 𝒜︀ takový, že L=LZ(𝒜︀).
Důkaz Dokážeme pouze implikaci doprava, protože u té doleva je důkaz velmi hnusný a technický. Náš automat bude jakýmsi způsobem simulovat odvozování v gramatice. Stačí nám jeden stav q. Předpokládejme bez újmy za obecnosti, že jde o levé odvozování, tedy vždy nahradíme nejlevější nonterminál. Libovolnou větnou formu během odvozování dokážeme zapsat jako xAα, kde x∈T*,A∈N,α∈(N∪T)*. Část x bude odpovídat již přečtenému slovu a část Aα zásobníku. Každé odvození bude odpovídat dvěma krokům automatu. V prvním kroku si automat vybere z přechodů odpovídajících pravidlům, kde pravidlu A→β přiřadíme přechod q→ε,A|γ←q. TBD
Příklad Máme li gramatiku
𝖲→0𝖲1|𝖠,𝖠→1𝖠0|S|ε,
uděláme z ní automat
δ(𝘲,ε,𝖲)≔{(𝘲,1𝖲0),(𝘲,𝖠)},δ(𝘲,ε,𝖠)≔{(𝘲,0𝖠1),(𝘲,𝖲),(𝘲,ε)},δ(𝘲,0,0)≔{(𝘲,ε)},δ(𝘲,1,1)≔{(𝘲,ε)}.
Teď mějme slovo w≔011001 vzniklé odvozením
𝖲⇒0𝖲1⇒0𝖠1⇒01𝖠01⇒011𝖠001⇒011011.
Odpovídající posllupnost v automatu bude
(𝗊,011001,𝖲)⇒(𝗊,011001,1𝖲0)⇒(𝗊,11001,1𝖲)⇒(𝗊,11001,1𝖠)⇒(𝗊,11001,10𝖠1)⇒(𝗊,1001,10𝖠)⇒(𝗊,1001,100𝖠1)⇒(𝗊,001,100𝖠)⇒(𝗊,001,100)⇒(𝗊,01,10)⇒(𝗊,1,1)⇒(𝗊,ε,ε).

Cvičení na bezkontextové gramatiky a zásobníkové automaty

Cvičení Najděte bezkontextovou gramatiku generující jazyk
L≔{𝖺i𝖻j𝖼k|i≠j∨j≠k}.
Řešení
𝖲→𝖲𝖠𝖢|𝖠𝖲𝖢,𝖠→𝖺𝖠|𝖺,𝖡→𝖻𝖡|𝖻,𝖢→𝖼𝖢|𝖼,𝖲𝖠→𝖺𝖲𝖠𝖻|𝖠|𝖡,𝖲𝖢→𝖻𝖲𝖢𝖼|𝖡|𝖢.
Cvičení Najděte bezkontextovou gramatiku generující jazyk nečtverců
L≔{w∈{𝖺,𝖻}*|∄u∈{𝖺,𝖻}*:w=uu}.
Poznámka Již jsme si dokázali, že jazyk čtverců, jehož je tento jazyk doplňkem, není bezkontextový.
Řešení
𝖲→𝖤|𝖮,𝖯→𝖺|𝖻,𝖮→𝖯𝖯𝖮|𝖯,𝖤→𝖤𝖺𝖤𝖻|𝖤𝖻𝖤𝖺,𝖤𝖺→𝖯𝖤𝖺𝖯|𝖺,𝖤𝖻→𝖯𝖤𝖻𝖯|𝖻.
Cvičení Odstraňte zbytečné symboly z gramatiky
S→𝖠𝖢|𝖢𝖠,𝖠→𝖺,𝖡→𝖡𝖢|𝖠𝖡|𝖻,𝖢→𝖺𝖡|𝖻.
ŘešeníŽádný symbol není zbytečný.
Cvičení Odstraňte zbytečné symboly z gramatiky
𝖲→𝖠𝖢|𝖢𝖠,𝖠→𝖺,𝖡→𝖡𝖢|𝖠𝖡,𝖢→𝖺𝖡|𝖻,𝖣→𝖠𝖺.
Řešení
𝖲→𝖠𝖢|𝖢𝖠,𝖠→𝖺,𝖢→𝖻.
Cvičení Z gramatiky
𝖲→𝖠𝖲𝖡|ε,𝖠→𝖺𝖠𝖲|𝖺,𝖡→𝖲𝖻𝖲|𝖠|𝖻𝖻
eliminujte ε-pravidla a jednotková pravidla a převeďte ji do Chomského normální formy.
ŘešeníPo eliminaci ε-pravidel:
𝖲→𝖠𝖲𝖡|𝖠𝖡,𝖠→𝖺𝖠𝖲|𝖺𝖠|𝖺,𝖡→𝖲𝖻𝖲|𝖲𝖻|𝖻𝖲|𝖻|𝖠|𝖻𝖻.
Po eliminaci jednotkových pravidel:
𝖲→𝖠𝖲𝖡|𝖠𝖡,𝖠→𝖺𝖠𝖲|𝖺𝖠|𝖺,𝖡→𝖲𝖻𝖲|𝖲𝖻|𝖻𝖲|𝖻|𝖺𝖠𝖲|𝖺𝖠|𝖺|𝖻𝖻.
Chomského normální forma:
𝖲→𝖣1𝖡|𝖠𝖡,𝖠→𝖯𝖺𝖣1|𝖯𝖺𝖠|𝖺,𝖡→𝖣2𝖲|𝖲𝖯𝖻|𝖯𝖻𝖲|𝖻|𝖯𝖺𝖣1|𝖯𝖺𝖠|𝖺|𝖯𝖻𝖯𝖻,𝖯𝖺→𝖺,𝖯𝖻→𝖻,𝖣1→𝖠𝖲,𝖣2→𝖲𝖯𝖻.
Cvičení Najděte zásobníkový automat 𝒜︀ takový, že
LS(𝒜︀)={z∈{0,1}*|z=uv,|u|1>|u|0}.
Řešení
Q≔{𝘲0,𝘲1},
F≔{𝘲1},
Γ≔{#,0},
z0≔#,
δ(𝘲0,0,#)≔(𝘲0,#0),δ(𝘲0,0,0)≔(𝘲0,00),δ(𝘲0,1,0)≔(𝘲0,ε),δ(𝘲0,1,#)≔(𝘲1,#),δ(𝘲1,0,#)≔(𝘲1,#),δ(𝘲1,1,#)≔(𝘲1,#).
Cvičení Najděte zásobníkový automat 𝒜︀ takový, že
LS(𝒜︀)={𝖺i𝖻j𝖼k|i=j∨j=k}.

Konečné překladače

Tuto část přednášel Prof. Jacques Sakarovitch a je dostupná na separátní stránce.