Adamátor Zápisky Hlášky

Jazyky, automaty a vyčíslitelnost

Tyto zápisky jsou z přednášek Ing. Petra Ambrože, Ph.D.

Děkuji Veronice Hendrychové za opravu četných překlepů.

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. %3 _p p p _p->p r_ p->p a + b q q p->q a r r q->r b r->r_ r->r a + b
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. Potom automat pro průnik vypadá takto: %17 _pp pp pp _pp->pp rr_ pp:n->pp a + b qp qp pp->qp b pq pq pp->pq a rp rp qp->rp a qq qq rq rq qp->rq a rp:s->rp a + b rp->rq a pr pr pq->pr b qr qr pq->qr b rr rr rq->rr b pr:n->pr a + b pr->qr b qr->rr a rr->rr_ rr:s->rr a + b Všimněme si, že stav qq je zbytečný.
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 L 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(ℬ).
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 konfigurace 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 Mějme tento automat: %59 _1 1 _1->1 3_ 2 1->2 ε 3 3->3_ 2->3 ε 5 2->5 e 4 4->1 a 4->5 b 5->1 ε 5->2 d 5->4 c Tranzitivní uzávěr vypadá takto: %81 _1 1 _1->1 3_ 3 1->3 ε 2 1->2 ε 3->3_ 2->3 ε 5 2->5 e 4 4->1 a 4->5 b 5->1 ε 5->1 ε 5->3 ε 5->2 d 5->4 c Použitím dopředného uzávěru dostaneme: %109 _1 1 _1->1 _2 2 _2->2 _3 3 _3->3 3_ 2->1 e 2->2 e 2->3 e 5 2->5 e 3->3_ 4 4->1 a + b 4->2 a + b 4->3 a + b 4->5 b 5->2 d 5->3 d 5->4 c Pokud bychom použili zpětný uzávěr, vznikl by následující automat: TBD
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
ES≔E∪{(p,ε,q)|∃a∈Σ:(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≔{𝖺𝖻𝖺𝖻,𝖻𝖺𝖻𝖺}. %141 _a a _a->a e_ i_ b a->b a f a->f b c b->c b d c->d a e d->e b e->e_ g f->g a h g->h b i h->i a i->i_ Podle konstrukce z důkazu dostaneme tento automat: %165 _a a _a->a e_ i_ a->a 1 b a->b c a->c 0 f a->f e e->e_ e->e 1 i i->i_ i->i 1 b->b 1 b->c c->e 0 c->c 1 d c->d d->e d->d 1 f->f 1 g f->g h f->h 0 g->g 1 g->h h->i h->h 1 Když z něj 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−1Bm.
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={𝖺m𝖻n𝖺m𝖻n|m,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 kroku 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⇒011001.
Odpovídající posloupnost 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.

Rozhodnutelnost a Turingovy stroje

Zatím jsme se věnovali problému rozhodnutí, jestli dané slovo patří do daného jazyka. Ovšem máme-li libovolný rozhodovací problém (tedy ptáme se, jestli nějaký daný vstup má danou vlastnost), můžeme ho snadno převést na „jazykový“ rozhodovací problém tím, že každý vstup zakódujeme do slova. Tedy chceme-li řešit obecné rozhodovací problémy, bez újmy na obecnosti stačí uvažovat problémy rozeznávání jazyků.
Definice neformální Nechť U je neprázdná množina. Algoritmus je postup, který s každým prvkem U dovoluje provést jednoznačnou konečnou posloupnost elementárních operací, jejíž výsledek je jednoznačně určený prvek nějaké množiny V. Semialgoritmus A je algoritmus, který vrátí výsledek v konečném počtu kroků jen pro nějakou množinu PO(A)⊂U.
Abychom tuto definici zformálnili, minimálně potřebujeme mít jasně určeno, co je elementární operace. Existuje spousta různých modelů, například pomocí rekurzivních funkcí, λ-kalkulu, … My si ukážeme model Turingových strojů
Definice Turingův stroj je 𝒜︀=(Q,Σ,Γ,δ,q0,𝙱,F), kde Q je množina stavů, Γ je pásková abeceda, B∈Γ je prázdný znak, Σ⊂Γ∖{𝙱} je vstupní abeceda, q0∈Q je počáteční stav, F je množina konečných stavů a δ:Q×Γ→Q×Γ×{𝙻,𝙿} je přechodová funkce. Jeho konfigurace je αLqαR, kde q∈Q je aktuální stav a αL,αR∈Γ* jsou části pracovní pásky, přičemž na první znak αR míří jakási hlava stroje. Na množině konfigurací definujeme relaci ⇒ tak, že Tranzitivní uzávěr relace ⇒ značíme ⇒*. Jazyk rozeznávaný Turingovým strojem je L(𝒜︀)≔{w∈Σ*|q0w⇒*α1pα2,α1,α2∈Γ*,p∈F}.
Poznámka Všimněme si, že na rozdíl od automatů může být výpočet v Turingově stroji ukončen jen dosažením koncového stavu, nikoliv přečtením celého vstupu. To speciálně znamená, že se nemusí nikdy zastavit.
Příklad Zkusme sestavit Turingův stroj rozeznávající náš starý dobrý jazyk L={𝖺n𝖻n|a,b∈ℕ}. Myšlenka bude taková, že bude jezdit tam a zpátky a vždy smaže jedno 𝖺 ze začátku a jedno 𝖻 z prostředka. Budeme mít pět stavů: 𝘲0 je počáteční a přepíše 𝖺→𝖷, q1 jede doprava, až narazí na 𝖻, a přepíše ho na 𝖸, 𝘲2 jede doleva, až narazí na X, a škrtne 𝖺 za ním, 𝘲3 na konci zkontroluje, jestli bylo vše přepsáno, a 𝘲4 bude konečný stav. Takže volíme Q≔{𝘲0,𝘲1,𝘲2,𝘲3,𝘲4},Γ≔{𝖺,𝖻,𝖷,𝖸},F≔{𝘲4} a definujeme
δ(𝘲0,𝖺)≔(𝘲1,𝖷,𝙿),δ(𝘲0,𝖸)≔(𝘲3,𝖸,𝙿),δ(𝘲1,𝖺)≔(𝘲1,𝖺,𝙿),δ(𝘲1,𝖻)≔(𝘲2,𝖸,𝙻),δ(𝘲1,𝖸)≔(𝘲1,𝖸,𝙿),δ(𝘲2,𝖺)≔(𝘲2,𝖺,𝙻),δ(𝘲2,𝖷)≔(𝘲0,𝖷,𝙿),δ(𝘲2,𝖸)≔(𝘲2,𝖸,𝙻),δ(𝘲3,𝖸)≔(𝘲3,𝖸,𝙿),δ(𝘲3,𝙱)≔(𝘲3,𝙱,𝙿).
Slovo aabb bude rozeznáno takto: 𝘲0𝖺𝖺𝖻𝖻⇒𝖷𝘲1𝖺𝖻𝖻⇒𝖷𝖺𝘲1𝖻𝖻⇒𝖷𝘲2𝖺𝖸𝖻⇒𝘲2𝖷𝖺𝖸𝖻⇒𝖷𝘲0𝖺𝖸𝖻⇒𝖷𝖷𝘲1𝖸𝖻⇒𝖷𝖷𝖸𝘲1𝖻⇒𝖷𝖷𝘲2𝖸𝖸⇒𝖷𝘲2𝖷𝖸𝖸⇒𝖷𝖷𝘲0𝖸𝖸⇒𝖷𝖷𝖸𝘲3𝖸⇒𝖷𝖷𝖸𝖸𝘲3𝙱⇒𝖷𝖷𝖸𝖸𝙱𝘲4𝙱.
Definice Jazyk L je rekurzivně spočetný, pokud je rozeznatelný Turingovým strojem. Značíme L∈ℒRS.
Definice Turingův stroj je totální, pokud se na libovolném vstupu zastaví.
Definice Jazyk L je rekurzivní, pokud je rozeznatelný totálním Turingovým strojem. Značíme L∈ℒREK.
Definice neformální Nechť pro algoritmus A na množině U značí Au jeho výsledek pro u∈U. Funkce f:U→V je algoritmicky vyčíslitelná, pokud ∀u∈U:f(u)=Au. Částečná funkce f:(U)→V je algoritmicky parciálně vyčíslitelná, pokud existuje semialgoritmus A takový, že PO(A)=Df a ∀u∈Df:f(u)=Au.
Definice Funkce f:Σ*→Σ* je turingovsky vyčíslitelná, pokud existuje totální Turingův stroj takový, že po zastavení výpočtu se vstupem w∈Σ* zbyde na pásce právě f(w), popřípadě nějaké znaky navíc z Γ∖Σ.
Definice Částečná funkce f:(Σ*)→Σ* je turingovsky parciálně vyčíslitelná, pokud existuje Turingův stroj takový, že po zastavení výpočtu se vstupem w∈Df se zastaví a na pásce zbyde právě f(w), popřípadě nějaké znaky navíc z Γ∖Σ.
Konvence Pracujeme-li s funkcí f:ℕk→ℕ, vstup budeme kódovat pomocí unárního systému, kde části oddělujeme nulami. Tedy chceme-li spočíst f(n1,…,nk), na pásku zapíšeme 1n101n20⋯01nk.
Teze Churchova-Turingova Funkce je algoritmicky [parciálně] vyčíslitelná, právě když je turingovsky [parciálně] vyčíslitelná.
Poznámka Toto tvrzení nemůžeme nazvat větou ani domněnkou, protože pojem algoritmu není rigorózně definovaný.
Poznámka Používají se i silnější modely Turingova stroje: můžeme mít více pásek, dvourozměrnou pásku, povolit neposunutí hlavy po tranzici nebo i umožnit nedeterminismus. Dá se ukázat, že všechny tyto modely jsou ekvivalentní, co se týče výpočetní síly. Naopak ho můžeme trochu oslabit: například povolit jen jeden koncový stav nebo používat jen abecedu Γ={0,1,𝙱}.
Definice Rozhodovací problém je funkce P:Σ*→{ano,ne}. Jeho instance je w∈Σ* a odpověď je P(w).
Definice Rozhodovací problém P je rozhodnutelný, pokud existuje algoritmus, který pro každé w∈Σ* najde P(w).
Poznámka Podle Church-Turingovy teze je problém rozhodnutelný, právě když LP≔P−1({ano})∈ℒREK.
Věta Doplněk rekurzivního jazyka je rekurzivní jazyk.
Důkaz neformální Vytvoříme nový Turingův stroj, který svůj vstup nacpe do původního Turingova stroje, podívá se na odpověď a zneguje ji.
Poznámka Pro rekurzivně spočetné jazyky to nefunguje, protože u původního stroje nevíme, jestli se zastaví.
Věta Sjednocení dvou rekurzivních jazyků je rekurzivní jazyk.
Důkaz neformální Vytvoříme Turingův stroj, který pošle vstup do obou původních a podívá se, jestli alespoň jeden odpověděl ano.
Věta Sjednocení dvou rekurzivně spočetných jazyků je rekurzivně spočetný jazyk.
Důkaz neformální Podobný, akorát máme komplikaci v tom, že musíme jaksi pustit oba původní stroje najednou, aby se nestalo, že je jeden zasekne a tím zablokuje ten druhý.
Věta Je-li jazyk L i jeho doplněk rekurzivně spočetný, potom jsou rekurzivní.
Důkaz neformální Pustíme Turingovy stroje pro L,L¯ najednou a odpovíme za základě toho, který odpoví dřív.
Důsledek Pro každý jazyk L nastává právě jedna z možností:
  • L,L¯∈ℒREK.
  • L,L¯∉ℒRS.
  • L∈ℒRS∖ℒREK∧L¯∉ℒRS.
  • L¯∈ℒRS∖ℒREK∧L∉ℒRS.
Poznámka V následujících definicích budeme potřebovat nějak kódovat Turingovy stroje do posloupnosti nul a jedniček. Předpokládejme bez újmy na obecnosti, že Q={q1,…,qm},Σ={0,1},Γ={0,1,𝙱},i=q1,T={q2}. Označme P1≔0,P2≔1,P3≔𝙱,S1≔𝙻,S2≔𝙿. Potom pravidlo δ(qi,Pj)=(qk,Pl,Sm) můžeme zakódovat jako 0i10j10k10l10m. Celý Turingův stroj potom zakódujeme jako
⟨𝒜︀⟩≡111[kód prvního pravidla]11[kód druhého pravidla]11[kód třetího pravidla]11⋯11[kód posledního pravidla]111.
Potom naopak každá posloupnost bitů buď jednoznačně určuje Turingův stroj, nebo neurčuje žádný. V takovém případě ji interpretujeme jako Turingův stroj, který nepřijímá žádné slovo.
Definice Nechť (wi)i∈ℕ je posloupnost všech binárních slov v radixovém uspořádání a 𝒜︀j značí Turingův stroj, který se kóduje na wj. Uvažujme nekonečnou tabulku T{i,j}≔[wi∈ℒ(𝒜︀j)]. Potom diagonální jazyk je
Ld≔{wi∈{0,1}*|T{i,i}=0}={wi∈{0,1}*|wi∈L(𝒜︀i)}.
Věta Diagonální jazyk není rekurzivně spočetný.
Důkaz Nechť pro spor existuje Turingův stroj 𝒜︀k rozpoznávající Ld. Potom
  • je-li wk∈Ld, potom Tk,k=0∴wk∈ℒ(𝒜︀k)=Ld;
  • je-li wk∉Ld, potom Tk,k=1∴wk∈ℒ(𝒜︀k)=Ld.
Definice Univerzální jazyk je
Lu≔{⟨𝒜︀⟩w|𝒜︀je Turingův stroj přijímající slovow}.
Věta Univerzální jazyk je rekurzivně spočetný.
Důkaz neformální Sestavíme Turingův stroj, který odsimuluje zadaný Turingův stroj 𝒜︀ na daném vstupu. To můžeme udělat například pomocí tří pásek. Na první bude kód 𝒜︀, na druhé bude obsah simulované pásky a na třetí bude kód aktuálního stavu. Algoritmus bude fungovat nějak takto:
  1. Zkontrolujeme, jestli na vstupu je platný kód Turingova stroje. Pokud není, odpovíme ne.
  2. Všechno za kódem 𝒜︀ zkopírujeme na druhou pásku.
  3. Na třetí pásku umístíme nulu.
  4. Budeme simulovat jednotlivé kroky stroje 𝒜︀, kde každý krok vypadá následovně:
    1. Na třetí pásce přečteme kód aktuálního stavu.
    2. Na druhé pásce přečteme symbol pod hlavou.
    3. Na první pásce najdeme příslušné pravidlo. Pokud neexistuje, odpovíme ne.
    4. Na druhou pásku zapíšeme vzniklý symbol a posuneme její hlavu.
    5. Na třetí pásku zapíšeme nový stav.
    6. Pokud jsme se dostali do koncového stavu, odpovíme ano.
Definice Jazyk L1 je turingovsky redukovatelný na jazyk L2, pokud existuje turingovsky vyčíslitelná funkce f:Σ*→Σ* taková, že w∈L1⟺f(w)∈L2. Značíme L1≤mL2.
Poznámka Pro rozhodovací problémy P1,P2 budeme značit P1≤mP2⟺LP1≤mLP2.
Věta Nechť P1≤mP2. Potom
  1. P1∉ℒREK⟹P2∉ℒREK,
  2. P1∉ℒRS⟹P2∉ℒRS.
Důkaz Dokážeme pouze první tvrzení v obměněné implikaci, pro druhé je důkaz analogický. Nechť P2∈ℒREK, tedy existuje totální Turingův stroj 𝒜︀ rozeznávající LP2. Potom můžeme sestrojit Turingův stroj pro P1, který vezme vstup u a do 𝒜︀ hodí f(u).
Věta Halting Problem Univerzální jazyk není rekurzivní.
Důkaz Předpokládejme pro spor, že pro něj existuje totální Turingův stroj 𝒜︀. Dokážeme, že Ld¯≤mLu. Převodní algoritmus bude vypadat takto:
  1. Pro dané slovo w najdeme i takové, že w=wi (v již zavedeném radixovém uspořádání).
  2. Vezmeme Turingův stroj 𝒜︀i zakódovaný číslem i.
  3. Podíváme se, jestli 𝒜︀ přijme ⟨𝒜︀i⟩wi.
Potom 𝒜︀ se zastaví a přijme ⟨𝒜︀i⟩wi ⟺ 𝐴 přijme wi ⟺ w∈Ld¯. No a kdyby pro spor Ld¯∈ℒREK, potom také Ld∈ℒREK, což víme, že není.
Definice Definujme jazyky
LNE≔{⟨𝒜︀⟩|L(𝒜︀)≠∅},
LE≔{⟨𝒜︀⟩|L(𝒜︀)=∅}.
Věta LNE∈ℒRS.
Důkaz Vezmeme nedeterministický automat, který odsimuluje zadaný automat na všech možných vstupech.
Věta LNE∉ℒREK.
Důkaz Nechť pro spor existuje totální Turingův stroj 𝒩︀ pro LNE. Pomocí něj sestrojíme totální Turingův stroj ℬ pro Lu. Máme daný automat 𝒜︀ a vstup w a chceme zjistit, jestli w∈L(𝒜︀). Sestrojíme automat 𝒜︀w, který zamítne všechna slova kromě w a slovo w přijme, právě když ho přijme 𝒜︀. Potom stačí spustit 𝒩︀ se vstupem 𝒜︀w.
Důsledek LE∉ℒRS.
Definice Množina 𝒮︀⊂ℒRS je vlastnost rekurzivně spočetných jazyků. Vlastnost je triviální, pokud 𝒮︀=∅ nebo 𝒮︀=ℒRS.
Důsledek Riceova věta Každá netriviální vlastnost rekurzivně spočetných jazyků je nerozhodnutelná.
Problém Postův korespondenční Dostaneme dvě stejně dlouhé konečné posloupnosti slov P=(w1,…,wk),R=(x1,…,xk). Instance (P,R) má řešení, pokud existuje posloupnost indexů (i1,…,im) z k^ taková, že wi1⋯wim=xi1⋯xim.
Příklad Máme-li
P:w1=1,w2=10111,w3=10,
R:x1=111,x2=10,x3=0,
potom w2w1w1w3=101111110=x2x1x1x3, takže instance má řešení.
Příklad Máme-li
P:w1=10,w2=011,w3=101,
R:x1=101,x2=11,x3=011,
potom instance nemá řešení.
Věta Postův korespondenční problém je nerozhodnutelný.
Věta Nejednoznačnost bezkontextové gramatiky je nerozhodnutelná.
Důkaz Dokážeme, že Postův korespondenční problém se dá převést na nejednoznačnost bezkontextové gramatiky. Nechť A=(w1,…,wn),B=(x1,…,xn) jsou seznamy slov z Postova problému a a1,…,an jsou nějaká písmena nepoužívaná ve slovech. Definujme jazyky
L1≔{wi1⋯wimaim⋯ai1|m∈ℕ,i1,…,im∈n^},
L2≔{xi1⋯ximaim⋯ai1|m∈ℕ,i1,…,im∈n^}.
Vezměme gramatiku s pravidly
𝖲→𝖲A|𝖲B,𝖲A→wi𝖲Aai|wiai,𝖲B→xi𝖲Bai|xiai.
Tato gramatika generuje jazyk L1∪L2 a je nejednoznačná, právě když daná instance Postova problému má řešení.
Poznámka Pomocí jazyků L1,L2 z tohoto důkazu se také dá dokázat, že pro bezkontextové gramatiky G1,G2 jsou následující problémy nerozhodnutelné:
  • L(G1)∩L(G2)=∅?
  • L(G1)=L(G2)?
  • L(G1)∈RegΣ*?
  • L(G1)=Σ*?
  • L(G1)⊂L(G2)?