CIS 262 jazyky - CIS 262-UPENN

Úvod do teorie výpočtu

Jean GallierDepartment of Computer and Information ScienceUniversity of Pennsylvaniaphiadelphia, PA 19104, USAe-mail:[email protected]

©C Jean Gallierprosím, nereprodukujtebez souhlasu autora

Březen 5, 2020

4 obsah

6.4 Čerpací Lemma
6.5 rychlý algoritmus pro kontrolu ekvivalence stavu
7 bezkontextových gramatik a jazyků
7.1 bezkontextové gramatiky
7.2 derivace a bezkontextové jazyky
7.3 normální formy pro bezkontextové gramatiky
7.4 regulární jazyky jsou bezkontextové
7.5 zbytečné produkce v bezkontextových gramatikách
7.6 Greibachova normální forma
7.7 nejméně pevné body
7.8 bezkontextové jazyky jako nejméně pevné body
7,9 nejméně pevných bodů a greibachova normální forma
7.10 stromových domén a Gornových stromů
7.11 derivační stromy
7.12 Ogdenova Lemma
7.13 Pushdown automaty
7.14 od bezkontextových gramatik k PDA
7.15 od PDA k Bezkontextovým Gramatikám
7.16 Chomsky-Schutzenbergerova věta
8 A Survey ofLR-Parsing Methods
8.1 LR(0)-charakteristické automaty
8.2 Shift/Reduce analyzátory
>
8.3 výpočet prvního
8.4 intuice za algoritmem Shift/reduce
8.5 metoda grafu pro výpočet pevných bodů
8.6 výpočet následného
8.7 Algoritmtraverse
8.8 více onLR (0)-charakteristické automaty
8.9 LALR(1) – Lookahead sady
8.10 výpočetní první, následovat, atd. za přítomnostiǫ-pravidel
8.11 LR (1)-charakteristické automaty

Úvod

teorie výpočtu se zabývá algoritmy a algoritmickými systémy: jejich návrh a reprezentace, jejich úplnost a jejich složitost.

účelem těchto poznámek je představit některé základní pojmy teorie komputace, včetně konceptů z formálních jazyků a teorie automatů, teorie komputovatelnosti, některé základy teorie rekurzivních funkcí a úvod do komplexityteorie. Další témata, jako je korektnost programů, se zde neobjeví (prostě není dost času!).

poznámky jsou rozděleny do tří částí. První část je věnovánaformální jazykya automaty. Druhá část se zabývá modely výpočtu, rekurzivními funkcemi a neschůdností. Třetí část se zabývá výpočetní složitostí, zejména třídypandnp.

5

Základy teorie formálního jazyka

2.1 Přehled některých základních matematických notací a

N,Z,Q,R, C.

Pakpřírodní čísla, N={ 0 , 1, 2 ,…}.

Theintegers, Z={…,− 2 ,− 1 , 0 , 1 , 2 ,…}.

Therationals,

{

|p, q∈Z, q 6 = 0

}

null

Thereals, R. Thecomplexní čísla, C={a+ib / a, b∈R}.

vzhledem k jakémukoli setX, thepower setofXis sada všech podmnožin ofxa je označena 2X. notace f: X→Y

označuje afunkciwithdomainxandrange(orcodomain)y.

graph(f) ={(x,f (x)} / x∈X}⊆X×Y

je graf.

7 8 Kapitola 2. Základy teorie formálního jazyka

Im (f) =f (X) ={y∈Y |x x X X, y=f (x)} Y Y

je theimageoff.

obecněji, ifA X X, pak

f (A) ={y∈Y / x x A A, y=f (x)} Y Y

je (přímý) obraz.

IfB Y Y, pak f-1 (B) ={x∈X|f(x)∈B} X X

je inverzní obraz (orpullback) ofB.

f− 1 (B) je množina; může být prázdná i ifB 6 =∅.Vzhledem k tomu, dvě funkcef: X→Y andg: Y→Z, functiong◦f:X→Zgiven by

(g◦f)(x) =g(f(x)) pro allx X X

je složeníoffandg.

funkce idX: X→Xgiven by

idX(x) =x pro allx∈X

je funkce(ofX).

a funkcef:X→Y isinjektivní(stará terminologie jedna ku jedné)pokud pro všechny x 1 ,x 2 ∈X,

iff(x 1) =f (x 2), pakx 1 =x 2 ;

ekvivalentně ifx 16 =x 2, thenf (x 1) 6 =f(x 2 ).

fakt: IfX 6 =∅(a soY 6=∅), functionf: X →Y je injektivní iff existuje functionr: Y →X (aleft inverzní) taková, že

r◦f= idX.

Poznámka:ris surjective.Functionf: X→Y isurjective (stará terminologie)pokud pro spojence∈Y existuje nějakýchx∈Xtakový thaty=f(x), ifff (X) =Y.

fakt: IfX 6 =∅(a soY 6=∅), functionf: X→Y je surjective iff existuje funkce: Y →X (přímá inverseorsekce) taková, že

f◦s= idY.

10 Kapitola 2. ZÁKLADY FORMÁLNÍCH JAZYKŮ, TEORIE

relationR⊆X×Xissymmetricif pro allx,y∈X, pokud (x,y)∈R, pak (y,x)∈R

relationR⊆X×X symetrický iffR− 1 ⊆R

GivenR⊆X×X(vztah onX), defineRnby

R 0 =IXRn+1=R◦Rn.

Thetranstive closureR+ofRis daný

R+=

⋃

n≥ 1

Rn.

fakt.R+je nejmenší přechodná relace obsahujícír.

Thereflexivní a transitive closureR∗ofRis daný

R∗=

⋃

n≥ 0

Rn=R+IX IX.

fakt.R∗je nejmenší transitivní a reflexní relace obsahující r.

vztah⊆X×XJE vztah anekvivalence, pokud je reflexní, symetrický a tranzitivní.

fakt. Nejmenší vztah ekvivalence obsahující vztahr X X×XJE dán

(R∪R− 1 )∗.

a relationR X X×Xisantisymetricif pro allx,y∈X, if (x, y)R Rand(y, x) R R, thenx=y.

a relationR X X×Xis apartial order if it is reflexive, transitive, and antisymmetic.

částečný řádr ⊆X×X je celkové pořadí, pokud pro allx, y ∈X,buď (x, y) either Ror (y,x)∈R.

2.2 abecedy, řetězce, jazyky

náš pohled na jazyky je tojazyk je sada řetězců. Na druhé straně je řetězec konečnýsekvence písmen z nějaké abecedy. Tyto pojmy jsou definovány přísně následovně.

definice 2.1.AnalphabetΣ je anyfiniteset.

2.2. Abecedy, řetězce, jazyky 11

často píšeme Σ ={a 1,…, ak}. Asymboly abecedy se nazývají asymboly.Příklad:Σ ={a}Σ ={a,b, c}Σ ={ 0, 1 }Σ ={α, β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ,}} řetězec je konečná posloupnost symbolů. Technicky je vhodné definovat řetězce jakofunkce. Pro jakékoli číslo≥1, nechť

={ 1 , 2 ,…,n},

a forn= 0, let =∅.

definice 2.2. Vzhledem k abecedě Σ, astring overΣ (nebo jednoduše řetězec) délky nisany funkce

u: →Σ.

integernis thelengthhof strunu, a to je označeno jako|u|. Kdyn= 0, pakspeciální řetězec: →Σ délky 0 se nazývá prázdný řetězec nebo nulový řetězec a označuje se jakoǫ.

vzhledem k tomu, strunu: →Σ délky≥1,u(i) je thei-th písmeno v strunu. Pro sim-plicitu notace píšeme místo ofu(i) a označujeme strunu=u(1)u(2)···u(n)jako

u=u 1 u 2 * * * un,

s každýmui Σ Σ.

například pokud Σ ={a, b}andu: →Σ je definováno tak,že(1) =a,u(2) =b, andu (3) =a, píšeme=aba.

další příklady řetězců jsou

práce, zábava, gabuzomeuh

řetězce délky 1 jsou functionsu: →Σ jednoduše vybíráte nějaký elementu(1) =Aiin Σ.Identifikujeme tedy každý symbolai Σ Σ s odpovídajícím řetězcem délky 1.

množina všech řetězců nad abecedou Σ, včetně prázdného řetězce, je označena jako Σ∗.

2.2. Abecedy, řetězce, jazyky 13

pro základní casen= 0, sinceu 0 =ǫ, máme

u 0 u =uu=u = uǫ=uu 0.

pro indukční krok máme

un+1u= (unu)u podle definice ofun+ = (uun)u podle indukční hypotézy =u(unu) asociativitou =uun + 1 podle definice ofun+1.

definice 2.4.Vzhledem k abecedě Σ, vzhledem k libovolným dvěma řetězcům, v Σ Σ∗definujeme následující významy takto:

uje předpona různé existuje něco∈Σ∗takové, že

v = uy.

uje přípona rozdíl existuje nějakýchx Σ Σ∗takové, že

v=xu.

uis a substring ofviff existují somex, y Σ Σ∗takové, že

v=xuy.

říkáme, žeje správná předpona (přípona, podřetězec) ofviffuje předpona (přípona, podřetězec)ofvandu 6 =v.

například gaje předpona ofgabuzo,zois přípona ofgabuzoandbuzis podřetězec ofgabuzo.Připomeňme, že částečné uspořádání≤ na množinách je binární vztah≤ S S×S, který je reflexní, tranzitivní a antisymetrický.

pojmy prefix, přípona a podřetězec definují binární vztahy na Σ∗v pravém slova smyslu. Lze ukázat, že tyto vztahy jsou částečné objednávky.

dalším důležitým uspořádáním řetězců je lexikografické (nebo slovníkové) uspořádání.

definice 2.5. Vzhledem k abecedě Σ ={a 1 ,…, ak}předpokládal totálně objednané takové, že 1 < a 2 <···< ak, vzhledem k libovolným dvěma řetězcůmsu, v Σ Σ∗, definujemelexikografické uspořádánítakto:







(1) ifv=uy, pro somey Σ Σ∗, nebo (2)ifu=xaiy, v=xajz, ai< aj, withai, aj Σ Σ a pro someyx, y, z Σ Σ∗.

14 Kapitola 2. Základy teorie formálního jazyka

myšlenka je, že jsme scanuandvsimultually zleva doprava, porovnáním thsymboluminuto themth symbolvminv, počínaje SM= 1. Pokud nevznikne žádný rozpor, thatis, if them-TH symboluminuagrees with them-TH symbolvminvform= 1,…,| u/, pak je předpona a prohlašujeme, že předchází lexikografickému uspořádání. V opačném případě na chvíli volíme společnou předponu(případně prázdný řetězec) a pak je zde aleftmost rozpor, což znamená, že je forma=xaiyandvis zformv=xajz, Sai 6 =aj (andx, y, z Σ Σ∗libovolná). Pak musíme přerušit kravatu ak tomu použijeme skutečnost, že symbolya1 < a 2 <···< ak se předpokládá ,že je (úplně)uspořádáno, takže vidíme, který zaiandaj přijde první, sayai< aj, a prohlašujeme thatu=xaiyprecedesv=xajzin lexikografické uspořádání.

Všimněte si, že případy (1) a (2) se vzájemně vylučují. V případě (1), uje předpona ofv. V případě (2) v6uandu 6 =v.

například abb, gallhagergallier.

je poměrně zdlouhavé dokázat, že lexikografické uspořádání je ve skutečnosti zvláštní uspořádání.Ve skutečnosti se jedná o totální uspořádání, což znamená, že pro jakékoli dva struny, v Σ Σ∗, buďtouv, orvu.

existuje řetězec, který je indukčně definován takto:

ǫR=ǫ, (ua)R=auR,

kde∈Σ Andu∈Σ∗.

například reillag=gallierR.

settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa, dostaneme

aR= (ǫa)R=aǫR=aǫ=,

namelyaR=neboť alla∈Σ.

může být ukázáno indukcí na / v/, že

(uv)R=vRuR.

užitečný trik, který omezuje těžkopádnou notaci při indukci na strunáchje pozorování, že anonempty stringw Σ Σ∗délky + 1( n≥0) lze zapsat jako

w=UA, pro someu Σ Σ∗a některé symbola Σ Σ, s|u/ = n.

16 Kapitola 2. Základy teorie formálního jazyka

pokudnení to prázdná množina, sincef: X→Nis injection iff existuje surjectionr: N→Xtak thatr◦f= idX, setxje počítatelný iff existuje asurjectionfromNontoX.

fakt. Lze ukázat, že setx je počítatelný, pokud je buď konečný, nebo pokud je v bijectionwithN (v tomto případě je nekonečný).

uvidíme později thatn×NIS počitatelné. V důsledku toho je množina racionálních číselje spočitatelná.

množina je nespočitatelná, pokud není počítatelná.

například R (množina reálných čísel) je nespočetná.Podobně

(0,1) ={x R R / 0 < x < 1 }

je nespočetný. Nicméně, tam je bijekce mezi (0,1) andR (najít jeden!) Množina 2 ze všech podmnožin nespočetných. Toto je zvláštní případ Cantorovy teoriediskutováno níže.

Předpokládejme|Σ|=kwith Σ ={a 1 ,…, ak}. Za prvé, všimněte si, že existujístruny délkya(kn+1-1)/(k−1) řetězce délky nanejvýš Σ; kdyk= 1, druhý vzorecby měl být nahrazen byn+ 1. Protože řetězec je funkce:{ 1,…, n} →Σ, pakpočet řetězců délkyje počet funkcí od{ 1,…, n}na Σ a od té dobykardinalita Σ isk, existují takové funkce (To se okamžitě projeví indukcí onn). Pak počet řetězců délky maximálně

1 + K+k 2 +···+kn.

pokud k = 1, toto číslo je n+ 1, a pokud k ≥ 2, jako součet geometrické řady, je to(kn+1-1)/(k-1−.

Pokud Σ 6 =∅, pak množina Σ∗všech řetězců nad Σ je nekonečná a spočitatelná, jak nyní ukazujemkonstrukcí explicitní bijekce z Σ∗ontoN.

Ifk= 1 writea=a 1, a pak

{a}∗={ǫ, a, aa, aaa,…,účetní,…}.

máme bijectionn7→anfromNto{a}∗.Ifk≥2, pak si můžeme představit řetězec

u=ai 1 ···ain

jako reprezentaci integerv(u) v basekshifted by (kn−1)/(k−1), s

2.2. Abecedy, řetězce, jazyky 17

ν (u) =i 1 kn-1 +i 2 kn− 2 +···+v-1 k+v

kn-1 k− 1

(i 1-1) kn− 1 +···+ (v-1 -1) k + v-1.

(a withv (ǫ) = 0), kde 1≤ij≤kforj= 1,…, n.

necháme to jako cvičení, abychom to ukázaliv: Σ∗→Nis a bijection. Najít implicitně (to je vzorec) pro inverzní jev překvapivě obtížné.

ve skutečnosti ν odpovídá výčtu Σ∗kde uprecedesv if / u / < / v|, auprecedesvin lexikografické uspořádání if|u|=|v|. Je snadné zkontrolovat, zda je výše uvedené (uprecedesv) celkové pořadí.

například ifk= 2 a pokud píšeme Σ ={a, b}, pak výčet začíná

ǫ, 0a,b, 1,2 , aa ,ab, ba, bb, 3,4 , 5 , 6 , aaa ,aab, aba, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

Chcete-li získat další řádek, zřetěztenalevo a pak zřetězitnalevo. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

funguje to!

na druhé straně, Pokud Σ 6 =∅, je množina 2Σ ∗ všech podmnožin Σ∗(všechny jazyky) nespočitatelná.Ve skutečnosti můžeme ukázat, že neexistuje žádná surjekce znonto 2Σ ∗ nejprve to ukážemeneexistuje žádná surjekce z Σ∗na 2Σ∗. Toto je zvláštní případ Cantorovy věty.Tvrdíme, že pokud neexistuje surjekce z Σ∗na 2Σ ∗, pak neexistuje surjekce znonto 2Σ∗.

důkaz. Předpokládejme protikladem, že existuje surjectiong: N→ 2 Σ ∗ . Ale pokud Σ 6 =∅, pakσ∗je nekonečná a spočitatelná, máme tedy bijectionv: Σ∗→n. Pak kompozice

Σ ν ν / / N

g / / 2 Σ ∗

je surjekce, protože bijectionvis surjekce, gis surjekce a compositionof surjekce je surjekce, což je v rozporu s hypotézou, že neexistuje žádná surjekce zσ∗na 2Σ ∗ .

2.3. Operace na jazycích 19

2.3 operace na jazycích

způsob, jak vytvářet složitější jazyky z jednodušších jazyků, je kombinovat je pomocí různých operací. Nejprve přezkoumáme množinové teoretické operace spojení, křižovatky adoplnění.

vzhledem k nějaké abecedě Σ je pro libovolné dva jazyky L 1, L 2 lomeno Σ ,theunionL 1 L L 2 ofL 1andL 2 jazykem

L 1 L L 2 ={w Σ Σ Σ|w Σ L 1 nebo w∈L 2 }.

TheintersectionL 1 L L 2 ofL 1 andL 2 je jazyk

L 1 L L 2 ={w Σ Σ Σ / w w L 1 A w∈L 2 }.

rozdíl 1-L 2 ofL 1 andL 2 je jazyk

L 1-L 2 ={w Σ Σ Σ / w∈L 1 A w / ∈L 2 }.

rozdíl se také nazývárelativní doplněk.

zvláštní případ rozdílu se získá, když 1 = Σ∗, v tomto případě definujeme jazyk complementlof a

L={w Σ Σ∗/w / w l}.

výše uvedené operace nepoužívají strukturu řetězců. Používají se následující operacekatenace.

definice 2.8.Vzhledem k abecedě Σ je pro libovolné dva jazyky L 1, L 2 lomeno Σ konkatenacel 1 L 2 ofL 1 andL 2 jazykem

L 1 L 2 ={w Σ Σ Σ|u u L L 1 ,v v v L 2, w=uv}.

pro jakýkoli jazyk definujemetakto:

L 0 ={ǫ}, Ln+1=LnL (n≥0).

nastavením n= 0 inLn+1=LnL, sinceL 0 ={ǫ}, dostaneme

L 1 =L0+1=L 0 L={}} L=L,

soL 1 =L.

20 Kapitola 2. ZÁKLADY FORMÁLNÍCH JAZYKŮ, TEORIE

následující vlastnosti jsou snadno ověřit:

L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L,(L 1 ∪{ǫ})L 2 =L 1 L 2 ∪L 2 ,L 1 (L 2 ∪{ǫ}) =L 1 L 2 ∪L 1 ,LnL=LLn.

Obecně platí, že L 1 L 26 =L 2 L 1.So operace, které jsme zavedli, kromě doplnění (sinceL= Σ∗ – Lis nekonečný ifLis konečný a Σ je neprázdný), zachovávají konečnost jazyků. To není případ pro další dvě operace.

definice 2.9.Vzhledem k abecedě Σ, pro jakýkoli jazyk Σ, theKleene∗ – closureL∗ofLis jazyk

L∗=