- Introduktion til teorien om beregning
- 4 indhold
- introduktion
- 5
- Grundlæggende om Formel sprogteori
- 2.1 gennemgang af nogle grundlæggende matematiske notationer og
- N,å,k,R,C.
- {
- }
- 7
- 8 Kapitel 2. Grundlæggende om Formel sprogteori
- 10 Kapitel 2. GRUNDLÆGGENDE FORMELLE SPROG TEORIEN
- R+=
- ⋃
- R∗=
- ⋃
- 2.2. Alfabeter, strenge, sprog 11
- 2.2. Alfabeter, strenge, sprog 13
-
-
-
- 14 kapitel 2. Grundlæggende om Formel sprogteori
- 16 kapitel 2. Grundlæggende om Formel sprogteori
- 2.2. Alfabeter, strenge, sprog 17
- 2.3. Operationer på sprog 19
- 20 kapitel 2. GRUNDLÆGGENDE FORMELLE SPROG TEORIEN
Introduktion til teorien om beregning
Jean GallierDepartment of Computer and Information ScienceUniversity of PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]
Christ C Jean GallierPlease, gør det ikkegengiveuden tilladelse fra forfatteren
marts 5, 2020
4 indhold
- 6.4 den pumpende Lemma
- 6.5 en hurtig algoritme til kontrol af Tilstandsækvivalens
- 7 kontekstfrie grammatikker og sprog
- 7.1 kontekstfrie grammatikker
- 7.2 afledninger og kontekstfrie sprog
- 7.3 normale former for kontekstfrie grammatikker
- 7.4 almindelige sprog er kontekstfrie
- 7.5 ubrugelige produktioner i kontekstfrie grammatikker
- 7.6 Greibachs normale Form
- 7.7 mindst faste punkter
- 7.8 kontekstfrie sprog som mindst faste punkter
- 7.9 mindst faste punkter og Greibachs normale form
- 7.10 Trædomæner og Gorn træer
- 7.11 afledninger træer
- 7.12 ogdens Lemma
- 7.13 Push ned Automata
- 7.14 fra kontekstfrie grammatikker til PDA ‘er
- 7.15 fra PDA’ er til kontekstfrie grammatikker
- 7.16 Chomsky-Schutsenberger-sætningen
- 8 En undersøgelse ofLR-Parsing metoder
- 8.1 LR(0)-karakteristisk Automata
- 8.2 Skift/reducer parsere
- 8.3 beregning af første
- 8.4 intuitionen bag Skift/reducer algoritmen
- 8.5 Grafmetoden til beregning af faste punkter
- 8.6 beregning af følg
- 8.7 algorithmtraverse
- 8.8 mere onLR (0)-karakteristisk Automata
- 8.9 LALR(1) – Lookahead sæt
- 8.10 Computing først, følg, etc. i nærværelse af Kris-regler
- 8.11 LR(1) – karakteristisk automat
introduktion
teorien om beregning vedrører algoritmer og algoritmiske systemer: deresdesign og repræsentation, deres fuldstændighed og deres kompleksitet.
formålet med disse noter er at introducere nogle af de grundlæggende forestillinger om teorien omcomputation, herunder begreber fra formelle sprog og automatteori, teorien omcomputabilitet, nogle grundlæggende i rekursiv funktionsteori og en introduktion til kompleksitetsteori. Andre emner som korrekthed af programmer vil ikke værebehandlet her (der er ikke nok tid!).
noterne er opdelt i tre dele. Den første del er afsat tilformelle sprogog automata. Den anden del omhandler modeller af beregning, rekursive funktioner ogubeslutsomhed. Den tredje del omhandler beregningskompleksitet, isærpandnp.
5
Grundlæggende om Formel sprogteori
2.1 gennemgang af nogle grundlæggende matematiske notationer og
N,å,k,R,C.
Thenaturlige tal, n={ 0 , 1 , 2 ,…}.
Theintegers, Å={…,− 2 ,− 1 , 0 , 1 , 2 ,…}.
Therationals,
K=
{
PK
/p, K, K, K 6 = 0
}
null
der er R. de komplekse tal,C={a+ib|a, b-r}.
i betragtning af et hvilket som helst sæt er kraftsættet af alle undergrupper af seksand betegnet 2 gange.notationen f:K-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H
er thegraphoff.
7
8 Kapitel 2. Grundlæggende om Formel sprogteori
Im(F) =f(H) ={Y-H | – H-H, y=f(H)} – H-H
er imageoff.
mere generelt er ifA-k, derefter
f(A) ={y-k |k-k-k-k, y=f(k)} k-k
det(direkte) billedeofa.
IfB-B, derefter f-1(b) ={k-b|f(K-B) B} K –
er det omvendte billede (orpullback) ofB.
f− 1 (B) er et sæt; det kan være tomt, selv ifB 6 =liter.Givet to functionsf:X→Y andg:Y→Z, functiong◦f:X→Zgiven af
(g◦f)(x) =g(f(x)) for allx∈X
er thecompositionoffandg.
funktionen IDH:
idh(h) =for allhøj
er identitetsfunktionen(ofh).
a functionf: y Erinjektiv (gammel terminologione-to-one)hvis for alle 1, 2 g,
iff (1) = f (2), derefter 1 =2 ;
ækvivalent ifh 16 = 2, thenf (1) 6 =f(2).
fakta: IFKS 6 =liter(og soja 6 = liter), en funktionf:liter Y er injektiv, hvis der er en funktionr:Y liter(omvendt), således at
r liter f= liter.
Bemærk:ris surjektiv.En functionf:X→Y issurjective(gamle terminologyonto)hvis allieret∈Y, der er somex∈Xsuch thaty=f(x), ifff(X) =Y.
Fakta: IfX 6 =∅(og soja 6 =∅), en functionf:X→Y er surjective iff der er en funktioner:Y →X(ret inverseorsection), således at
f◦s= idY.
10 Kapitel 2. GRUNDLÆGGENDE FORMELLE SPROG TEORIEN
EN relationR⊆X×Xissymmetricif for allx,y∈X, hvis (x,y)∈R, så er (y,x)∈R
En relationR⊆X×Xis symmetrisk iffR− 1 ⊆R.
GivenR⊆X×X(et forhold onX), defineRnby
R 0 =IXRn+1=R◦Rn.
Thetranstive closureR+ofRis givet af
R+=
⋃
n r 1
Rn.
fakta.R+er den mindste transitive relation indeholdenderr.
Derforfleksiv og transitiv closureR Kris ofRis givet af
R∗=
⋃
n ret 0
Rn=r+ret.
fakta.R-r er den mindste transitive og refleksive relation, der indeholder r.
et forhold, der er ækvivalent, hvis det er refleksivt, symmetrisk og transitivt.
fakta. Den mindste ækvivalensrelation, der indeholder en relationR, er givet af
(R, R, R− 1).
En relationR⊆X×Xisantisymmetricif for allx,y∈X, hvis (x,y)∈Rand (y,x)∈R,thenx=y.
En relationR⊆X×Xis apartial orden, hvis det er refleksiv, transitive, og antisymmetic.
en delvis ordrerr er en samlet rækkefølge,hvis for alle, y,enten (y,y), ror(y, H), R.
2.2 alfabeter, strenge, sprog
vores syn på sprog er detet sprog er et sæt strenge. Til gengæld er en streng en endelsekvens af bogstaver fra noget alfabet. Disse begreber defineres strengt som følger.
Definition 2.1.Analphabet er en anyfiniteset.
2.2. Alfabeter, strenge, sprog 11
vi skriver ofte List ={A 1 ,…, ak}. Theaiare kaldessymboleraf alfabetet.Eksempel:Σ ={a}Σ ={a,b,c}Σ ={ 0 , 1 }Σ ={α,β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ,ζ}En streng er en endelig sekvens af symboler. Teknisk er det praktisk at definere strenge somfunktioner. For enhver integern L. 1, Lad
={ 1 , 2 ,…, n},
og forn= 0, lad = ret.
Definition 2.2. Givet et alfabet-Karrus, der strækker sig over-karrus (eller blot en streng) med længde nisany-funktion
u: karrus.
helheden er stringens længde, og den betegnes som|u|. Nårn= 0, kaldes denspecial stringu: list af længde 0tom streng eller null strengog er betegnet som List.
givet en stringu: lengthn lengthn 1,U(I) er thei-th brev i stringu. For sim-plicity af notation skriver vieui stedet for U(i), og vi betegner stringu=u(1)u(2)···u (n)som
u=u 1 u 2 ···un,
med eachui Lira.
hvis f.eks.
andre eksempler på strenge er
arbejde, sjov, gabuh
strenge af længde 1 er functionsuDermed, vi vil identificere hver symbolai kursist med den tilsvarende streng af længde 1.
sættet af alle strenge over et alfabet-Larsus, inklusive den tomme streng,betegnes som Larras.
2.2. Alfabeter, strenge, sprog 13
for basen casen= 0, sinceu 0 =list, vi har
u 0 u=Litu=u=Litu=u 0.
for induktionstrinnet har vi
un+1U= (unu)u per definition ofun+ = (uun)u ved induktionshypotesen =u(unu) ved associativitet =uun+1 per definition ofun+1.
Definition 2.4.I betragtning af et alfabetkrus, givet to stringsu, v-kors definerer vi følgendenoteringer som følger:
UIS et præfiks ofviff der er somey-en sådan, at
v=Uy.
uis et suffiks ofviff der er noget af en sådan, at
v=su.
uis en understreng afviff der er noget,og så er det
v=suy.
vi siger detuis et korrekt præfiks (suffiks, understreng) afviffuis et præfiks (suffiks, understreng)afvandu 6 =v.
for eksempel gais et præfiks afgabusso,er et suffiks afgabussoogbusser en understreng afgabuso.Husk på, at en delvis bestilling af Kris på et sæt er en binær relation, som er refleksiv, transitiv og antisymmetrisk.
begreberne præfiks, suffiks og substring definerer binære relationer på kur i det indlysendemåde. Det kan vises, at disse relationer er delvise ordrer.
en anden vigtig bestilling på strenge er den leksikografiske (eller ordbog) bestilling.
Definition 2.5. Givet et alfabet L. = {- En 1,…, AK}antog helt bestilt sådan thata 1 < a 2 <···< ak, givet nogen to stringsu, v Kurt, vi definerer deneksikografiske ordresom følger:
UV
(1) ifv=uy, for en eller anden IfU, eller (2) IfU=en,v=en,AI< aj,medai,aj en, og for en eller anden,y,en en.
14 kapitel 2. Grundlæggende om Formel sprogteori
ideen er, at vi scanuandvsamtidig fra venstre mod højre, sammenligner demsymboluminuto themth symbolvminv, begyndende MedM= 1. Hvis der ikke opstår uoverensstemmelse, thats, hvis dem-TH symboluminuagreesmed dem-TH symbolvminvform= 1,…, / u/, denuer et præfiks af vandog Vi erklærer dethidtil den leksikografiske rækkefølge. Ellers, i et stykke tideuogvagree langs en fælles præfiks(muligvis den tomme streng), og derefterder er aleftmest uoverensstemmelse, hvilket betyder, atuis af formu=aiyandvis afformv=AJ,medai 6 =aj (Aks,y, å vilkårlig). Så skal vi bryde slipset, ogFor at gøre dette bruger vi det faktum, at symbolernea 1 < a 2 <···< ak antages at være (helt)bestilt, så vi ser, hvilken ofaiandajcomes først, sayai< aj, og vi erklærer, atu=aaiyphidesv=ajsin den leksikografiske rækkefølge.
bemærk, at sager (1) og (2) udelukker hinanden. I tilfælde (1), uis et præfiks ofv. I tilfælde (2) v6uandu 6 =v.
for eksempel abb, gallhagergallier.
det er ret kedeligt at bevise, at den leksikografiske bestilling faktisk er apartial bestilling.Faktisk er det atotal bestilling, hvilket betyder,at for enhver to stringsu, v kr,eitheruv, orvu.
Omvendelsenaf en streng defineres induktivt som følger:
LR=LR,(ua)R=LR,
hvor lr og lr.
for eksempel reillag=gallierR.
Ved settingu=ǫin (ua)R=auR,
sinceǫR=ǫanda=ǫa, vi får
aR= (ǫa)R=aǫR=aǫ=a,
namelyaR=afor alla∈Σ.
det kan vises ved induktion på|v|at
(uv)R=vRuR.
et nyttigt trick, der skærer ned på besværlig notation, når man laver induktion på stringser observationen om, at anonempty stringkraner af længdenn+ 1 (n-kraner 0) kan skrives som
v=ua, for someu-kraner og nogle Symbola-kraner, med|u|=n.
16 kapitel 2. Grundlæggende om Formel sprogteori
hvis det ikke er det tomme sæt, da det er en injektion, hvis der er en surjectionr:n, hvis der er en surjectionr:N, hvis der er en surjectionr.
fakta. Det kan vises, at et sæt kan tælles, hvis det enten er endeligt, eller hvis det er i bijectionmedn(i hvilket tilfælde Det er uendeligt).
vi vil senere se, at NIS tæller. Som følge heraf er sættetaf rationelle taltælles.
et sæt eruoverkommelighvis det ikke kan tælles.
for eksempel er R(sæt af reelle tal) utallige.Tilsvarende
(0,1) ={r| 0 < < 1 }
er utallige. Der er dog en vedektion mellem (0,1) andR(find en!) Sættet 2naf alle undergrupper afer utallige. Dette er et specielt tilfælde af Cantor ‘ s theorediskuteret nedenfor.
Antag|Lr|=kmed LRR ={- en 1 ,…, ak}. Først skal du bemærke, at der er knstrings af længdeog (kn+1-1)/(k−1) strenge af længde på Mostnover liter; nårk= 1, skal den anden formel erstattes afyn+ 1. Faktisk, da en streng er en functionu: {1,…, n} prist, denantal strenge af længdeer antallet af funktioner fra {1 ,…, n}til Kristian, og sidenkardinalitet af Kristian isk, der erknsådanne funktioner (dette vises straks ved induktion onn). Så antallet af strenge af længde højst er
1 + k + k 2 +···+kn.
hvis k = 1, er dette tal n+ 1, og hvis K−2, som summen af en geometrisk serie, er den(kn+1-1)/(k-1).
hvis Kristian 6 = Kristian, så er den indstillede Kristian af alle strenge over Kristian uendelig og tællelig, som vi nu viser ved at konstruere en eksplicit bijektion fra Kristian Onton.
Ifk= 1 skrivea=a 1 , og derefter
{a} l={L,A,aa,aaa,…,en,…}.
vi har bijectionn7-kren anfromNto{a} – kren.Ifk 2, så kan vi tænke på strengen
u=ai 1 ···ain
som en repræsentation af integerv(u) i basekshifted af (kn−1)/(k−1), med
2.2. Alfabeter, strenge, sprog 17
liter(u) =i 1 kn− 1 + i 2 kn− 2 +···+in-1 k + in
=
kn-1k− 1
- (i 1 -1) kn− 1 +···+ (i – 1 -1) k+i− 1.
(og medv ( lp) = 0), hvor 1 lp IJ lp= 1,…, n.
vi overlader det som en øvelse for at vise detv: Kristian Nis en vedektion. Findingeksplicit (deter en formel) for den inverse ofvis overraskende vanskelig.
faktisk svarer kr.til opregningen af Kr. hvor hid. v. if|u| < |V|, og HID. V. i den leksikografiske rækkefølge if|u|=|v|. Det er nemt at kontrollere, at ovenståendeforhold (uphidtilesv) er en samlet ordre.
for eksempel, ifk= 2, og hvis vi skriver Prip ={a, B}, begynder tællingen med
Prip,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
for at få den næste række skal du sammenkædepå venstre side og derefter sammenkædepå venstre side. Vehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.
det virker!
på den anden side, hvis KRP 6 = KRP, sæt 2 KRP af alle delmængder af KRP(alle sprog) er utallige.Ja, Vi kan vise, at der ikke er nogen surjection fromNonto 2 kr først, vi vil vise, at der ikke er nogen surjection fra Krona på 2 Krona. Dette er et specielt tilfælde af Cantors sætning.Vi hævder , at hvis der ikke er nogen surjection fra Kristian til 2 Kristian, så er der heller ingen surjection fromnonto 2 Kristian.
bevis. Antag ved modsigelse, at der er en surjectiong:N kr 2 kr . Men hvis den 6. er den 6. er den uendelig og kan tælles, så har vi bijectionv: den N. Derefter er kompositionen
Kris // n
g // 2 Kris
en surjektion, fordi bijektionen er en surjektion,GIS en surjektion, og sammensætningen af surjektioner er en surjektion, der modsiger hypotesen om, at der ikke er nogen surjektion fra Kris til 2 .
2.3. Operationer på sprog 19
2.3 operationer på sprog
en måde at opbygge mere komplekse sprog fra enklere er at kombinere dem ved hjælp afforskellige operationer. Først gennemgår vi de sætteoretiske operationer af union, kryds ogkomplementering.
Givet nogle alfabet Σ, for to sprogl 1 ,L-2 over Σ, theunionL 1 ∪L 2 ofL 1andL 2 er det sprog
L 1 ∪L 2 ={w∈Σ∗|w∈L 1 eller w∈L 2 }.
skæringspunktet L 1 L 2 af L 1 og L 2 er sproget
L 1 L 2 ={B LR|b l 1 og B L 2 }.
ThedifferenceL 1 −l 2 ofL 1 andL 2 er sproget
L 1 −l 2 ={B LR|B LR 1 og B /LR 2 }.
forskellen kaldes ogsårelativ komplement.
der opnås et specielt tilfælde af forskellen, nårl 1 = liter, i hvilket tilfælde vi definerer komplementlaf et sprogsom
l={b liter|vægt /liter l}.
ovenstående operationer bruger ikke strukturen af strenge. Følgende operationer brugerkoncatenation.
Definition 2.8.Givet et alfabet Σ, for to sprogl 1 ,L-2 over Σ, theconcatenationL 1 L 2 ofL 1 andL 2 er det sprog
L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , w=uv}.
for et hvilket som helst languageL definerer visom følger:
L 0 ={list}, Ln+1=LnL (n list 0).
ved settingn= 0 inLn+1=LNL, sinceL 0 ={list}, vi får
L 1 =L0+1=l 0 L={LIST}L=L,
soL 1 =L.
20 kapitel 2. GRUNDLÆGGENDE FORMELLE SPROG TEORIEN
De følgende egenskaber er nemt kontrolleres:
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.
generelt,L 1 L 26 =L 2 L 1.So langt, de operationer, som vi har introduceret, undtagen komplementering (sinceL= Price−Lis Infinite iflis finite og Price is nonempty), bevare sprogets endelighed. Dette er ikkesagen for de næste to operationer.
Definition 2.9.Givet et alfabetkrus, for ethvert sprogeloverkrus, denkleene-lukninglkrus ofLis sproget
Lkrus=