CIS 262 språk - CIS 262-UPENN

Introduksjon Til Teorien Om Beregning

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

©C Jean Galliervennligst, gjør det ikkeprodusere uten tillatelse fra forfatteren

Mars 5, 2020

4 INNHOLD

6.4 Pumping Lemma
6.5 En Rask Algoritme For Å Sjekke Tilstandsekvivalens
7 Kontekstfrie Grammatikker og Språk
7.1 Kontekstfrie Grammatikker
7.2 Avledninger Og Kontekstfrie Språk
7.3 Normale Former For Kontekstfrie Grammatikker
7.4 Regulære Språk er Kontekstfrie
7.6 Greibach-Normalformen
7.7 Minste Faste Punkter
7.8 Kontekstfrie Språk Som Minst Faste Punkter
7.9 Minst Faste Punkter Og Greibach Normal Form
7.10 Tre Domener Og Gorn Trær
7.11 Derivasjoner Trær
7.12 Ogden ‘ S Lemma
7.13 Pushdown Automater
7.14 Fra Kontekstfrie Grammatikker TIL PDAS
7.15 Fra PDAS Til Kontekstfrie Grammatikker
7.16 Chomsky-Schutzenberger Teoremet
8.1 LR(0)-Karakteristisk Automata
8.2 Skift/Redusere Parsere
8.3 beregning av første
8.4 Intuisjonen Bak Skift/Redusere Algoritmen
8.5 Grafmetoden For Beregning Av Faste Punkter
8.6 Beregning av følge
8.7 algoritmtraverse
8.8 mer onLR(0) – Karakteristisk Automata
8.9 LALR (1) – Lookahead Sett
8.10 Databehandling FØRST, FØLGE, etc. I nærvær avǫ-Regler
8.11 LR (1)-Karakteristisk Automat

Introduksjon

teorien om beregning er opptatt av algoritmer og algoritmiske systemer: deres design og representasjon, deres fullstendighet og deres kompleksitet.

hensikten med disse notatene er å introdusere noen av de grunnleggende begrepene i teorien om computation, inkludert begreper fra formelle språk og automatteori, teorien om computability, noen grunnleggende om rekursiv funksjonsteori, og en introduksjon til kompleksitetsteori. Andre emner som korrekthet av programmer vil ikke værebehandlet her (det justisn ‘ t nok tid!).

notatene er delt inn i tre deler. Den første delen er viet tilformale språkog automata. Den andre delen omhandler modeller av beregning, rekursive funksjoner ogubesluttsomhet. Den tredje delen omhandler beregningskompleksitet, ispesielt klassenespandnp.

5

Grunnleggende Om Formell Språkteori

2.1 Gjennomgang Av Noen Grunnleggende Matte Notasjon og

N,Z,Q,R,C.

Naturlige tall, n={ 0 , 1 , 2 ,…}.

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

Nasjonale,

{

}

null

Thereals,R. Thecomplex tall, C={a+ib|a,b∈r}.

gitt noen setX, thepower setofxer settet av alle undergrupper avxog er betegnet 2X. notasjonen f: X→Y

betegner enfunksjonwithdomainxandrange (orcodomain)Y.

graf(f) ={(x,f(x)}|x∈X}⊆X×Y

er graphoff.

7 8 KAPITTEL 2. GRUNNLEGGENDE OM FORMELL SPRÅKTEORI

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

er theimageoff.

Mer generelt, ifA⊆X, deretter

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

er (direkte) bildeofa.

Ifb⊆Y, så er f− 1 (B) ={x∈X|f(x)∈B}⊆x

er detvers bilde(ellerpullback) ofB.

f− 1 (B) er et sett; det kan være tomt selv omb 6 =∅Gitt to functionsf:X→Y andg:Y→Z, functiong◦f:X→Zgiven av

(g◦f)(x) =g(f(x)) for allx∈X

er thecompositionoffandg.

funksjonen idX: X→xgitt av

idX (x) =x for allx∈X

er identity funksjon(ofX).

en funksjonf: X→Y isinjektiv(gammel terminologien-til-en)hvis for allx 1 ,x 2 ∈x,

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

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

Faktum: IfX 6 =∅(og soya 6 =∅), en funksjonf: X →Y er injektiv iff det er en Funksjonr: Y →x (omvendt) slik at

r◦f= idX.

Merk: ris surjective.En functionf:X→Y issurjective(gamle terminologyonto)hvis for alliert∈Y, det er somex∈Xsuch thaty=f(x), ifff(X) =Y.

Fakta: IfX 6 =∅(og soya 6 =∅), en functionf:X→Y er surjective iff det er et funksjoner:Y →X(rett inverseorsection) slik at

f◦s= idY.

10 KAPITTEL 2. GRUNNLEGGENDE OM FORMELLE SPRÅK TEORI

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 X(et forhold onX), defineRnby

R 0 =IXRn+1=H◦Rn.

Thetransive closureR+ofRis gitt av

R+=

⋃

n≥ 1

Rn.

Fakta.R+er det minste transitive forholdet som inneholderr.

derfleksibel og transitiv stenging∗avris gitt av

R∗=

⋃

n≥ 0

Rn=R+∪IX.

Fakta.R∗er den minste transitive og refleksive relasjonen som inneholder r.

et forholdr⊆x×forholdhvis det er refleksivt, symmetrisk og transitivt.

Fakta. Den minste ekvivalensrelasjonen som inneholder en relationr⊆X×gitt av

(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 for hvis den er refleksiv, transitiv, og antisymmetic.

en delvis bestillingr ⊆x×X er atotal bestilling hvis for allx,y ∈x, enten (x,y)∈ Ror(y,x)∈r.

2.2 Alfabeter, Strenger, Språk

vårt syn på språk er detspråket er et sett med strenger. I sin tur er en streng en endeligsekvens av bokstaver fra noe alfabet. Disse begrepene er strengt definert som følger.

Definisjon 2.1.AnalphabetΣ

2.2. ALFABETER, STRENGER, SPRÅK 11

vi skriver Ofte Σ ={a 1,…,ak}. Theaiare kalte segsymbolerav alfabetet.Eksempler:Σ ={a}Σ ={a,b,c}Σ ={ 0 , 1 }Σ ={α,β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ,ζ}En streng er en endelig sekvens av symboler. Teknisk er det praktisk å definere strenger somfunksjoner. For ethvert heltall≥1, la

={ 1 , 2 ,…, n},

og forn= 0, la =∅.

Definisjon 2.2. Gitt et alfabet Σ, astring overΣ (eller bare en streng) med lengde nisany funksjon

u: → σ.

integernis thelengthof stringu, og det er betegnet som / u/. Whenn= 0, thespecial stringu: → σ av lengde 0 kalles theempty string, eller null string, og er betegnet somǫ.

gitt en stringu: → σ av lengden ≥ 1,u(i) er bokstaven i stringu. For sim-plicity av notasjon 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 ∈ σ.

for eksempel, Hvis Σ ={a,b}andu: → σ er definert slik thatu(1) =a,u(2) =b, andu(3) =a, skriver vieu=aba.

Andre eksempler på strenger er

arbeid, moro, gabuzomeuh

Strenger av lengde 1 er funksjonsu: → σ Bare plukke noen elementu(1) =aiin σ.Dermed vil vi identifisere alle symbolai ∈ σ med tilsvarende streng av lengde 1.

settet av alle strenger over et alfabet Σ, inkludert den tomme strengen, betegnes Som Σ ∗.

2.2. ALFABETER, STRENGER, SPRÅK 13

For basen casen= 0, sinceu 0 =ǫ, har vi

u 0 u=hryvu=u=u = u 0.

for induksjonstrinnet har vi

un+1u= (unu)u per definisjon avun + = (uun)u ved induksjonshypotesen = u (unu) ved assosiativitet =uun+1 per definisjon avun+1.

Definisjon 2.4.Gitt et alfabet Σ, gitt noen to stringsu, v ∈ σ ∗ definerer vi følgendenotionene som følger:

uis et prefiks ofviff det er noen ∈ σ ∗ slik At

v=uy.

uis et suffiks ofviff det er noenx ∈ σ ∗ Slik at

v=xu.

uis en delstreng ofviff det er somex, y ∈ σ ∗ Slik at

v=xuy.

Vi sier detu er et riktig prefiks (suffiks, delstreng) avviffuer et prefiks (suffiks, delstreng)avvandu 6 =v.

for eksempel,gais et prefiks avgabuzo,zois et suffiks avgabuzoandbuzer en delstreng avgabuzo.Husk at en delvis bestilling av≤ på et sett er en binær relasjon≤ ⊆ Som Er refleksiv, transitiv og antisymmetrisk.

begrepene prefiks, suffiks, og substring, definere binære relasjoner På Σ ∗ i obviousway. Det kan vises at disse relasjonene er delvise ordrer.

En annen viktig bestilling på strenger er leksikografisk (eller ordbok) bestilling.

Definisjon 2.5. Gitt et alfabet Σ ={a 1,…, ak}antatt helt bestilt slik thata 1 < a 2 <···< ak, gitt noen to stringsu, v ∈ σ ∗, definerer vileksikografisk bestillingsom følger:







(1) ifv=uy, for somey ∈ σ ∗, eller (2) ifu=xaiy,v=xajz,ai< aj,withai,aj ∈ σ, og for somex,y,z ∈ σ ∗.

14 KAPITTEL 2. GRUNNLEGGENDE OM FORMELL SPRÅKTEORI

tanken er at vi scanuandvsamtidig fra venstre til høyre, sammenligne thsymboluminuto themth symbolvminv, begynner medm= 1. Hvis ingen avvik oppstår, deter, hvis dem-th symboluminuagreeswith dem-th symbolvminvform= 1,…, / u/, den er et prefiks avvand vi erklærer detovertruffen leksikografisk bestilling. Ellers, for en stunduandvagree langs en felles prefixx (muligens den tomme strengen), og dadet er aleftmost avvik, noe som betyr thatuis av formu=xaiyandvis av theformv=xajz, withai 6 =aj (andx,y,z ∈ σ ∗ Vilkårlig). Da må vi bryte slipset, ogå gjøre dette bruker vi det faktum at symbolenea 1 < a 2 <···< ak antas å være (helt)bestilt, så vi ser hvilke ofaiandajcomes først, sayai< aj, og vi erklærer thatu=xaiyproducesv=xajzin leksikografisk bestilling.

merk at saker (1) og (2) er gjensidig utelukkende. I tilfelle (1), uer et prefiks ofv. I tilfelle(2)v6uandu 6 =v.

for eksempel abb, gallhagergallier.

det er ganske kjedelig å bevise at leksikografisk bestilling faktisk er apartial bestilling.Faktisk er det atotal bestilling,noe som betyr at for noen to stringsu, v ∈ σ ∗,eitheruv, orvu.

Derversalwrof a stringwer definert induktivt som følger:

ǫ=ǫ, (ua)R=auR,

hvoren ∈ σ Ogu ∈ σ ∗.

for eksempel reillag=gallierR.

Av settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa, får vi

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

namelyaR=for alla∈Σ.

Det kan vises ved induksjon på / v / at

(uv) R=vRuR.

et nyttig triks som kutter ned på tungvint notasjon når du gjør induksjon på strenger er observasjonen at anonempty stringw ∈ σ ∗ av lengden+ 1 (n≥0) kan skrives som

w=ua, for noenu ∈ σ ∗ og noen Symbola ∈ σ, med|u|=n.

16 kapittel 2. GRUNNLEGGENDE OM FORMELL SPRÅKTEORI

Ifx Er ikke det tomme settet, sidencef: X→Nis en injeksjon iff det er en surjectionr: N→Xslik thatr◦f = idX, setXis tellbar iff det er asurjectionfromNontoX.

Fakta. Det kan vises at en setXis tellbar hvis enten det er endelig eller hvis det er i bijectionwithN (i så fall er det uendelig).

vi vil se senere thatn×nis tellbar. Som en konsekvens, setqof rasjonelle talleneer tellbar.

et sett isuncountablehvis det ikke kan telles.

For eksempel Er R (settet med reelle tall) utallige.Tilsvarende

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

er utallige. Det er imidlertid en bijection mellom (0,1) andR(finn en!) Settet 2nav alle undergrupper avnis utallige. Dette er et spesielt tilfelle Av Cantors teoremdiskutert nedenfor.

Anta|Σ / =kwith Σ ={a 1,…,ak}. Først må du observere at det erknstrings av lengdeog (kn+1-1) / (k−1) strenger av lengde på de flesteover Σ; whenk= 1, den andre formelenbør erstattes av byn+ 1. Faktisk, siden en streng er en funksjonu: {1,…, n} → σ, daantall strenger av lengderetter antall funksjoner fra {1,…, n}Til Σ, og siden Kardialitet Av Σ isk, er det knnsuch funksjoner (dette vises umiddelbart ved induksjon onn). Så antall strenger av lengde på det mestenis

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

hvis k = 1, er dette tallet n+ 1, og hvis k ≥ 2, som summen av en geometrisk rekke, er det(kn+1-1) / (k−1).

Hvis Σ 6 =∅, Så Er den fastsatte Σ ∗ av alle strenger over σ uendelig Og tellbar, da vi nå viser ved å konstruere en eksplisitt bijeksjon fra σ ∗.

Ifk= 1 writea=a 1, og deretter

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

Vi har den bijectionn7@ anfromNto{a}∗.Ifk≥2, så kan vi tenke på strengen

u = ai 1 * * * ain

som en representasjon av integerv (u) i basekshifted av(kn−1)/(k−1), med

2.2. ALFABETER, STRENGER, SPRÅK 17

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

kn− 1k− 1

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

(og medv (ǫ) = 0), hvor 1≤ij≤kforj= 1,…, n.

vi legger det som en øvelse for å vise Thatv: Σ ∗ → Nis A Bijection. Findingexplicit(deter en formel) for den inverse avvis overraskende vanskelig.

faktisk tilsvarer ν opplistingen Av Σ ∗ if|u| < / v|, ogovertruffen leksikografisk bestilling if|u|=|v/. Det er enkelt å sjekke at ovenforrelasjon (hidtil us) er en total ordre.

for eksempel ifk= 2 og hvis vi skriver Σ ={a,b}, begynner opptellingen med

ǫ,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 å få neste rad, sammenkoblettil venstre, og deretter sammenkoblettil venstre. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

det fungerer!

på den Annen side, Hvis Σ 6 =∅, er den fastsatte 2Σ ∗ av alle undergrupper av hryvnias(alle språk) ikke mulig å telle.Faktisk kan vi vise at det ikke er noen surjeksjon franonto 2σ ∗ først, vi vil vise detdet er ingen surjeksjon FRA σ ∗ Til 2σ ∗. Dette er et spesielt tilfelle Av Cantors teorem.Vi hevder AT hvis Det IKKE er noen surjection FRA Σ ∗ til 2σ ∗ , så er DET HELLER INGEN surjection fra side 2σ ∗.

Bevis. Anta i motsetning at det er en surjectiong: N→ 2 Σ ∗ . Men Hvis Σ 6 = hryvnias, så erσ ∗ uendelig og tellbar, så har vi derfor en bijectionv: σ ∗ → N. Da er sammensetningen

Σ ∗ ν // n

g // 2 σ ∗

er en surjeksjon, fordi bijeksjonenvis en surjeksjon, gis en surjeksjon og sammensetningenav surjeksjoner er en surjeksjon, som motsier hypotesen om atdet ikke er noen surjeksjon fraσ ∗ til 2σ ∗ .

2.3. OPERASJONER på SPRÅK 19

2.3 Operasjoner På Språk

en måte å bygge mer komplekse språk fra enklere er å kombinere dem ved hjelp av ulike operasjoner. Først vurderer vi de settteoretiske operasjonene til union, intersection ogkomplementering.

Gitt noen alfabetet Σ, for to languagesL 1 ,L-2 over Σ, theunionL 1 ∪L 2 ofL 1andL 2 er den language

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

Veikryssetl 1 ∩L 2 av 1 og 2 er språket

L 1 ∩l 2 ={w ∈ σ ∗|w∈l 1 og w∈l 2 }.

Differencel 1-L 2 ofL 1 ogl 2 er språket

l 1 −L 2 ={w ∈ σ ∗|w∈l 1 og w /∈l 2 }.

forskjellen kalles ogsårelativ komplement.

et spesielt tilfelle av forskjellen oppnås nårl 1 = Σ ∗, i så fall definerer vi thecomplementLof a languagelas

l = {w ∈ σ ∗|W /∈l}.

ovennevnte operasjoner bruker ikke strukturen av strenger. Følgende operasjoner brukerkonkatenering.

Definisjon 2.8.Gitt et alfabet Σ, for to languagesL 1 ,L-2 over Σ, theconcatenationL 1 L 2 ofL 1 andL 2 er den language

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

for alle språk definerer vi følgende:

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

ved settingn= 0 inLn+1=LnL, sinceL 0 ={ǫ}, får vi

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

soL 1 = L.

20 KAPITTEL 2. GRUNNLEGGENDE OM FORMELLE SPRÅK TEORI

følgende egenskaper er lett verifisert:

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 operasjonene som vi har introdusert, bortsett fra komplementering (sinceL= Σ ∗ Uendelig ifLis endelig og σ er nonempty), bevare språkets finitet. Dette er ikkesaken for de neste to operasjonene.

Definisjon 2.9.Gitt et alfabet Hryvnias, for alle språkover Σ, thekleene∗-lukking av∗språket

l∗=