pokud přechodová funkce není totální, doplníme ji pomocí stavu fail (do něj povedou přechody pro chybějící kombinace stavů a písmen, z něj povedou přechody pouze opět do fail pro každé písmeno)
pokud F=∅ a je vyžadováno F=∅, přidáme stav final (je incidentní jen s přechody, které vedou z final do final pro každé písmeno abecedy)
Definice: Slovo, ϵ, λ, Σ∗, Σ+, jazyk
mějme neprázdnou množinu symbolů Σ
slovo je konečná (i prázdná) posloupnost symbolů s∈Σ
prázdné slovo se značí ϵ nebo λ
Σ∗ … množina všech slov v abecedě Σ
Σ+ … množina všech neprázdných slov v abecedě Σ
jazyk L⊆Σ∗ je množina slov v abecedě Σ
Definice: Operace zřetězení, mocnina, délka slova
nad slovy Σ∗ definujeme tyto operace:
zřetězení slov u.v nebo uv
mocnina (počet opakování) un
délka slova ∣u∣
počet výskytů s∈Σ ve slově u značíme ∣u∣s
Definice: Rozšířená přechodová funkce
mějme přechodovou funkci δ:Q×Σ→Q
rozšířenou přechodovou funkci δ∗:Q×Σ∗→Q (tranzitivní uzávěr δ) definujeme induktivně:
δ∗(q,ϵ)=q
δ∗(q,wx)=δ(δ∗(q,w),x) pro x∈Σ,w∈Σ∗
idea: aplikujeme přechodovou funkci na celé slovo
Definice: Jazyky rozpoznatelné konečnými automaty, regulární jazyky
jazykem rozpoznávaným (přijímaným) deterministickým konečným automatem A=(Q,Σ,δ,q0,F) nazveme jazyk L(A)={w∣w∈Σ∗∧δ∗(q0,w)∈F}
slovo je přijímáno automatem A≡w∈L(A)
jazyk L je rozpoznatelný konečným atuomatem ≡ existuje konečný automat A takový, že L=L(A)
třídu jazyků rozpoznatelných konečnými automaty označíme F, nazveme regulární jazyky
Věta: Iterační (pumping) lemma pro regulární jazyky
věta
nechť L je regulární jazyk
(∃n∈N)(∀w∈L):∣w∣≥n⟹w=xyz
y=ϵ
∣xy∣≤n
∀k≥0:xykz∈L
důkaz
mějme regulární jazyk L, pak existuje DFA A s n stavy, přičemž L=L(A)
vezměme libovolné slovo délky aspoň n
a1a2…am=w∈L
m≥n
ai∈Σ
definujme pi jako stav automatu, v němž budeme po i písmenech toho slova
∀i:pi=δ∗(q0,a1a2…ai)
zjevně p0=q0
máme n+1pi a n různých stavů automatu, takže mezi pi se nějaký stav opakuje, vezmeme první takový
(∃i,j)(0≤i<j≤n∧pi=pj)
definujeme
x=a1…ai
y=ai+1…aj
z=aj+1…am
tj. w=xyz, y=ϵ, ∣xy∣≤n
Věta: Neregularita L01={0n1n∣n≥0}
předpokládejme regularitu L01
vezměme m z pumping lemmatu
zvolme w=0m1m
rozdělme w=xyz dle pumping lemmatu
∣xy∣≤n je na začátku w, takže obsahuje jen nuly
y=ϵ
z pumping lemmatu xz∈L01, což je spor, protože xz obsahuje méně nul než jedniček
Algoritmus: Hledání dosažitelných stavů
definice: dosažitelný stav
mějme DFA A=(Q,Σ,δ,q0,F)
stav q∈Q je dosažitelný, existuje-li w∈Σ∗ takové, že δ∗(q0,w)=q
dosažitelné stavy hledáme iterativně
začneme s M0={q0}
Mi+1=Mi∪{q∈Q:(∃p∈Mi)(∃x∈Σ)(δ(p,x)=q)}
opakujeme dokud Mi+1=Mi
korektnost
každé Mi obsahuje pouze dosažitelné stavy
úplnost
pro dosažitelný stav q mějme nejkratší takové w, že δ∗(q0,w)=q
∣w∣=n
w=x1…xn
zjevně δ∗(q0,x1…xi)∈Mi
tedy q=δ∗(q0,w)∈Mn
Redukovaný DFA
Definice: Kongruence
mějme konečnou abecedu Σ a relaci ekvivalence ∼ na Σ∗
∼ je pravá kongruence ≡(∀u,v,w∈Σ∗):u∼v⟹uw∼vw
∼ je konečného indexu ≡ rozklad Σ∗/∼ má konečný počet tříd
třídu kongruence ∼ obsahující slovo u značíme [u]∼ nebo [u]
příklady
relace „končí stejným písmenem“ je pravá kongruence
relace „mají stejný počet znaků“ není konečného indexu
Věta: Myhill-Nerodova věta
věta
nechť L je jazyk nad konečnou abecedou Σ
potom následující trzení jsou ekvivalentní:
L je rozpoznatelný konečným automatem
existuje pravá kongruence ∼ konečného indexu nad Σ∗ tak, že L je sjednocením jistých tříd rozkladu Σ∗/∼
důkaz ⟹
definujeme u∼v≡δ∗(q0,u)=δ∗(q0,v)
je to ekvivalence, je to pravá kongruence
má konečný index (protože automat má konečně mnoho stavů)
L={w∈Σ∗:δ∗(q0,w)∈F}
=⋃q∈F{w∈Σ∗:δ∗(q0,w)=q}
=⋃q∈F[w∈Σ∗:δ∗(q0,w)=q]
tedy L je sjednocením tříd, které odpovídají přijímajícím stavům automatu
důkaz ⟸
abeceda automatu bude Σ
za stavy Q položíme třídy rozkladů Σ∗/∼
počáteční stav q0:=[ϵ]
koncové stavy budou třídy, jejichž sjednocením je L
přechodová funkce δ([u],x):=[ux]
je korektní z definice pravé kongruence
zjevně L(A)=L
použití k důkazu neregularity
ukážeme pro pumpovatelný jazyk slov ve tvaru a+bici nebo bicj
pro regulární L musí existovat pravá kongruence konečného indexu m
mějme množinu řetězců S={ab,abb,abbb,…,abm+1}
∣S∣=m+1, tedy nutně existují dvě slova i=j, která padnou do stejné třídy
abi∼abj
tedy abici∼abjci
ale abici∈L a abjci∈/L, což je spor, takže jazyk není regulární
Definice: Automatový homomorfismus
nechť A1,A2 jsou DFA
řekneme, že zobrazení h:Q1→Q2 je automatovým homomorfismem, jestliže:
h(q01)=q02
h(δ1(q,x))=δ2(h(q),x)
q∈F1⟺h(q)∈F2
homomorfismus prostý a na (tzn. bijekci) nazýváme isomorfismus
Věta: Ekvivalence automatů
definice: dva konečné automaty A,B nad stejnou abecedou Σ jsou ekvivalentní, jestliže rozpoznávají stejný jazyk, tj. L(A)=L(B)
věta: existuje-li homomorfismus konečných automatů A1 do A2, pak jsou A1 a A2 ekvivalentní
důkaz
zjevně ∀w∈Σ∗:h(δ1∗(q,w))=δ2∗(h(q),w)
dále projdeme sérií ekvivalentních výroků
w∈L(A1)
δ1∗(q01,w)∈F1
h(δ1∗(q01,w))∈F2
δ2∗(h(q01),w)∈F2
δ2∗(q02,w)∈F2
w∈L(A2)
Definice: Ekvivalence stavů
říkáme, že stavy p,q∈Q konečného automatu A jsou ekvivalentní, pokud ∀w∈Σ∗:δ∗(p,w)∈F⟺δ∗(q,w)∈F
nejsou-li dva stavy ekvivalentní, říkáme, že jsou rozlišitelné
Algoritmus: Hledání rozlišitelných stavů v DFA
základ: pokud p∈F a q∈/F, pak je dvojice {p,q} rozlišitelná
indukce
nechť p,q∈Q,a∈Σ a o dvojici stavů {δ(p,a),δ(q,a)} víme, že jsou rozlišitelné, pak i {p,q} jsou rozlišitelné
opakujeme, dokud existuje nějaká nová trojice p,q,a
korektnost
uvažujme špatné páry stavů, které jsou rozlišitelné, ale algoritmus je nerozlišil
vezměme z nich pár {p,q} rozlišitelný nejkratším slovem w=a1…an
stavy r=δ(p,a1) a s=δ(q,a1) jsou rozlišitelné kratším slovem a2…an, takže pár není mezi špatnými
tedy v příštím kroku algoritmus rozliší i p,q
složitost
čas výpočtu je polynomiální vzhledem k počtu stavů
v jednom kole uvažujeme všechny páry, tj. O(n2)
kol je maximálně O(n2), protože v každém rozlišíme aspoň jeden pár
dohromady O(n4), ale lze zrychlit na O(n2) pamatováním závislostí mezi stavy
Algoritmus: Testování ekvivalence regulárních jazyků
testujeme ekvivalenci regulárních jazyků L,M
najdeme DFA AL,AM takové, že
L(AL)=L
L(AM)=M
QL∩QM=∅
vytvoříme DFA sjednocením stavů a přechodů (QL∪QM,Σ,δL∪δM,q0L,FL∪FM)
není důležité, zda jako počáteční stav zvolíme q0L nebo q0M
použijeme algoritmus hledání rozlišitelných stavů
jazyky jsou ekvivalentní ⟺ počáteční stavy q0L,q0M jsou ekvivalentní
Definice: Redukovaný DFA, redukt
deterministický konečný automat je redukovaný, pokud
nemá nedosažitelné stavy
žádné dva stavy nejsou ekvivalentní
δ je totální
konečný automat A je reduktem automatu B, pokud
A je redukovaný
A a B jsou ekvivalentní
lemma: každé dva ekvivalentní redukované automaty jsou izomorfní
lemma: pro každý DFA, který přijímá aspoň jedno slovo, existuje redukovaný DFA, který je s ním ekvivalentní
důsledek: všechny redukty jednoho DFA jsou izomorfní
Algoritmus: Nalezení reduktu DFA
eliminujeme nedosažitelné stavy
najdeme rozklad zbylých stavů na třídy ekvivalence
stavy nového automatu budou jednotlivé třídy
zkonstruujeme přechodovou funkci mezi třídami
počáteční stav nového automatu bude odpovídat třídě s počátečním stavem původního automatu
množinou přijímajících stavů budou třídy odpovídající přijímajícím stavům původního automatu
poznámka: pro nedeterministické konečné automaty tento algoritmus nefunguje
Nedeterministické ϵNFA
Definice: Nedeterministický konečný automat s ϵ přechody (ϵNFA)
nedeterministický konečný automat s ϵ přechody je pětice A=(Q,Σ,δ,q0,F)
Q … konečná množina stavů
Σ … konečná množina vstupních symbolů (abeceda)
δ:Q×(Σ∪{ϵ})→P(Q) … přechodová funkce vracející podmnožinu Q
q0∈Q … počáteční stav
alternativa: množina počátečních stavů S0⊆Q
F⊆Q … množina koncových (přijímajících) stavů
Definice: ϵ-uzávěr
pro q∈Q definujeme ϵ-uzávěr ϵclosure(q) rekurzivně
stav q je v ϵclosure(q)
p∈ϵclosure(q)∧r∈δ(p,ϵ)⟹r∈ϵclosure(q)
pro množinu stavů S⊆Q definujeme ϵclosure(S)=⋃q∈Sϵclosure(q)
idea: všechny stavy, do nichž se z daného stavu dostaneme prázdným slovem
Definice: δ∗ pro ϵNFA
mějme ϵNFA (Q,Σ,δ,q0,F)
rozšířenou přechodovou funkci δ∗ definujeme takto
δ∗(q,ϵ)=ϵclosure(q)
δ∗(q,wx)=ϵclosure(⋃p∈δ∗(q,w)δ(p,x))
pro x∈Σ,w∈Σ∗
Definice: Jazyk přijímaný ϵNFA
mějme NFA A=(Q,Σ,δ,q0,F)
pak L(A)={w∈Σ∗:δ∗(q0,w)∩F=0} je jazyk přijímaným automatem A
tedy L(A) je množina slov w∈Σ∗ takových, že δ∗(q0,w) obsahuje aspoň jeden přijímající stav
Věta: Uzavřenost regulárních jazyků na řetězcové operace
věta: jsou-li L,M regulární jazyky, jsou regulární i L.M,L∗,L+,LR,M∖L,L/M
důkaz
uvažujeme automaty pro L,M
vytvoříme NFA
jednotlivé části oddělujeme epsilon přechody, aby nemohly interagovat
LR … obrátíme šipky ve stavovém diagramu
M∖L
algoritmicky najdeme stavy, kam se dá dostat slovem z M
do těch stavů dáme epsilon přechody z počátečního stavu
L/M=(MR∖LR)R
ostatní jsou intuitivní
Regulární výrazy
Definice: Regulární výrazy, hodnota regulárního výrazu
RegE(Σ) … množina všech regulárních výrazů nad konečnou neprázdnou abecedou
L(α) … hodnota regulárního výrazu α
regulární výraz a jeho hodnota jsou definovány induktivně
základ
ϵ … prázdný řetězec, L(ϵ)={ϵ}
∅ … prázdný výraz, L(∅)=∅
a … znak a∈Σ, L(a)={a}
indukce
α+β … jako OR, L(α+β)=L(α)∪L(β)
αβ … L(αβ)=L(α)L(β)
α∗ … L(α∗)=L(α)∗
(α) … závorky nemění hodnotu, L((α))=L(α)
nejvyšší prioritu má iterace ∗, pak zřetězení, pak sjednocení +
třída RegE(Σ) je nejmenší třída uzavřená na uvedené operace
Věta: Varianta Kleeneho věty
věta
každý jazyk reprezentovaný konečným automatem lze zapsat jako regulární výraz
každý jazyk popsaný regulárním výrazem lze zapsat jako ϵNFA
důkaz
výraz → ϵNFA
indukcí dle struktury výrazu (viz prezentace)
jednotlivé stavební bloky musíme dostatečně oddělovat epsilon přechody
DFA → výraz
střídavě používáme dva kroky
sloučení hran – když mezi dvěma stavy vede více hran stejným směrem, nahradíme je jednou hranou ohodnocenou sjednocením regulárních výrazů z původních hran (sjednocujeme pomocí +)
eliminace stavu – libovolný stav, který není počáteční ani přijímající, odstraníme a zařídíme, že všechny trasy výpočtu, které jím původně procházely, zůstanou zachovány (přidáme odpovídající hrany)
pokud ve stavu byla smyčka, zohledníme to na hranách, přičemž výraz ze smyčky bude mít iteraci ∗
nakonec sjednotíme výrazy na hranách z počátečního do přijímajících stavů
Definice: Substituce jazyků
mějme konečnou abecedu Σ
pro každé x∈Σ budiž σ(x) jazyk v nějaké abecedě Yx
položme
σ(ϵ)={ϵ}
σ(u.v)=σ(u).σ(v)
zobrazení σ:Σ∗→P(Y∗), kde Y=⋃x∈ΣYx, se nazývá substituce
pro jazyk L definujeme σ(L)=⋃w∈Lσ(w)
nevypouštějící substituce je taková, kde žádné σ(x) neobsahuje ϵ
pokud ∀i=j:βi=βj, hovoříme o minimálním odvození
libovolný řetězec ω∈(V∪T)∗ odvoditelný z počátečního symbolu S nazýváme sentenciální forma
Definice: Jazyk generovaný gramatikou G
jazyk L(G) generovaný gramatikou G=(V,T,P,S) je množina terminálních řetězců, pro které existuje derivace ze startovního symbolu L(G)={w∈T∗:S⇒G∗w}
jazyk neterminálu A∈V definujeme L(A)={w∈T∗:A⇒G∗w}
Věta: L∈RE⟹L∈L3
věta: pro každý jazyk rozpoznávaný konečným automatem existuje gramatika typu 3, která ho generuje
důkaz
L=L(A) pro deterministický konečný automat A=(Q,Σ,δ,q0,F)
definujme gramatiku G=(Q,Σ,P,q0), kde pravidla P mají tvar
p→aq, když δ(p,a)=q
p→ϵ, když p∈F
platí L(A)=L(G)?
otestujeme pro prázdné a neprázdné slovo
Věta: ϵ-NFA pro gramatiku typu 3 rozpoznávající stejný jazyk
lemma: ke každé gramatice typu 3 existuje gramatika typu 3, která generuje stejný jazyk a obsahuje pouze pravidla ve tvaru A→aB,A→ϵ, kde A,B∈V,a∈T
zavedeme nové neterminály
odstraníme pravidla A→B
místo pravidel tvaru A→a1…anB nebo A→a1…an přidáme řetězce pravidel v povoleném tvaru
věta: pro každý jazyk L generovaný gramatikou typu 3 existuje ϵNFA rozpoznávající L
vezmeme G=(V,T,P,S) obsahující jen pravidla tvaru A→aB, respektive A→ϵ
z té snadno vyrobíme automat
Definice: Levé (a pravé) lineární gramatiky
gramatiky typu 3 nazýváme také pravé lineární (neterminál je vždy vpravo)
gramatika je levá lineární, jestliže má pouze pravidla tvaru A→Bw nebo A→w, přičemž A,B∈V,w∈T∗
lemma: jazyky generované levou lineární gramatikou jsou právě regulární jazyky
lze dokázat pomocí reverze
Definice: Lineární gramatika, jazyk
gramatika je lineární, jestliže má pouze pravidla tvaru A→uBw nebo A→w, kde A,B∈V,u,w∈T∗ (na pravé straně vždy maximálně jeden neterminál)
lineární jazyky jsou právě jazyky generované lineárními gramatikami
příklad: jazyk L={0i1i∣i≥1}
pozorování: lineární pravidla lze rozložit na levě a pravě lineární pravidla
Definice: Derivační strom
mějme gramatiku G=(V,T,P,S)
derivační strom pro G je strom, kde
kořen je označen startovním symbolem S
každý vnitřní uzel je ohodnocen neterminálem V
každý uzel je ohodnocen prvkem ze sjednocení V∪T∪{ϵ}
je-li uzel ohodnocen ϵ, je jediným dítětem svého rodiče
je-li A ohodnocení vrcholu a jeho děti jsou zleva po řadě ohodnoceny X1,…,Xk, pak (A→X1…Xk)∈P je pravidlo gramatiky
říkáme, že derivační strom dává (yields) sentenciální formu α (slovo w), jestliže α (respektive w) vznikne zřetězením listů ve směru zleva doprava
Definice: Levá a pravá derivace
levá (leftmost) derivace ⇒lm,⇒lm∗ v každém kroku přepisuje nejlevější neterminál
pravá (rightmost) derivace ⇒rm,⇒rm∗ v každém kroku přepisuje nejpravější neterminál
Věta: Ekvivalence tvrzení o derivacích
věta: pro danou gramatiku a jsou následující tvrzení ekvivalentní
A⇒lm∗w
A⇒∗w
existuje derivační strom s kořenem A dávající slovo w
důkaz
(1)⟹(2) … triviálně
(2)⟹(3) … z derivace vytvoříme strom
(3)⟹(1) … pro libovolný derivační strom najdeme levou derivaci průchodem stromu
Definice: Ekvivalence gramatik
gramatiky G1,G2 jsou ekvivalentní, jestliže L(G1)=L(G2), tj. generují stejný jazyk
Chomského normální forma, CFG
Definice: Zbytečný, užitečný, generující, dosažitelný symbol
symbol X je užitečný v gramatice G=(V,T,P,S), pokud existuje derivace tvaru S⇒∗αXβ⇒∗w, kde w∈T∗,X∈(V∪T),α,β∈(V∪T)∗
pokud X není užitečný, říkáme, že je zbytečný
X je generující, pokud X⇒∗w pro nějaké slovo w∈T∗
X je dosažitelný, pokud S⇒∗αXβ pro nějaká α,β∈(V∪T)∗
Definice: Nulovatelný neterminál; jednotkové pravidlo, jednotkový pár
neterminál A je nulovatelný, pokud A⇒∗ϵ
jednotkové pravidlo je (A→B)∈P, kde A,B jsou oba neterminály
dvojici A,B∈V takovou, že A⇒∗B pouze jednotkovými pravidly, nazýváme jednotkový pár (jednotková dvojice)
Věta: Gramatika v normálním tvaru, redukovaná
lemma
mějme bezkontextovou gramatiku G takovou, že L(G)−{ϵ}=∅
pak existuje CFG G1 taková, že L(G1)=L(G)−{ϵ}, a G1 neobsahuje ϵ-pravidla, jednotková pravidla ani zbytečné symboly
gramatika G1 se nazývá redukovaná
idea důkazu (podrobněji viz převod do Chomského normálního tvaru, který je silnější)
eliminujeme ϵ-pravidla
eliminujeme jednotková pravidla (tím nepřidáme ϵ-pravidla)
eliminujeme zbytečné symboly (tím nepřidáme žádná pravidla)
nejdříve eliminujeme negenerující, pak nedosažitelné
Definice: Chomského normální tvar
o bezkontextové gramatice G=(V,T,P,S) bez zbytečných symbolů, kde jsou všechna pravidla ve tvaru A→BC nebo A→a, kde A,B,C∈V,a∈T, říkáme, že je v Chomského normálním tvaru (ChNF)
Věta: Chomského normální tvar bezkontextové gramatiky
Algoritmus: Převod CFG do Chomského normálního tvaru
věta: mějme bezkontextovou gramatiku G takovou, že L(G)−{ϵ}=∅, pak existuje CFG G1 v Chomského normálním tvaru taková, že L(G1)=L(G)−{ϵ}
algoritmus
eliminujeme ϵ-pravidla
označíme nulovatelné symboly
přidáme verzi pravidel bez nulovatelných symbolů
odstraníme ϵ-pravidla
eliminujeme jednotková pravidla (tím nepřidáme ϵ-pravidla)
najdeme jednotkové páry
přidáme odpovídající pravidla
odstraníme jednotková pravidla
eliminujeme zbytečné symboly (tím nepřidáme žádná pravidla)
nejdříve eliminujeme negenerující, pak nedosažitelné
pravé strany délky aspoň 2 předěláme na samé neterminály
pravé strany s aspoň třemi neterminály rozdělíme na více pravidel
Věta: Lemma o vkládání (pumping) pro bezkontextové jazyky
věta
nechť L je bezkontextový jazyk
(∃n)(∀w∈L):∣w∣≥n⟹w=u1u2u3u4u5
u2u4=ϵ
∣u2u3u4∣≤n
∀k≥0:u1u2ku3u4ku5∈L
poznámka: v prezentaci je ostrá nerovnost ∣w∣>n, v jiných zdrojích neostrá
idea důkazu
vezmeme derivační strom pro w
nejdeme nejdelší cestu, na ní dva stejné neterminály
tyto neterminály určí dva postromy, které definují rozklad slova
větší podstrom můžeme posunout (k>1) nebo nahradit menším podstromem (k=0)
důkaz
vezmeme gramatiku v Chomského normální formě (pro L={ϵ} a ∅ zvol n=1)
nechť ∣V∣=v
položíme n=2v
pro w∈L takové, že ∣w∣≥n, má v derivačním stromu w cestu délky >v
pro slovo délky rovné 2v bude mít nejmělčí možný strom v+2 úrovní (většina vnitřních vrcholů se binárně větví, poslední úroveň slouží pro přechod k terminálům), tedy nejdelší cesty budou obsahovat v+2 vrcholů (z toho v+1 neterminálů)
vezmeme cestu maximální délky, terminál, kam vede, označíme t
aspoň dva z posledních v+1 neterminálů na cestě do t jsou stejné
vezmeme dvojici A1,A2 nejblíže k t (určují podstromy T1,T2)
cesta z A1 do t je nejdelší v podstromu T1 a má délku maximálně v+1
z toho plyne ∣u2u3u4∣≤n, jelikož slovo u2u3u4 je dané podstromem T1
z A1 vedou dvě cesty, jedna do T2, druhá do zbytku u2u4
Chomského normální tvar je nevypouštějící, tedy u2u4=ϵ
bezkontextová gramatika G=(V,T,P,S) je víceznačná, pokud existuje aspoň jeden řetězec w∈T∗, pro který můžeme najít dva různé derivační stromy, oba s kořenem S, dávající slovo w
v opačném případě nazýváme gramatiku jednoznačnou
bezkontextový jazyk L je jednoznačný, jestliže existuje jednoznačná CFG G tak, že L=L(G)
bezkontextový jazyk L je (podstatně) nejednoznačný, jestliže každá CFG G taková, že L=L(G), je nejednoznačná, takovému jazyku říkáme i víceznačný
poznámky
neexistuje algoritmus, který nám řekne, zda je gramatika víceznačná
typické příčiny víceznačnosti
není respektovaná priorita operátorů
posloupnost identických operátorů lze shlukovat zleva i zprava
odstranění víceznačnosti vynucením priority
zavedeme více různých proměnných, každou pro jednu úroveň „priority“
faktor – nelze rozdělit žádným operátorem
term – nelze rozdělit operátorem +, lze rozdělit ⋅
výraz – lze rozdělit + i ⋅
Zásobníkové automaty
Definice: Zásobníkový automat (PDA)
zásobníkový automat (PDA) je sedmice P=(Q,Σ,Γ,δ,q0,Z0,F)
Q … konečná množina stavů
Σ … neprázdná konečná množina vstupních symbolů
Γ … neprázdná konečná zásobníková abeceda
δ … přechodová funkce
δ:Q×(Σ∪{ϵ})×Γ→PFIN(Q×Γ∗)
kde PFIN(A) je množina všech konečných podmnožin množiny A
tedy δ(p,a,X)∋(q,γ)
q je nový stav
γ je řetězec zásobníkových symbolů, který nahradí X na vrcholu zásobníku
q0∈Q … počáteční stav
Z0∈Γ … počáteční zásobníkový symbol
F … množina přijímajících (koncových) stavů (může být nedefinovaná)
jak PDA funguje
je nedeterministický
v jednom časovém kroku
na vstupu přečte žádný nebo jeden symbol
přejde do nového stavu
nahradí symbol na vrchu zásobníku libovolným řetězcem (nejlevější znak bude na vrchu)
přechodový diagram
jako pro konečný automat
hrany popisujeme ve tvaru: vstupní znak, zásobníkový znak → push řetězec
jazyk přijímaný koncovým stavem je L(Pda)={w∈Σ∗:(∃q∈F)(∃α∈Γ∗)((q0,w,Z0)⊢Pda∗(q,ϵ,α))}
jazyk přijímaný prázdným zásobníkem je N(Pda)={w∈Σ∗:(∃q∈Q)((q0,w,Z0)⊢Pda∗(q,ϵ,ϵ))}
množina F je nerelevantní, takže ji lze vynechat – pak je PDA šestice
Věta: L(CFG), L(PDA), N(PDA)
lemma: vstup, který není čtený, a dno zásobníku neovlivní výpočet
lemma: od přijímajícího stavu k prázdnému zásobníku
na dno zásobníku přidáme špunt
z přijímajících stavů vedeme hranu do vypouštěcího stavu, kde zásobník vyprázdníme
lemma: od prázdného zásobníku ke koncovému stavu
na dno zásobníku přidáme špunt
z každého stavu uděláme přechod takový, že pokud je vidět špunt, přemístíme se do koncového stavu
věta: následující tvrzení jsou ekvivalentní
jazyk L je bezkontextový, tj. generovaný bezkontextovou gramatikou
jazyk L je přijímaný nějakým zásobníkovým automatem koncovým stavem
jazyk L je přijímaný nějakým zásobníkovým automatem prázdným zásobníkem
důkaz: ekvivalenci N(PDA) a L(PDA) už máme, ještě ukážeme ekvivalenci L(CFG) a N(PDA)
lemma: N(PDA) z L(CFG) – viz algoritmus „konstrukce PDA z CFG“
lemma: pro PDA existuje CFG
máme PDA (Q,Σ,Γ,δ,q0,Z0)
neterminály gramatiky budou složené symboly [qXp] … PDA vyšel z q, vzal X a (nakonec) přešel do p
zavedeme nový počáteční symbol S
definujeme pravidla
∀p∈Q:S→[q0Z0p]
„začneme v q0, (hned) odebereme Z0 (ale možná tam zase něco vrátíme) a nakonec se dostaneme do (koncového) stavu p“ (tedy přijmeme prázdným zásobníkem)
levá strana – jsme ve stavu q, z vrchu zásobníku vezmeme X, pak se (možná) něco stane, nakonec budeme v nějakém stavu pk
pravá strana – přešli jsme ze stavu q do konkrétního stavu p, přitom jsme přečetli písmeno s ze vstupu a na zásobníku přibyly symobly Y1…Yk, které je potřeba zpracovat (při zpracování prvního symbolu budeme vycházet z konkrétního stavu p, po zpracování posledního symbolu se dostaneme do nějakého stavu pk)
takže vlastně začátek každé strany pravidla vždycky vychází z přechodu, konec je „náhodný“
speciálně pro (p,ϵ)∈δ(q,a,A) vytvoříme pravidlo [qAp]→a
Algoritmus: Konstrukce PDA z CFG
mějme gramatiku G=(V,T,P,S)
konstruujeme PDA P=({q},T,V∪T,δ,q,S)
∀A∈V:δ(q,ϵ,A)={(q,β)∣(A→β)∈P}
∀a∈T:δ(q,a,a)={(q,ϵ)}
P přijímá prázdným zásobníkem
idea
stavy nás nezajímají – stačí nám jeden
na zásobníku nedeterministicky generujeme všechny možné posloupnosti terminálů
zásobníkový automat P=(Q,Σ,Γ,δ,q0,Z0,F) je deterministický PDA, právě když platí zároveň
δ(q,a,X) je nejvýše jednoprvková pro libovolnou trojici q,a,X
je-li δ(q,a,X) neprázdná pro nějaké a∈Σ, pak δ(q,ϵ,X) musí být prázdná
Věta: Zařazení LDPDA mezi LPDA a regulární jazyky
věta: nechť je L regulární jazyk, pak L=L(P) pro nějaký DPDA P
DPDA může simulovat deterministický konečný automat a ignorovat zásobník
lemma: jazyk Lwcwr je přijímaný DPDA, ale není regulární
Lwcwr … jazyk palindromů se středovou značkou c
důkaz neregularity plyne z pumping lemmatu na slovo 0nc0n
lemma: jazyk Labb je bezkontextový, ale není přijímaný žádným DPDA
Labb={aibi∣i∈N}∪{aib2i∣i∈N}
dokážeme sporem, uvažujme DPDA M přijímající Labb
vytvořme dvě kopie, M1 a M2
v M2 místo b budeme mít písmenko c
zkonstruujeme nový automat, počátečním stavem bude počáteční stav M1, koncovými stavy budou koncové stavy M2
z koncových stavů M1 uděláme přechody do odpovídajících stavů v M2
takový automat bude nutně přijímat {aibici∣i∈N}, což je spor, protože ten jazyk není bezkontextový, takže deterministický M nemůže existovat
Věta: L∈N(PDPDA), právě když L bezprefixový a L∈L(PDPDA′)
definice: jazyk L⊂Σ∗ je bezprefixový, pokud neexistují slova u,v∈L a z∈Σ+ taková, že u=vz
tj. pro žádná dvě slova u,v není v vlastním prefixem u
věta: jazyk L je N(P) pro nějaký DPDA P, právě když L je bezprefixový a L je L(P′) pro nějaký DPDA P′
důkaz⟹
prefix přijmeme prázdným zásobníkem
pro prázdný zásobník neexistuje instrukce, tj. žádné prodloužení není v N(P)
důkaz ⟸
převod P′ na P nepřidá nedeterminismus
Uzávěrové vlastnosti
Věta: CFL uzavřené na sjednocení, konkatenaci, iteraci, reverzi, naopak neuzavřené na průnik
důkazy
sjednocení
pokud V1∩V2=∅, musíme přejmenovat neterminály
přidáme nový symbol Snew a pravidlo Snew→S1∣S2
zřetězení
pokud V1∩V2=∅, musíme přejmenovat neterminály
Snew→S1S2
iterace
Snew→SSnew∣ϵ
pozitivní iterace
Snew→SSnew∣S
zrcadlový obraz (reverze)
obrátíme pravou stranu pravidel
protipříklad uzavřenosti na průnik
jazyk L={0n1n2n∣n≥1}={0n1n2i∣n,i≥1}∩{0i1n2n∣n,i≥1} není bezkontextový, přestože oba členy průniku jsou bezkontextové
Věta: CFL i DCFL jsou uzavřené na průnik s regulárním jazykem
zásobníkový a konečný automat můžeme spojit
uvažujeme PDA přijímající koncovým stavem
sestrojíme vlastně něco jako součinový automat
pokud se v daném přechodu nečte vstup, tak konečný automat stojí
Věta: CFL jsou uzavřené na substituci a homomorfismus
idea: listy v derivačním stromě generují další stromy
přejmenujeme neterminály na jednoznačné ve všech gramatikách
máme G=(V,Σ,P,S) a ∀a∈Σ:Ga=(Va,Ta,Pa,Sa)
vytvoříme novou gramatiku G′=(V′,T′,P′,S′)
V′=V∪⋃a∈ΣVa
T′=⋃a∈ΣTa
P′=⋃a∈ΣPa sjednoceno s pravidly z P, ve kterých všechna a∈Σ nahradíme Sa
G′ generuje jazyk σ(L)
idea pro homomorfismus: terminál a v derivačním stromě nahradím slovem h(a)
Věta: CFL jsou uzavřené na inverzní homomorfismus
věta
mějme bezkontextový jazyk L a homomorfismus h
pak h−1(L) je bezkontextový jazyk
je-li L deterministický CFL, je i h−1(L) deterministický CFL
idea důkazu
podobně jako u regulárních jazyků
máme PDA s bufferem
buffer je konečný, takže ho lze modelovat ve stavu
důkaz v prezentaci
Věta: Odečtení regulárního jazyka
věta
mějme bezkontextový jazyk L a regulární jazyk R
pak L−R je CFL
důkaz
L−R=L∩R
R je regulární
Věta: CFL nejsou uzavřené na doplněk ani rozdíl
L nemusí být CFL
protože L1∩L2=L1∪L2
L1−L2 nemusí být CFL
jelikož Σ∗−L (tedy doplněk) není vždy CFL
Věta: Uzavřenost DCFL na doplněk, sjednocení, průnik a homomorfismus
lemma: doplněk deterministického CFL je opět deterministický CFL
převrátíme koncovost stavů
nedefinované kroky ošetříme podložkou na zásobníku
cyklus odhalíme pomocí čítače
až po přečtení slova prochází koncové a nekoncové stavy (stačí si pamatovat, zda prošel koncovým stavem)
lemma: DCFL nejsou uzavřené na sjednocení ani průnik
jako protipříklad průniku opět použijeme L={0n1n2n∣n≥1}={0n1n2i∣n,i≥1}∩{0i1n2n∣n,i≥1}
uzavřenost sjednocení pak vylučuje identita L1∩L2=L1∪L2
lemma: DCFL nejsou uzavřené na homomorfismus
problém nastane např. když pomocí h(c)=ϵ odstraníme středovou značku z jazyka palindromů Lwcwr
Turingův stroj
Definice: Turingův stroj
turingův stroj (TM) je sedmice M=(Q,Σ,Γ,δ,q0,B,F)
Q … konečná množina stavů
Σ … konečná neprázdná množina vstupních symbolů
Γ … konečná množina všech symbolů pro pásku
vždy Γ⊇Σ,Q∩Γ=∅
δ … (částečná) přechodová funkce
zobrazení (Q−F)×Γ→Q×Γ×{L,R}
δ(q,X)=(p,Y,D)
q∈(Q−F) … aktuální stav
X∈Γ … aktuální symbol na pásce
p∈Q … nový stav
Y∈Γ … symbol pro zapsání do aktuální buňky, přepíše aktuální obsah
D∈{L,R} … směr pohybu hlavy (doleva, doprava)
q0∈Q … počáteční stav
B∈Γ−Σ … blank = symbol pro prázdné buňky, na začátku všude kromě konečného počtu buněk se vstupem
F⊆Q … množina koncových neboli přijímajících stavů
poznámka: někdy se nerozlišuje Γ a Σ a neuvádí se B, pak je TM pětice
Definice: Konfigurace Turingova stroje, krok Turingova stroje
konfigurace Turingova stroje (ID) je řetězec X1X2…Xi−1qXiXi+1…Xn
q … stav Turingova stroje
čtecí hlava je vlevo od i-tého symbolu
X1…Xn je část pásky mezi nejlevějším a nejpravějším symbolem různým od prázdného
výjimka: pokud je hlava na kraji, na tom kraji vkládáme jeden B navíc
kroky turingova stroje M značíme podobně jako u zásobníkových automatů (⊢M,⊢M∗)
Definice: TM přijímá jazyk, rekurzivně spočetný jazyk
turingův stroj M=(Q,Σ,Γ,δ,q0,B,F) přijímá jazyk L(M)={w∈Σ∗:(∃p∈F)(∃α,β∈Γ∗)(q0w⊢M∗αpβ)}
tj. množinu slov, po jejichž přečtení se dostane do koncového stavu
pásku nemusí uklízet (v naší definici)
jazyk nazveme rekurzivně spočetným, pokud je přijímán nějakým Turingovým strojem
Definice: Přechodový diagram pro TM
jako pro konečný automat
hrana q→p je označena seznamem všech dvojic X/YD, kde δ(q,X)=(p,Y,D)
D∈{←,→}
Definice: Vícepáskový Turingův stroj
počáteční pozice
vstup na první pásce, ostatní zcela prázdné
první hlava vlevo od vstupu, ostatní libovolně
hlava v počátečním stavu
jeden krok vícepáskového TM
hlava přejde do nového stavu
na každé pásce napíšeme nový symbol
každá hlava se nezávisle posune vlevo, zůstane na místě nebo se posune vpravo
Věta: Vícepáskový Turingův stroj
věta: každý jazyk přijímaný vícepáskovým TM je přijímaný i nějakým (jednopáskovým) Turingovým strojem
důkaz
máme k-páskový TM
konstruujeme jednopáskový TM
pásku si představíme, že má 2k stop (nad sebou)
liché stopy: pozice k-té hlavy
sudé stopy: znak na k-té pásce
pro simulaci jednoho kroku navštívíme všechny hlavy
ve stavu si pamatujeme
počet hlav vlevo
pro každé k symbol pod k-tou hlavou
pak už umíme provést jeden krok
simulaci výpočtu k-páskového stroje o n krocích lze provést v čase O(n2)
Definice: Nedeterministický TM
nedeterministickým Turingovým strojem nazýváme sedmici stejnou jako u TM
akorát δ:(Q−F)×Γ→P(Q×Γ×{L,R})
slovo w∈Σ∗ je přijímáno nedeterministickým TM, pokud existuje nějaký výpočet q0w⊢∗αpβ, kde p∈F
Věta: Nedeterministický TM
věta: pro každý MN nedeterministický TM existuje MD deterministický TM takový, že L(MN)=L(MD)
idea
prohledáváme do šířky všechny možné výpočty MN
modelujeme TM se dvěma páskami
první páska: posloupnost (fronta) konfigurací
druhá páska: pomocný výpočet
vždycky vezmeme konfiguraci z fronty, provedeme na ní postupně každý možný krok a výsledek vždy přidáme na konec fronty
Věta: TM s jednosměrnou páskou
věta: pro každý TM existuje TM, který přijímá stejný jazyk a nikdy nejde vlevo od počáteční pozice a nikdy nepíše blank B
důkaz
zákaz psaní blanku B
místo psaní B budeme psát B1
všechny instrukce pro čtení B zkopírujeme rovněž pro čtení B1
jednosměrná páska
přepíšeme vstup do horní stopy dvoustopé pásky
pod nejlevější symbol dáme nový znak ∗, abychom věděli, že jsme na levém okraji a máme přepnout z horní stopy do dolní
ve stavu („hlavě“) si pamatujeme, jestli čteme horní nebo spodní stopu
pokud vidíme ∗, odpovídající instrukce přepíšeme na změnu stopy
LBA, diagonální jazyk
Definice: Separovaná gramatika
definice: gramatika je separovaná, pokud obsahuje pouze pravidla tvaru α→β, kde
buď α,β∈V+ (neprázdné posloupnosti neterminálů),
nebo α∈V a β∈T∪{ϵ}
lemma: ke každé gramatice G lze sestrojit ekvivalentní separovanou gramatiku G′
stačí všechny terminály nadtrhnout a přidat pravidla ∀a∈T:a→a
Definice: Monotónní (nevypouštějící) gramatika
gramatika je monotónní (nevypouštějící), jestliže pro každé pravidlo (α→β)∈P platí ∣α∣≤∣β∣
monotónní gramatiky slovo v průběhu generování nezkracují
lemma: ke každé monotónní gramatice lze nalézt ekvivalentní kontextovou gramatiku
připomenutí: v kontextové gramatice povolujeme pravidla αAβ→αωβ
A∈V
α,β∈(V∪T)∗
ω∈(V∪T)+
nejprve gramatiku separujeme
stále jsme se nezbavili pravidel tvaru AB→CD (a delších), kde všechna písmena jsou neterminály
přidáme sadu nových neterminálů
např. AB→CD převedeme na AB→AˉB→AˉBˉ→CBˉ→CD
Věta: Příklad kontextového jazyka
lemma: jazyk L={aibjck∣1≤i≤j≤k} je kontextový jazyk, není bezkontextový
důkaz (na jedničku je potřeba umět)
S→aSBC∣aBC … generování symbolů a
B→BBC … množení symbolů B
C→CC … množení symbolů C
CB→BC … uspořádání symbolů B a C (pravidlo není kontextové, je potřeba ho upravit nadtrháváním)
aB→ab … začátek přepisu B na b
bB→bb … pokračování přepisu B na b
bC→bc … začátek přepisu C na c
cC→cc … pokračování přepisu C na c
je důležité, že tam chybí cB→cb
Definice: Lineárně omezený automat (LBA)
lineárně omezený automat je nedeterministicý TM, kde na pásce je označen levý a pravý konec l,r
tyto symboly nelze při výpočtu přepsat a nesmí se jít nalevo od l ani napravo od r
slovo w je přijímáno LBA, pokud existuje přijímající výpočet q0lwr⊢∗lαpβr, kde p∈F
Věta: Každý kontextový jazyk lze přijímat pomocí LBA
máme kontextovou gramatiku, sestrojíme LBA
prázdné slovo vyřešíme zvlášť
derivaci gramatiky budeme simulovat pomocí LBA
použijeme pásku se dvěma stopami
slovo w dáme nahoru, na začátek dolní stopy dáme S
nedeterministicky přepisujeme slovo ve druhé stopě podle pravidel G
pravá část se odsune
pokud jsou ve druhé stopě samé terminály, porovnáme ji s první stopou
slovo přijmeme nebo zamítneme
Věta: LBA přijímají pouze kontextové jazyky
máme LBA, sestrojíme monotónní gramatiku
výpočet ukryjeme do „dvoustopých“ neterminálů
nejprve vygenerujeme slovo, kde v horní stopě bude nějaké slovo ∈Σ∗ a ve spodní bude páska LBA s tímto slovem (v prvním neterminálu dole bude trojice q0,l,a0, v posledním bude dole dvojice an,r)
pak simulujeme práci LBA ve „druhé“ stopě
jakmile se dostaneme do koncového stavu, smažeme „druhou“ stopu
speciálně je potřeba ošetřit přijímání prázdného slova – pomocí speciálního startovacího pravidla
Věta: Rekurzivně spočetné jsou L0
máme TM, sestrojíme gramatiku
gramatika nejprve vygeneruje slovo a obrácenou pásku stroje (se slovem)
potom simuluje výpočet
nakonec smaže pásku, nechá pouze slovo
Věta: Každý jazyk typu 0 je rekurzivně spočetný
idea: TM postupně generuje všechny derivace
derivaci S⇒ω1⇒⋯⇒ωn=w kódujeme jako slovo #S#ω1#…#w#
umíme udělat TM, který přijímá slova #α#β#, kde α⇒β
umíme udělat TM, který přijímá takto zapsanou posloupnost derivací
tedy umíme udělat TM postupně generující všechna slova
vygenerujeme slovo
tvoří slovo derivaci?
končí derivace slovem w?
pokud ano, přijímáme w
pokud ne, generujeme další slovo
Definice: TM zastaví
TM zastaví, pokud vstoupí do stavu q s čteným symbolem X a pokud neexistuje instrukce pro tuto konfiguraci, tedy δ(q,X) není definováno
z definice vyplývá, že v přijímajícím stavu TM zastaví
dokud nezastaví, nevíme, jestli přijme nebo nepřijme slovo
Definice: Rekurzivní jazyky
říkáme, že TM M rozhoduje jazyk L, pokud L=L(M) a pro každé w∈Σ∗ stroj nad w zastaví
jazyky rozhodnutelné TM nazýváme rekurzivní jazyky
rekurzivní jazyky jsou podmnožinou rekurzivně spočetných jazyků
Definice: Diagonální jazyk
diagonální jazyk Ld je definovaný jako jazyk slov w∈{0,1}∗ takových, že TM reprezentovaný jako w nepřijímá slovo w
kódování TM
M={Q,{0,1},Γ,δ,q1,B,{q2}}
předpokládáme
počáteční stav je vždy q1
q2 je vždy jediný koncový stav
první symbol je 0, druhý 1, třetí B, ostatní symboly pásky očíslujeme libovolně
směr L je 1, směr L je 2
krok δ(qi,Xj)=(qk,Xl,Dm) kódujeme jako 0i10j10k10l10m
zjevně nebudou dvě jedničky za sebou, protože stavy, symboly i směry číslujeme od jedničky
celý TM se skládá z kódů přechodů v nějakém pořadí oddělených dvojicemi jedniček
pořadí kódů: jsou seřazeny podle délky, stejně dlouhé jsou uspořádány lexikograficky
Věta: Ld není rekurzivně spočetný jazyk
věta: Ld není rekurzivně spočetný jazyk, tj. neexistuje TM přijímající Ld
idea důkazu
kdyby existoval TM přijímající Ld, spuštění takového stroje na vlastním kódu by vedlo k paradoxu
důkaz
mějme uspořádanou spočetnou množinu Turingových strojů
kód každého z nich označím jako wi
mějme tabulku, kde v buňce ij bude 1 nebo 0 podle toho, jestli automat s kódem wi přijímá slovo wj
Ld pak bude obsahovat slova wk taková, že v buňce kk bude napsáno „nepřijímá“
předpokládejme, že Ld je rekurzivně spočetný, tedy Ld=L(Md) pro nějaký TM Md (kód takového automatu máme označený jako wd)
co bude v tabulce v buňce dd, které odpovídá otázce, zda automat Md přijímá svůj vlastní kód?
pokud Md přijímá svůj kód, je to spor, protože kód Md pak nemůže náležet do Ld
pokud Md nepřijímá svůj kód, je to spor, protože kód Md pak musí náležet do Ld
Definice: Univerzální jazyk
univerzální jazyk Lu definujeme jako množinu binárních řetězců, které kódují pár (M,w), kde M je TM a w∈L(M)
TM přijímající Lu se nazývá univerzální Turingův stroj
Věta: Existence univerzálního Turingova stroje
věta: existuje Turingův stroj U, pro který Lu=L(U)
idea: pojďme sestrojit Turingův stroj, který simuluje Turingův stroj s kódem M
důkaz
popíšeme U jako vícepáskový Turingův stroj
na první pásce máme přechody M a řetězec w
na druhé pásce simulujeme výpočet M používající stejný formát jako kód M (takže nuly oddělené jedničkami)
třetí páska obsahuje stav M reprezentovaný i nulami
dále máme pomocnou čtvrtou pásku
průběh výpočtu
otestujeme, zda je kód M legitimní (jestli ne, zastavíme U bez přijetí)
inicializujeme 2. pásku kódovaným slovem (každý znak kódujeme jako jedničku a k nul, kde k je číslo znaku)
blanky necháme prázdné a nahradíme 1000 pouze v případě potřeby
na 3. pásku napíšeme počáteční stav 0
posuneme hlavu na 2. pásce na první simulované políčko
simulace jednoho přechodu
na první pásce najdeme přechod
změníme stav na 3. pásce
nahradíme znak na 2. pásce (tady používáme pomocnou 4. pásku)
posuneme hlavu na 2. pásce správným směrem
pokud jsme nenašli instrukci pro M, zastavíme
pokud M přejde do přijímajícího stavu, tak U také přijme
Věta: Postova věta
lemma: je-li L rekurzivní jazyk, je rekurzivní i L
stroj se vždycky zastaví, stačí prohodit přijetí/nepřijetí
Postova věta: jazyk L je rekurzivní ⟺L i L jsou rekurzivně spočetné
důkaz ⟹
triviální
důkaz ⟸
máme TM pro L (označíme M1) i pro L (označíme M2)
pro w naráz simulujeme běh M1 i M2 v Turingově stroji M
pokud jeden z Mi přijme, M zastaví a odpoví
jazyky jsou komplementární, takže jeden z Mi vždy zastaví
Věta: Nerozhodnutelnost univerzálního jazyka
věta: Lu je rekurzivně spočetný, ale není rekurzivní
důkaz
máme TM přijímající Lu⟹Lu je rekurzivně spočetný
kdyby byl Lu rekurzivní, tak by Lu byl také rekurzivní
pro TM M přijímající Lu můžeme zkontruovat TM M′ přijímající Ld
stačí ze slova w na vstupu M′ vytvořit dvojici (w,w) a předat ji Turingovu stroji M
výsledek jeho výpočtu určí výsledek výpočtu M′
protože víme, že Ld není rekurzivně spočetný, pak Lu není rekurzivně spočetný a Lu není rekurzivní
Nerozhodnutelné problémy
Definice: Rozhodnutelný problém
problém … množina otázek (nebo spíše vstupů) kódovatelná řetězci nad abecedou Σ s odpověďmi ∈{ano,ne}
pokud problém definuji jako množinu, jde o otázku, zda vstup kóduje prvek dané množiny (např. polynom s celočíselným kořenem)
problém je (algoritmicky) rozhodnutelný, pokud existuje TM takový, že pro každý vstup w∈P TM zastaví a navíc přijme, právě když P(w)=ano (tj. pro P(w)=ne zastaví v nepřijímajícím stavu)
nerozhodnutelný problém … není rozhodnutelný
existuje analogie mezi rozhodnutelným problémem a rekurzivním jazykem
Věta: Redukce problému
definice: redukcí problému P1 na P2 nazýváme algoritmus R, který pro každou instanci w∈P1 zastaví a vydá R(w)∈P2, přičemž…
P1(w)=ano⟺P2(R(w))=ano
tedy i P1(w)=ne⟺P2(R(w))=ne
věta: existuje-li redukce problému P1 na P2, pak…
pokud P1 je nerozhodnutelný, pak je nerozhodnutelný i P2
pokud P1 není rekurzivně spočetný, pak není rekurzivně spočetný ani P2
důkaz
kdyby byl P2 rozhodnutelný (respektive rekurzivně spočetný), mohli bychom algoritmus pro převod vstupu P1 na vstup P2 zkombinovat s algoritmem pro P2, takže bychom dostali rozhodnutelný (nebo rekurzivně spočetný) algoritmus pro P1, což by byl spor
Věta: Problém zastavení není rozhodnutelný
definice: instancí problému zastavení je dvojice řetězců M,w∈{0,1}∗
definice: problém zastavení je najít algoritmus Halt(M,w), který vydá 1, právě když stroj M zastaví na vstupu w, jinak vydá 0
věta: problém zastavení není rozhodnutelný
idea důkazu: redukujeme Ld na Halt
důkaz
předpokládejme, že máme algoritmus (Turingův stroj) pro Halt
modifikujeme ho na stroj Haltno(w)
w∈{0,1}∗
pokud Halt(w,w) vrátí 1, spustíme nekonečný cyklus
jinak zastavíme
takže Haltno(w) vlastně obrací výsledek Halt(w,w)
otázka Halt(Haltno,Haltno) není řešitelná, proto algoritmus Halt nemůže existovat
Časová složitost
Definice: Časová složitost
mějme Turingův stroj M, který zastaví na každém vstupu
časová složitost M je funkce f:N→N, kde f(n) je maximální počet kroků výpočtu M nad vstupy délky n
Definice: (Asymptotická) horní hranice O(g(n))
mějme funkce f,g:N→R+
říkáme, že f(n)∈O(g(n)), pokud existují c,n0∈N+ taková, že ∀n≥n0:f(n)≤c⋅g(n)
v takovém případě říkáme, že g(n) je (asymptotická) horní granice pro f(n)
Definice: Třída časové složitosti
mějme funkci t:N→R+
definujeme třídu časové složitosti TIME(t(n)) jako množinu všech jazyků, které jsou rozhodnutelné jednopáskovým Turingovým strojem v čase O(t(n))
tj. pro vstup délky n TM vždy zastaví nejpozději po O(t(n)) a vydá správnou odpověď
lemma: Turingův stroj s časem t(n) má jednopáskový ekvivalent O(t2(n))
Definice: Doba běhu nedeterministického TM
mějme nedeterministický Turingův stroj, který zastaví na každém vstupu
doba běhu M je funkce f:N→N, kde f(n) je maximální počet kroků, který M potřebuje v jakékoliv větvi výpočtu nad jakýmkoliv vstupem délky n
o takovém nedeterministickém Turingově stroji M říkáme, že rozhoduje jazyk L(M) v čase f(n)
Věta: Převod mezi časovou složitostí pro deterministický a nedeterministický TM
věta
mějme funkci t:N→R+, přičemž t(n)≥n
každý nedeterministický Turingův stroj s časem t(n) má deterministický ekvivalent 2O(t(n))
důkaz
máme-li pro dvojici Q×Γ maximálně d variant, tak se TM po k krocích může dostat maximálně do dk konfigurací
tedy simulujeme v čase O(t(n)⋅dt(n))=2O(t(n))
Věta: CFL⊆P
definice: P (PTIME) … třída jazyků rozhodnutelných v polynomiálním čase jednopáskovým deterministickým Turingovým strojem
P=⋃kTIME(nk)
věta: každý bezkontextový jazyk patří do P
důkaz
gramatiku převedeme do Chomského normální formy (velikost nezávisí na n)
CYK algoritmus je polynomiální, konkrétně O(n3)
Definice: Verifikátor
verifikátor jazyka L je algoritmus V, kde
L={w∣V pro nějaký řetězec c přijímá ⟨w,c⟩}
nápověda c pro snadné ověření se nazývá certifikát
časová složitost verifikátoru se měří pouze vzhledem k délce w
polynomiální verifikátor rozhoduje v čase polynomiálním vzhledem k ∣w∣
jazyk L je polynomiálně verifikovatelný, pokud má polynomiální verifikátor
pak vždy existuje i polynomiální certifikát, delší by verifikátor nestihl ani přečíst
Věta: NP, NTIME
definice: NP … třída jazyků rozhodnutelných v polynomiálním čase
je tvořena jazyky s polynomiálním verifikátorem
definice: NTIME
mějme funkci t:N→R+
NTIME(t(n)) … třída jazyků rozhodnutelných nedeterministickým TM v čase O(t(n))
věta: NP=⋃kNTIME(nk)
idea důkazu
převedeme verifikátor na NTM a opačně
NTM uhodne certifikát a simuluje verifikátor
verifikátor bere prijímající větev NTM jakožto certifikát
důkaz ⟹
mějme L∈NP
hledáme NTM M
vezmeme verifikátor V z definice NP
nechť rozhoduje L v čase nk
M na vstupu w délky n
nedeterministicky uhodne řetězec c délky ≤nk
spustí V na vstupu ⟨w,c⟩
pokud V přijme, M také přijme
důkaz ⟸
mějme L rozhodnutelný NTM M v polynomiálním čase
hledáme verifikátor V
V na vstupu ⟨w,c⟩
simuluje M na vstupu w, v bodech větvení vybere větev podle c
pokud tato větev NTM přijme, V přijme
pokud všechny větve selhaly, NTM nepřijímá, tedy ani V nepřijímá
funkce f:Σ∗→Σ∗ je polynomiálně vyčíslitelná, pokud existuje Turingův stroj M, který pro každý vstup w v polynomiálním čase zastaví s f(w) na pásce
jazyk A je převoditelný v polynomiálním čase na jazyk B, značíme A≤PB, pokud existuje funkce f:Σ∗→Σ∗ vyčíslitelná v polynomiálním čase a ∀w∈Σ∗:w∈A⟺f(w)∈B
funkci f pak nazýváme polynomiální redukcí A do B
Definice: SAT, 3SAT
formule je 3-cnf, pokud je v CNF a v každé klauzuli jsou nejvýše tři literály
formule je splnitelná, existuje-li takové ohodnocení výrokových proměnných, že je hodnota formule TRUE
problém 3SAT je pro každou 3-cnf formuli rozhodnout, zda je splnitelná
problém SAT je pro každou booleovskou formuli rozhodnout, zda je splnitelná
Definice: NP úplnost
jazyk B je NP-úplný, pokud je NP a každý jazyk A∈NP je na B polynomiálně převoditelný
věta: pokud B je NP-úplný a B∈P, pak P=NP
věta: pokud B je NP-úplný a B≤PC pro nějaké C∈NP, pak C je NP-úplný
Věta: Cook-Levinova věta
věta: SAT je NP-úplný.
důkaz
SAT je NP: nedeterministický TM uhodne správné ohodnocení a v polynomiálním čase ověří, že je pro něj formule pravdivá
dále dokážeme, že je SAT NP-úplný
vezmeme libovolný L∈NP
nechť M je nedeterministický TM, který rozhoduje jazyk L v čase nk−3 pro nějaké k
uvažujeme jenom nk−3 kvůli šířce tabulky – aby hlava nemohla vyjet ven
pro jednoduchost uvažujeme NTM s jednostrannou páskou
vytvoříme tabulku nk×nk, každý řádek odpovídá konfiguraci M na vstupu w
tabulku „dláždíme“ okénky širokými 3 buňky a vysokými 2 buňky
na základě přechodové funkce δ jsou povoleny jen určité typy okének
pokud tabulku vydláždíme jen povolenými okénky, každý řádek bude odpovídat legální konfiguraci TM dosažitelné jedním krokem z předchozího řádku
nedeterminismus se schová v SATu
z tabulky vytvoříme formuli ϕ=ϕcell∧ϕstart∧ϕmove∧ϕaccept
ϕcell povoluje pro každé políčko tabulky právě jedno písmeno
ϕstart definuje počáteční konfiguraci pro vstup w
ϕmove popisuje povolené kroky (okénka)
ϕaccept je disjunkce přes přítomnost přijímajícího stavu v libovolné buňce tabulky
tvrzení: převod má polynomiální složitost, konkrétně O(n2klogn)
Věta: 3SAT je NP-úplný
použijeme důkaz Cook-Levinovy věty
je potřeba prevést okénka pohybu do CNF
stačí konstantní čas – velikost podformule závisí na stroji, nikoliv na délce vstupu
dlouhé klauzule rozdělíme zavedením nových proměnných
co-NP, prostorová složitost
Věta: Problém tautologičnosti je co-NP
definice: jazyk L⊆Σ∗ patří do třídy co-NP, právě když jeho doplněk Σ∗−L patří do NP
P je částí NP i co-NP
domníváme se, že NP-úplné problémy nejsou v co-NP (pokud P = NP, tak jsou)
definice: problém, zda je výroková formule tautologie, nazýváme tautologičnost (TAUT)
věta: problém tautologičnosti je co-NP
důkaz z pozorování, že doplněk TAUT (do množiny korektních formulí) je snadno převoditelný na SAT a SAT je v NP
doplněk TAUT
existuje ohodnocení, pro které je formule FALSE?
je negace formule splnitelná?
doplněk SAT
je negace formule tautologie?
Definice: Prostorová složitost
pro deterministický Turingův stroj M, který zastaví na každém vstupu, je prostorová složitost M funkce f:N→N, kde f(n) je maximální počet buněk pásky, které M přečte při jakémkoliv vstupu délky n
pro nedeterministický Turingův stroj M, jehož všechny větve výpočtu zastaví na každém vstupu, je prostorová složitost M funkce f:N→N, kde f(n) je maximální počet buněk pásky, které M přečte při jakémkoliv vstupu délky n na libovolné větvi výpočtu
Definice: Třídy prostorové složitosti
mějme funkci f:N→R+
definujeme třídy prostorové složitosti SPACE(f(n)) a NSPACE(f(n))
SPACE(f(n)) … třída jazyků rozhodnutelných v prostoru O(f(n)) deterministickým TM
NSPACE(f(n)) … třída jazyků rozhodnutelných v prostoru O(f(n)) nedeterministickým TM
Věta: Savitchova věta
věta: pro libovolnou funkci f:N→R+, pro kterou f(n)≥n, platí NSPACE(f(n))⊆SPACE(f2(n))
důkaz
nestačí NTM simulovat přímo, to bychom potřebovali prostor 2O(f(n))
v kvadratickém čase vyřešíme problém dosažitelnosti (CANYIELD)
„je v NTN z konfigurace c1 dosažitelná konfigurace c2 v maximálně t krocích a maximálně používající prostor f(n)?“
metoda rozděl a panuj
za c1 vezmeme počáteční konfiguraci, za c2 přijímající
simulujeme NTM pomocí TM v kvadratickém prostoru
NTM modifikujeme, aby se před přijetím „vynuloval“ (smazal pásku a posunul se na nejlevější políčko)
sloučíme přijímající stavy do jednoho
tím máme jednoznačnou přijímající konfiguraci
najdeme d maximální počet štěpení konfigurace v jednom kroku, tj. horní odhad pro počet konfigurací
je to 2d⋅f(n)
tak získáme i horní odhad času běhu libovolné větve
složitost simulace
CANYIELD potřebuje ukládat konfigurace a t, tj. O(f(n)) prostoru
počet volání CANYIELD je logaritmický vzhledem k t=2d⋅f(n)
hloubka rekurze je O(log(2d⋅f(n))), tedy O(f(n))
celkem O(f(n))⋅O(f(n))=O(f2(n)) prostoru
potřebujeme znát f(n), ale to nevadí, můžeme zkoušet postupně od jedničky nebo přidat do předpokladu, že NTM rozhoduje jazyk v prostoru f(n)
Definice: PSPACE
PSPACE … třída jazyků rozhodnutelných v polynomiálním prostoru deterministickým Turingovým strojem
PSPACE=⋃k∈NSPACE(nk)
NPSPACE ani nedefinujeme, protože NPSPACE = PSPACE, podle Savichovy věty
Věta: Prostorové a časové třídy
věta: P⊆NP⊆PSPACE=NPSPACE⊆EXPTIME=⋃kTIME(2nk)
P⊆PSPACE, respektive NP⊆NPSPACE
stroj v čase t(n) navštíví maximálně t(n) políček, proto pro t(n)≥n stačí prostor t(n)
PSPACE⊆EXPTIME
pro f(n)≥n dosáhne TM M pracující v prostoru f(n) maximálně f(n)⋅2O(f(n)) různých konfigurací
v konečném deterministickém výpočtu se žádná konfigurace neopakuje, proto existuje TM M′ simulující M v čase f(n)⋅2O(f(n))