CIS 262 languages - CIS 262 - UPENN

Introduction to the Theory of Computation

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

©c Jean Gallierprosimy, nie powielaj bez zgody autora

marzec 5, 2020

4 spis treści

6.4 Lemat pompujący
6.5 szybki algorytm sprawdzający równoważność stanu
7 gramatyki i języki bez kontekstu
7.1 gramatyki bez kontekstu
7.2 pochodne i języki bez kontekstu
7.3 formy normalne dla gramatyk bez kontekstu
7.4 języki regularne są wolne od kontekstu
7.5 bezużyteczne produkcje w gramatykach bez kontekstu
7.6 Greibach normalna forma
7.7 najmniej stałych punktów
7.8 języki wolne od kontekstu jako najmniej stałych punktów
7.9 najmniej stałych punktów i postać normalna Greibacha
7.10 domeny Drzew i Drzewa Gorn
7.11 drzewa pochodne
7.12 Lemat Ogdena
7.13 automaty Pushdown
7.14 od gramatyki bez kontekstu do gramatyki bez kontekstu
7.15 od gramatyki bez kontekstu
7.16 twierdzenie Chomsky ’ ego-Schutzenbergera
8 badanie metod parsowania lr
8.1 LR(0)-Automatyka charakterystyczna
8.2 parsery Shift/reduce
8.3 obliczanie pierwszego
8.4 intuicja stojąca za algorytmem Shift/reduce
8.5 metoda Wykresów do obliczania punktów stałych
8.6 Obliczanie follow
8.7 algorithmtraverse
8.8 Więcej onLR(0)-charakterystyczne automaty
8.9 LALR(1)-Zestawy Lookahead
8.10 Obliczanie pierwszy, śledzić, itp. w Obecnościǫ-reguły
8.11 LR (1) – automaty charakterystyczne

wprowadzenie

teoria obliczeń dotyczy algorytmów i systemów algorytmicznych: ich projektowania i reprezentacji, ich kompletności i złożoności.

celem tych notatek jest wprowadzenie niektórych podstawowych pojęć teorii obliczeniowej, w tym pojęć z języków formalnych i teorii automatów, teorii komputeryzacji, niektórych podstaw teorii funkcji rekurencyjnych oraz wprowadzenie do kompleksowości. Inne tematy, takie jak poprawność programów, nie będą tutaj poruszane (nie ma justisn wystarczająco dużo czasu!).

notatki są podzielone na trzy części. Pierwsza część poświęcona jest językom formalnym i automatom. Druga część zajmuje się modelami obliczeń, funkcjami rekurencyjnymi i rozwiązywalnością. Trzecia część dotyczy złożoności obliczeniowej, w szczególności klasyspandnp.

5

Podstawy teorii języka formalnego

2.1 Przegląd niektórych podstawowych notacji matematycznych i

N,Z,Q,R,C.

następnie liczby, N={ 0 , 1 , 2 ,…}.

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

{

/ p, q∈Z, q 6 = 0

}

null

, R. Liczby zespolone, C={a+ib / A, b∈R}.

biorąc pod uwagę dowolny setX, thepower setofXis zbiór wszystkich podzbiorów Xand jest oznaczony 2X. notacja f: X→Y

oznacza afunctionwithdomainXandrange (orcodomain)Y.

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

jest thegraphoff.

7 8 Rozdział 2. Podstawy formalnej teorii języka

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

to theimageoff.

ogólnie rzecz biorąc, ifA⊆X, następnie

f(A) ={y∈Y |∃x∈a, y=f(x)}⊆Y

jest(bezpośrednim) imageofA.

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

jest odwrotnym obrazem (lub zwrotem) ofB.

f-1 (B) jest zestawem; może być pusty nawet jeślib 6=∅.Biorąc pod uwagę dwie funkcje:X→Y i G:Y→Z, funkcja◦f:X→Zgiven by

(g◦f)(x) =G(f(x)) dla wszystkich X∈X

jest składnikiem zandg.

funkcja idX:X→Xgiven by

idX(x) =X for allx∈X

jest funkcją(ofX).

a functionf: X→Y isinjective (stara terminologia)if for allx 1 ,x 2 ∈X,

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

równoważnie ifx 16 =x 2, thenf (x 1 ) 6 = f (x 2).

fakt: IfX 6 = ∅(i soY 6=∅), funkcja F: X →Y jest iniekcyjna iff istnieje funkcja R: Y →X (odwrotność aleft) taka, że

r◦f= idX.

Uwaga: ris surjective.A functionf: X→Y issurjective (stara terminologia)if for ally∈y, there is somex∈Xsuch thatty=f(x), ifff(X) =Y.

Fact: IfX 6 =∅(and soY 6 =∅), A functionf:X→Y issurjective iff there is a functions:Y →X(arright inverseorsection) such that

f◦s= Idy.

10 Rozdział 2. Podstawy formalnej teorii języka

GivenR⊆X×X(a onx po stosunku), defineRnby

P 0 =IXRn+1=P◦ph.

thetranstive closureR+ofRis given by

R+=

⋃

N≥ 1

Rn.

fakt.R+jest najmniejszą relacją przechodnią zawierającą r.

Tamfleksyjny i przechodni closureR

R∗=

⋃

n≥ 0

Rn = R + ∪IX.

fakt.R∗jest najmniejszą relacją przechodnią i refleksyjną zawierającą r.

a relationR⊆X×X jest relacją równoważności, jeśli jest refleksyjna, symetryczna i przechodnia.

fakt. Najmniejsza relacja równoważności zawierająca relację r⊆X×Xis dana przez

(R∪R− 1 )∗.

a relationR⊆X×Xisantisymmetricif for allx,y∈X, if (x,y) R Rand (y,x) R R,thenx=y.

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

częściowa kolejność r ⊆X×X jest sumaryczną kolejnością,jeśli dla allx, y ∈X,either (x,y) R Ror(y, x)∈ R.

2.2 alfabety, ciągi znaków, języki

nasz pogląd na języki jest taki, że język jest zbiorem ciągów znaków. Z kolei ciąg jest skończonymsekwencja liter z jakiegoś alfabetu. Pojęcia te definiowane są rygorystycznie w następujący sposób.

definicja 2.1.AnalphabetΣ jest anyfiniteet.

2.2. Alfabety, ciągi znaków, języki 11

często piszemy Σ ={a 1,…, ak}. Te znaki alfabetu są nazywane symbolami alfabetu.Przykłady:Σ = {a} Σ = {a, b, c} Σ = {0 ,1} Σ = {α,β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ, ζ}ciąg jest skończonym ciągiem symboli. Technicznie, wygodne jest definiowanie ciągów jakofunkcje. Dla dowolnej liczby całkowitej≥1, niech

={ 1 , 2 ,…, n},

and forn= 0, let =∅.

definicja 2.2. Dany Alfabet Σ, ciąg nadσ (lub po prostu ciąg) długości funkcji

u: → Σ.

liczba całkowita jest długością stringu i jest oznaczona jako|u|. Gdyn= 0, ciąg specjalny: → Σ o długości 0 nazywa się ciągiem zerowym lub ciągiem zerowym i oznacza się goǫ.

biorąc pod uwagę stringu: →Σ o długościn≥1,u(i) jest literą w stringu. Dla sim-pliczności notacji,piszemy zamiast ofu(i) i oznaczamy stringu=u(1)u(2)···u(N)jako

u=u 1 u 2 ···un,

z każdymui Σ.

na przykład, jeśli Σ ={a,b}andu: →Σ jest zdefiniowane w taki sposób,żeu(1) =A, u(2) =B, andu(3) =a, piszemy=Aba.

inne przykłady ciągów to

work, fun, gabuzomeuh

ciągi o długości 1 są funkcjami: →Σ Po prostu wybierając jakiś element(1) =Aiin Σ.W ten sposób będziemy identyfikować każdy symbol∈Σ z odpowiadającym mu ciągiem długości 1.

zbiór wszystkich ciągów nad alfabetem Σ, łącznie z pustym ciągiem,jest oznaczany jako Σ∗.

2.2. Alfabety, ciągi, języki 13

dla bazy casen= 0, ponieważ 0 =ǫ, mamy

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

dla kroku indukcyjnego mamy

un + 1U = (unu)u z definicji ofun+ = (uun) u z hipotezy indukcyjnej =u(unu) z asocjacji =uun+1 z definicji ofun+1.

definicja 2.4.Biorąc pod uwagę Alfabet Σ, biorąc pod uwagę dowolne dwa stringi, V∈Σ define definiujemy następujące wyrażenia w następujący sposób:

uis a prefiks ofviff there is somey∈Σ∗such that

v=uy.

uis a sufiks ofviff there is somex Σ Σ∗sufiks that

v=xu.

uis a substring ofviff there are somex, y∈Σ∗such that

v=xuy.

mówimy, że jest to właściwy prefiks (sufiks, podłańcuch) viffuis a prefiks (sufiks,podłańcuch)vandu 6 =v.

na przykład gais a prefiks gabuzo,zois a sufiks gabuzo andbuzis a substring ofgabuzo.Przypomnijmy, że częściowe uporządkowanie≤ na zbiorze jest relacją binarną≤⊆ s×S, która jest elastyczna, przechodnia i antysymetryczna.

koncepcje prefiksu, przyrostka i podłańcucha definiują relacje binarne na Σ∗w sposób oczywisty. Można wykazać, że relacje te są częściowymi porządkami.

kolejnym ważnym uporządkowaniem ciągów jest uporządkowanie leksykograficzne (lub słownikowe).

definicja 2.5. Dany alfabet Σ = {a 1 ,…, AK} Załóżmy, że totalnie zamówił takie thata 1 < a 2 <···< ak, biorąc pod uwagę dowolne dwa stringi, v Σ Σ∗, definiujemy następujące uporządkowanie:







(1) ifv=uy, dla somey∈Σ∗, lub (2) ifu=xaiy,v = xajz,ai< AJ,withai,AJ Σ Σ, oraz dla somex,y,z∈Σ∗.

14 Rozdział 2. Podstawy teorii języka formalnego

chodzi o to, że skanujemy ivsymultajnie od lewej do prawej, porównując jesymboluminutowy symbol vminv, zaczynając od M= 1. Jeśli nie pojawi się rozbieżność, thatis, if them-TH symboluminuagrees with them-TH symbolvminvform= 1,…, / u/, wtedy jest prefiksem V i deklarujemy, że jest zapisany w porządku leksykograficznym. W przeciwnym razie, przez jakiś czas, przez jeden wspólny przedrostek (być może pusty ciąg), a następnie istnieje największa rozbieżność, co oznacza, że jest to formulu=xaiyandvis formulv=xajz,Zai 6 =AJ(andx,y, z∈Σ Σ dowolne). Następnie musimy zerwać krawat, a do tego używamy faktu, że symbolsa 1 < a 2 <···< zakłada się, że ak jest (całkowicie)uporządkowany, więc widzimy, który z nich jest pierwszy, sayai< aj i deklarujemy, że u=xaiyprecedesv=xajzin kolejność leksykograficzna.

zauważ, że przypadki (1) i (2) wzajemnie się wykluczają. W przypadku (1) uis przedrostek ofv. W przypadku (2) v6uandu 6 =v.

na przykład abb, gallhagergallier.

dość żmudne jest udowodnienie, że porządkowanie leksykograficzne jest w rzeczywistości porządkowaniem jednostkowym.W rzeczywistości jest to kolejność całkowita, co oznacza, że dla dowolnych dwóch stringsu, V∈Σ∗, eitheruv, orvu.

różnie zdefiniowano stringwis indukcyjnie w następujący sposób:

rr=ǫ,(ua)R=auR,

gdzie Σ Σ Andu∈Σ∗.

na przykład reillag=gallierR.

w settingu=ǫin (Ukr.) P=aury

sinceǫR=ǫanda=ǫa, otrzymujemy

ar= (ǫa)P=aǫR=aǫ=a,

namelyaR=афор Alla∈Σ.

można wykazać przez indukcję na|v|, że

(uv)R=vRuR.

przydatna sztuczka, która zmniejsza uciążliwą notację podczas wykonywania indukcji na stringjest obserwacja, że anonempty stringw Σ Σ∗o długościn+ 1 (N≥0) może być zapisana jako

w=ua, dla someu Σ Σ∗i niektórych symboli Σ Σ, z|u|=N.

16 Rozdział 2. Podstawy teorii języka formalnego

IfXis nie jest pustym zbiorem, sincef: X→Nis injection iff there is a surjectionr: N→Xsuch thatr◦f = idX, the setxis countable iff there is asurjectionfromNontoX.

fakt. Można wykazać, że zbiór jest policzalny, jeśli albo jest skończony, albo jest w dwujęzyczności (w takim przypadku jest nieskończony).

zobaczymy później thatn×Nis policzalne. W konsekwencji zbiór liczb wymiernych jest policzalny.

zestaw jest nie do przeliczenia, jeśli nie jest policzalny.

na przykład R(zbiór liczb rzeczywistych) jest niepoliczalny.Podobnie

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

jest niezliczone. Istnieje jednak bijekcja pomiędzy(0,1) andR (Znajdź jeden!) Zbiór 2NO wszystkich podzbiorów zbioru uncountable. Jest to szczególny przypadek twierdzenia Cantora omówionego poniżej.

|Σ|=kwith Σ ={a 1 ,…, ak}. Po pierwsze, należy zauważyć, że istnieją ciągi o długości (kn+1-1)/(k−1) ciągi o długości co najwyżej Σ; gdyk= 1, drugi wzór należy zastąpić przezyn+ 1. Rzeczywiście, ponieważ ciąg jest funkcją: {1 ,…, n} →Σ, wtedy liczba ciągów długości jest liczbą funkcji od{ 1 ,…, N}do Σ, a od momentu powstania Σ isk istnieją takie funkcje (Jest to natychmiast pokazane przez indukcję onn). Wtedy liczba ciągów o długości co najwyżej

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

jeśli k = 1, liczba ta wynosi n+ 1, a jeśli K ≥ 2, jako suma szeregu geometrycznego, to jest(kn+1-1)/(k−1).

jeśli Σ 6=∅, to zbiór Σ∗wszystkich ciągów nad Σ jest nieskończony i policzalny, jak teraz pokazujemy konstruując jednoznaczną bijekcję z Σ∗ontona.

Ifk = 1 writea = a 1, a następnie

{a}∗={ǫ,a,aa,aaa,…,,,..}.

mamy bijectionn7→anfromNto{a}∗.Ifk≥2, then we can think of the string

u=AI 1 ···ain

as a representation of the integerv(u) in basekshifted by (kn−1)/(k−1), with

2.2. Alfabety, ciągi znaków, języki 17

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

kn-1 k− 1

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

(i withv (ǫ) = 0), gdzie 1≤ij≤kforj= 1,…, N.

zostawiamy to jako ćwiczenie, aby pokazać, Żev: Σ∗→Nis a bijection. Findingexplicite (thatis, wzór) dla odwrotnościvis zaskakująco trudne.

w rzeczywistości ν odpowiada wyliczeniu Σ∗, gdzie uprecedesv if|u|< / v/, a także uporządkowaniu leksykograficznemu if|u|=|v|. Łatwo jest sprawdzić, czy aboverelation (uprecedesv) jest całkowitym zamówieniem.

na przykład, ifk =2 i jeśli piszemy Σ = {a,b}, to wyliczenie zaczyna się od

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

aby uzyskać następny wiersz, połącz z lewej strony, a następnie połącz z lewej. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

to działa!

z drugiej strony, jeśli Σ 6 =∅, zbiór 2σ ∗ wszystkich podzbiorów Σ∗(wszystkich języków) jest nie do przeliczania.Rzeczywiście, możemy pokazać, że nie ma surjekcji od Σ ∗ na 2σ.najpierw pokażemy, że nie ma surjekcji od Σ∗na 2σ.. Jest to szczególny przypadek twierdzenia Cantora.Twierdzimy, że jeśli nie ma surjekcji z Σ∗na 2Σ ∗ , to nie ma również surjekcji z Σ∗na 2σ∗.

dowód. Załóżmy przez sprzeczność, że istnieje surjectiong: N→ 2 Σ ∗ . Ale jeśli Σ 6=∅, toσ∗jest nieskończone i policzalne, stąd mamy dwujęzyczność: Σ∗→N. Następnie kompozycja

Σ ν ν / / n

g // 2 Σ ∗

jest surjekcją, ponieważ bijectionvis a surjection,gis a surjection, a skład surjekcji jest surjekcją, zaprzeczając hipotezie, że nie ma surjekcji odσ∗do 2Σ ∗ .

2.3. Operacje na językach 19

2.3 operacje na językach

sposobem budowania bardziej złożonych języków z prostszych jest łączenie ich przy użyciu różnych operacji. Po pierwsze, dokonujemy przeglądu teoretycznych operacji łączenia, przecięcia i skompletowania.

Biorąc pod uwagę niektóre alfabetu Σ, dla dowolnych dwóch języków L 1 ,L 2 nad Σ, zjednoczenie L 1 ∪L 2 L 1 i L 2 jest językiem

L 1 ∪L 2 ={w∈Σ∗|w∈L 1 lub w∈L 2 }.

Sekcja 1 ∩L 2 z 1 i 2 jest językiem

L 1 ∩L 2 ={w∈Σ∗|w∈L 1 i w∈L 2 }.

ThedifferenceL 1 −L 2 ofL 1 andL 2 is the language

L 1 −L 2 ={w∈Σ Σ|w∈L 1 and w /∈L 2 }.

różnica nazywana jest także dopełniaczem.

szczególny przypadek różnicy otrzymujemy, gdy l 1 = Σ∗, w którym to przypadku definiujemy iloczyn języka

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

powyższe operacje nie wykorzystują struktury łańcuchów. Poniższe operacje wykorzystująkonkatenację.

definicja 2.8.Biorąc pod uwagę alfabetu Σ, dla dowolnych dwóch języków L 1 ,L 2 nad Σ, zjednoczenie L 1 L 2 L 1 i L 2 jest językiem

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

dla dowolnego języka definiujemy następująco:

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

ustawiając N= 0 inLn+1 = LnL, sinceL 0 = {ǫ}, otrzymujemy

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

soL 1 =L.

20 Rozdział 2. Podstawy formalnej teorii języka

następujące właściwości można łatwo sprawdzić:

L∅=∅,∅L=∅,L{ǫ}=l{ǫ}L=L(L-1 ∪{ǫ})L 2 =l 1 l 2 ∪l 2 ,l 1 l 2 ∪{ǫ}) =L 1 l 2 ∪1 l ,ЛнЛ=устаканится.

ogólnie L 1 L 26 =L 2 L 1.So far, operacje, które wprowadziliśmy, z wyjątkiem dopełnienia (sinceL= Σ∗ – Lis nieskończony iflis skończony, a Σ jest niepamięć), zachowują skończoność języków. Nie dotyczy to dwóch kolejnych operacji.

definicja 2.9.Biorąc pod uwagę Alfabet Σ, dla dowolnego języka Σ, theKleene∗ – closureL∗ofLis języka

L∗ =