Jazyky, automaty a vyčíslitelnost

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

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=v1vn,w=w1wm jsou slova. Potom jejich zřetězení je slovo vwv1vnw1wm.
Definice Nechť K,L jsou jazyky. Potom jejich zřetězení je jazyk KL{vw|vK,wL}.
Definice Nechť K je jazyk. Definujme mocniny K0{ε},Kn+1KnK. Potom jeho iterace je K*n0Kn 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ů, IQ je množina počátečních stavů, FQ je množina koncových stavů, Σ je abeceda a EQ×Σ×Q je množina přechodů. Přechod (p,a,q)E budeme značit paq.
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ů cp0a1p1a2anpn. Výpočet je úspěšný, pokud p0I a pnF. Ohodnocení výpočtu je slovo wa1an. Úsporně značíme p0wpn.
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,LRecΣ*. Potom KLRecΣ*.
Důkaz Vezmeme automat (QKQL,Σ,EKEL,IKIL,FKFL), 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,LRecΣ*. Potom KLRecΣ*.
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é qQ,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,)|qQ,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
u1v{wpokudv=uw,nedefinovánojinak.
Definice Nechť uΣ*,KΣ*. Potom levý kvocient je
u1K{wΣ|uwK}.
Věta uzavřenost rozeznávaných jazyků na levý kvocient Nechť uΣ*,KRecΣ*. Potom u1KRecΣ*.
Důkaz Vezmeme automat (QK,Σ,EK,Iu,FK), kde
Iu{qQK|iIK:iuq}.
Důsledek Nechť KRecΣ*. Potom množina {u1K|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|n0}Rec𝛴*, neboť tento jazyk zjevně má nekonečně mnoho různých levých kvocientů.
Definice Stav pQ 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=w1wnΣ* je wwnw1. Zrcadlový obraz jazyka LΣ* je L{w|wL}.
Věta Nechť 𝒜︀ je konečný automat. Potom L(𝒜︀𝖳)=L(𝒜︀).
Důkaz Triviální.
Věta Nechť LRecΣ*. Definujme
Pref(L){wΣ*|vΣ*:wvL},
Suf(L){wΣ*|uΣ*:uwL},
Fakt(L){wΣ*|u,vΣ*:uwvL}.
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 pQ konečného automatu je dosažitelný ze stavu qQ, 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 iI,pQ,tF existují výpočty iup,pvp,pwt, kde |v|>0. Potom zjevně každé slovo ve tvaru uvnw,n0 je rozeznávané.
(⇒)
Jistě existuje wL(𝒜︀) 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ť LRecΣ*. Potom existuje N takové, že pokud f=uv1vNwL,u,wΣ*,v1,,vNΣ+, potom existují indexy 0j<kN takové, že
n0:uv1vj(vj+1vk)nvk+1vNwL.
Důkaz Nechť 𝒜︀ je automat rozeznávající L, N je počet jeho stavů a uv1vNwL. Vezměme úspěšný výpočet iuq0v1q1v2vNqNwt. 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ť LRecΣ*. Potom existuje N takové, že pokud f=g1hg2L,|h|N, potom můžeme rozložit h=uvw,u,wΣ*,vΣ+ tak, že n0:g1uvnwg2L.
Poznámka v se nazývá iterovaný faktor nebo pumpovaný faktor.
Důsledek první věta o vkládání Nechť LRecΣ*. Potom existuje N takové, že pokud fL,|f|N, potom můžeme rozložit f=uvw,u,wΣ*,vΣ+ tak, že n0:uvnwL.
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|n0}. Dokážeme pomocí první věty o vkládání, že LRec{𝖺,𝖻}*. Kdyby byl rozeznávaný, potom existuje N0 takové, že 𝖺N𝖻N=uvw,|v|>0 tak, že pro všechna n0 je uvnwL. 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|n0}{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|n0}{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 paqεr, potom přihodíme par. 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εqar bychom přihodili hranu par, 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)|aS:(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ť piKiq,ik^ jsou přechody vedoucí do stavu q, qLjrj,jl^ jsou přechody vedoucí z něj a qMq 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 piNi,jKiMLjqj. 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 pQ je Lp{wΣ*|tF:pwt}.
Poznámka
L(𝒜︀)=iILi.
Poznámka wLp, právě když w=ε,pF nebo w=av,aΣ,vΣ*,paq,vLq.
Poznámka Můžeme si vyjádřit:
Lp=qQEp,qLq+δp,F,
kde Ep,q{L|pLq} a δp,F{ε|pF}. 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=KXL.
Důkaz Že je to řešení, dokážeme snadno. Nechť PΣ* je nějaké jiné řešení, tedy P=KPL. Z toho plyne KPP a LP. Vynásobením druhé nerovnosti zleva K dostaneme KLKPP. Dalším vynásobením dostaneme K2LKPP. Opakováním dostaneme KnLP pro všechna n0, tedy i K*LP. Předpokládejme pro spor, že K*LP, tedy existuje fPK*L. Vezměme nejkratší takové f. Jelikož P=KPL, fP a fL, musí být fKP, tedy f=gh,gK,hP. Speciálně gε, tedy |h|<|f|, tekže podle předpokladu minimality f je hK*L. Potom ale i fK*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){qQ|pwq}.
Definice Automat 𝒜︀ je deterministický, pokud |I|=1 a pQ,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𝒟︀{UQ|UF} a
E𝒟︀{PaQ|Q=pPδ(p,a)}.
Potom
wL(𝒜︀)iI:δ(i,w)Fδ𝒟︀(I,w)Fδ𝒟︀(I,w)F𝒟︀wL(𝒟︀).
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ť LRecΣ*. Potom L¯RecΣ*.
Důkaz Nechť 𝒜︀ je deterministický úplný automat pro jazyk L. Snadno dokážeme, že pro 𝒜︀¯(Q,Σ,δ,I,QF) 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 L1L2. 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 LRecΣ*. Potom φ(L)RecΔ*.
Důkaz V automatu každou hranu paq nahradíme pφ(a)q.
Poznámka Vopáčná implikace neplatí. Nechť L{𝖺n𝖻n|n0} a φ(w)𝖼|w|. Potom LRec{𝖺,𝖻}*, ale φ(L)={𝖼n|nmod2=0}Rec{𝖼}*.
Věta Nechť φ:Σ*Δ* je morfismus a LRecΔ*. 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 pq, 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 pQ. Potom pF[p]F/.
(⇒)
Plyne přímo z definice.
(⇐)
Stačí v definici ekvivalence zvolit xε.
Lemma Nechť 𝒜︀ je deterministický automat a xΣ*,pQ. 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
xL(A/)δM([i],x)F/lemma[δ(i,x)]F/lemmaδ(i,x)FxL(𝒜︀).
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,QF}. Poté vytvoříme Qk+1 jako zjemnění Qk, kde pro pq(modQk) vezmeme
pq(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,qQ:pq(modQl)Lp=Lq. Předpokládejme pro spor, že tomu pro nějaká p,q tak není. Vezměme nejkratší možné wLpLq. Nechť w=ax,aΣ. Definujeme-li rδ(p,a),sδ(q,a). Potom rs(modQl) a xLpLq, 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|pn}{p𝖻p|pn{0}}.
Potom v determinizaci tohoto automatu je každý stav dosažitelný, tedy 𝒜︀det2n stavů.

Myhillova-Nerodeova věta

Definice Nechť LRecΣ* je rozeznávaný deterministickým automatem 𝒜︀. Pro x,yΣ* definujeme ekvivalenci x𝒜︀y, pokud δ(i,x)=δ(i,y).
Věta Nechť LRecΣ* je rozeznávaný deterministickým automatem 𝒜︀. Potom 𝒜︀ je pravá kongruence, tedy x,yΣ*,aΣ:x𝒜︀yxa𝒜︀ya.
Důkaz
δ(i,xa)=δ(δ(i,x),a)=δ(δ(i,y),a)=δ(i,ya).
Věta Nechť LRecΣ* 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,yL, jinak x,yL.
Věta Nechť LRecΣ* 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ť LRecΣ* 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]|xL} a definujme přechodovou funkci jako δ([x],a)=[xa]. Z pravé kongruence plyne, že definice je korektní. Ze zjemnění plyne, že xL[x]F. Z konečného indexu plyne, že automat je konečný.
Definice Nechť LΣ*. Definujeme ekvivalenci L na Σ*, kde xLy, pokud zΣ*:xzLyzL.
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 xyxLy. Nejprve snadno dokážeme indukcí, že xyzΣ*:xzyz, a z toho už to plyne.
Věta Myhillova-Nerodeova Nechť L je jazyk. Potom následující tvrzení jsou ekvivalentní:
  1. LRecΣ*.
  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=uv1vhw,u,wΣ*,viΣ+ existují 0j<kh taková, že
uv1vhwLn0:uv1vj(vj+1vk)nvk+1vhwL.
Definice Nechť h. Jazyk LΣ* splňuje vlastnost 𝔈h, pokud pro každé f=uv1vhw,u,wΣ*,viΣ+ existují 0j<kh taková, že
uv1vhwLn0:uv1vjvk+1vhwL.
Věta Parikh-Erenfeucht-Rosenberg Nechť LΣ*. Potom následující tvrzení jsou ekvivalentní:
  1. LRecΣ*.
  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ů, NT=, SN je startovní znak a PN×(NT)* je množina produkcí. Místo (A,α)P píšeme AαP.
Definice Nechť G je gramatika a α,β,γ(NT)*,AN. Definujeme relaci , kde αAβαγβ, pokud AγP. Tranzitivní uzávěr této relace značíme *.
Definice Jazyk generovaný gramatikou G je
L(G){wT*|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 XNT v gramatice G je užitečný, pokud existuje derivace S*αXβ*wT*, kde α,β(NT)*. 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 AN,wT*:AG*w.
Důkaz Začneme s N. Následně budeme opakovaně nastavovat
NN{AN|A(w(TN)*)P}
až do doby, kdy se N nezmění. Poté si necháme jen pravidla používající symboly, které pořád máme:
PP(N×(NT)*).
Lemma Pro každou bezkontextovou gramatiku G=(N,T,P,S),L(G) existuje ekvivalentní gramatika G=(N,T,P,S) taková, že XNT,α,β(NT)*: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:
PP(N×(NT)*).
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 AN.
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 {AN|A*ε}. Začneme s {AN|AεP}. Potom budeme iterativně nastavovat
{BN|B(α+)P}.
Následně vytvoříme množinu P tak, že pro každé pravidlo AX1XkP přidáme pravidla AY1Yk taková, že
  • je-li Xi, potom Yi=Xi,
  • je-li Xi, potom Yi{Xi,ε},
  • Y1Ykε.
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 AB, kde A,BN.
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,BN,α(TN)(TN)+, 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 ABC nebo Aa, kde A,B,CN,aT.
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é aT na pravé straně nějakého pravidla Aα,|α|2 zavedeme nový nonterminál Ca, přidáme pravidlo Caa 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 AB1Bm,m3 zavést nové nonterminály D1,,Dm2 a pravidlo nahradíme pravidly AB1D1,D1B2D2,,Dm3Bm2Dm2,Dm2Bm2Bm.
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 Aaα, kde AN,aT,αN*.
Lemma Neobsahuje-li derivační strom gramatiky G v Chomského normální formě pro slovo uL(G) cestu z kořene delší než k, potom |u|2k1.
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 wL,|w|N existuje rozložení w=uv1xv2y, kde |v1xv2|N,|v1v2|1 a pro všechna n0 je uv1nxv2nyL.
Příklad Pomocí věty o vkládání můžeme snadno dokázat, že L{𝖺n𝖻n𝖼n|n0} 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 N2l. 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 NKNL=. Pro sjednocení vytvoříme nový startovní symbol SNKNL a vezmeme gramatiku
GKL(NKNL{S},TKTL,PKPL{SSL|SK},S).
Analogicky pro zřetězení vezmeme gramatiku
GKL(NKNL{S},TKTL,PKPL{SSLSK},S).
A pro iteraci vezmeme gramatiku
GK*(NK{S},TK,PK{SSKS,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,m0},K{𝖺m𝖻n𝖼n|n,m0}. 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 LK=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 LK 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 LK={𝖺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, q0Q je počáteční stav, z0Γ je symbol na dně zásobníku, FQ 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 pa,z|γq.
Definice Konfigurace zásobníkového automatu je (q,w,β), kde qQ 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Σ*|tF,βΓ*:(q0,w,z0)𝒜︀*(t,ε,β)}.
Definice Nechť 𝒜︀ je zásobníkový automat. Potom jazyk rozeznávaný prázdným zásobníkem je
LZ(𝒜︀){wΣ*|pQ:(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é tF{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é qQ. 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 xT*,AN,α(NT)*. Čá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 w011001 vzniklé odvozením
𝖲0𝖲10𝖠101𝖠01011𝖠001011011.
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|ijjk}.
Ř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=jj=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, q0Q 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 qQ 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Γ*,pF}.
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 LRS.
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 LREK.
Definice neformální Nechť pro algoritmus A na množině U značí Au jeho výsledek pro uU. Funkce f:UV je algoritmicky vyčíslitelná, pokud uU: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 uDf: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 wDf 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 1n101n2001nk.
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ž LPP1({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.
  • LRSREKL¯RS.
  • L¯RSREKLRS.
Poznámka V následujících definicích budeme porť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 P10,P21,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]1111[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}*|wiL(𝒜︀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 wkLd, potom Tk,k=0wk(Ak)=Ld;
  • je-li wkLd, potom Tk,k=1wk(Ak)=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 simuloané 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 konečného stavu, odpovíme ano.
Definice Jazyk L1 je turingovsky redukovatelný na jazyk L2, pokud existuje turingovsky vyčíslitelná funkce f:Σ*Σ* taková, že wL1f(w)L2. Značíme L1mL2.
Poznámka Pro rozhodovací problémy P1,P2 budeme značit P1mP2LP1mLP2.
Věta Nechť P1mP2. Potom
  1. P1REKP2REK,
  2. P1RSP2RS.
Důkaz Dokážeme pouze první tvrzení v obměněné implikaci, pro druhé je důkaz analogický. Nechť P2REK, 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 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 Lu¯mLd. 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ůç stroj 𝒜︀i zakódovaný číslem i.
  3. Podíváme se, jestli 𝒜︀ přijme 𝒜︀iwi.
Potom 𝒜︀ se zastaví a přijme 𝒜︀iwi 𝐴 přijme wi wLd¯. No a kdyby pro spor Ld¯REK, potom také LdREK, což víme, že není.
Definice Definujme jazyky
LNE{𝒜︀|L(𝒜︀)},
LE{𝒜︀|L(𝒜︀)=}.
Věta LNERS.
Důkaz Vezmeme nedeterministický automat, který odsimiluje zadaný automat na všech možných vstupech.
Věta LNEREK. 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 wL(𝒜︀). 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 LERS.
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 rekuurzivně 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 wi1wim=xi1xim.
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 nejednoznacnost 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{wi1wimaimai1|m,i1,,imn^},
L2{xi1ximaimai1|m,i1,,imn^}.
Vezměme gramatiku s pravidly
𝖲𝖲A|𝖲B,𝖲Awi𝖲Aai|wiai,𝖲Bxi𝖲Bai|xiai.
Tato gramatika generuje jazyk L1L2 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)?