- introduktion till teorin om beräkning
- 4 innehåll
- introduktion
- 5
- grunderna i formell språkteori
- 2.1 översyn av några grundläggande matematiska Notation och
- N,Z,Q,R,C.
- {
- }
- 7
- 8 kapitel 2. Grunderna i formell språkteori
- 10 kapitel 2. GRUNDERNA I FORMELLA SPRÅK TEORIN
- R+=
- ⋃
- R∗=
- ⋃
- 2.2. Alfabet, strängar, språk 11
- 2.2. Alfabet, strängar, språk 13
-
-
-
- 14 kapitel 2. Grunderna i formell språkteori
- 16 kapitel 2. Grunderna i formell språkteori
- 2.2. Alfabet, strängar, språk 17
- 2.3. Operationer på språk 19
- 20 kapitel 2. GRUNDERNA I FORMELLA SPRÅK TEORIN
introduktion till teorin om beräkning
Jean Gallierinstitutionen för data – och Informationsvetenskapuniversity of PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]
C. C. Jean Galliernågonting, intereproducerautan tillstånd av författaren
Mars 5, 2020
4 innehåll
- 6.4 den pumpande Lemma
- 6.5 en snabb algoritm för att kontrollera Tillståndsekvivalens
- 7 Kontextfria grammatik och språk
- 7.1 Kontextfria grammatiker
- 7.2 härledningar och Kontextfria språk
- 7.3 normala former för Kontextfria grammatiker
- 7.4 vanliga språk är Kontextfria
- 7.5 värdelösa produktioner i Kontextfria grammatiker
- 7.6 Greibach normalform
- 7.7 minst fasta punkter
- 7.8 Kontextfria språk som minst fasta punkter
- 7.9 minst fasta punkter och Greibach normalform
- 7.10 Träddomäner och Gorn träd
- 7.11 härledningar träd
- 7.12 Ogden ’ s Lemma
- 7.13 Pushdown automater
- 7.14 från Kontextfria grammatik till PDA: s
- 7.15 från PDA: S till Kontextfria grammatik
- 7.16 Chomsky-Schutzenberger-satsen
- 8 en undersökning avlr-Parsningsmetoder
- 8.1 LR(0)-karakteristiska automater
- 8.2 Skift/minska parsers
- 8.3 beräkning av första
- 8.4 intuitionen bakom Skift/minska algoritm
- 8.5 grafen metod för beräkning av fasta punkter
- 8.6 beräkning av följ
- 8.7 algoritmtraverse
- 8.8 mer onLR (0)-karakteristiska automater
- 8.9 LALR(1) – Lookahead uppsättningar
- 8.10 Computing först, följ, etc. i närvaro av 2,295 xnumx>
- 8,11 LR(1)-karakteristisk automat
introduktion
beräkningsteorin handlar om algoritmer och algoritmiska system: derasdesign och representation, deras fullständighet och deras komplexitet.
syftet med dessa anteckningar är att introducera några av de grundläggande begreppen i teorin om beräkning, inklusive begrepp från formella språk och automatteori, teorin om datorbarhet, några grunder för rekursiv funktionsteori och en introduktion till komplexitetteori. Andra ämnen som riktigheten av program kommer inte att varabehandlas här (det barainte tillräckligt med tid!).
anteckningarna är indelade i tre delar. Den första delen ägnas åtformalspråkoch automater. Den andra delen handlar om modeller av beräkning, rekursiva funktioner ochobeslutbarhet. Den tredje delen handlar om beräkningskomplexitet, ispeciellt klassernapandnp.
5
grunderna i formell språkteori
2.1 översyn av några grundläggande matematiska Notation och
N,Z,Q,R,C.
Thenatural tal, N={ 0 , 1 , 2 ,…}.
Theintegers, Z={…,− 2 ,− 1 , 0 , 1 , 2 ,…}.
Therationals,
Q=
{
pq
/ p,q Aci 6 = 0
}
null
Thereals, R. Dekomplexa tal, C = {a + ib / A, B CB r}.
givet någon setX, denpower setofxär uppsättningen av alla delmängder avxoch betecknas 2x.notationen f:X Bisexuell y
betecknar afunctionwithdomainXandrange(orcodomain)Y.
graph(F) ={(x,f(x)}|x Accubic X} Accubic X Accubic Y
är thegraphoff.
7
8 kapitel 2. Grunderna i formell språkteori
Im (f) =f(X) ={Y 2CU |x 2CU X, Y=F(x)} 2CU y
ärimageoff.
Mer generellt, ifA⊆X, tryck
f(A) ={y∈Y |∃x∈A, y=f(x)}⊆Y
är(direkt) imageofA.
IfB 2b, sedan f – 1(B) ={x 2b X|f(x) 2b X
är den omvända bilden (ellerpullback) avb.
f – 1 (B) är en uppsättning; det kan vara tomt även ifB 6 =kcal.Med tanke på två functionsf:X→Y andg:Y→Z, functiong◦f:X→Zgiven av
(g◦f)(x) =g(f(x)) för allx∈X
är thecompositionoffandg.
funktionen idX: X megapixlar Xgivet av
idX(x) =X för allax megapixlar X
är identifieringsfunktionen(ofX).
en funktionf: X megapixlar Y ärinjektiv (gammal terminologinen-till-en)om för allax 1, x 2 megapixlar x,
iff (x 1) = f (x 2), sedanx 1 = x 2 ;
motsvarande ifx 16 =x 2, sedan f (x 1) 6 =f(x 2).
Fact: IfX 6 = https: / / oc (och soja 6 = oc), en functionf: X OC Y är injective iff det finns en functionr: y oc X (aleft inverse) så att
r oc f= idX.
notera: ris surjective.En functionf:X→Y issurjective(gamla terminologyonto)om för ally∈Y, det är somex∈Xsuch thaty=f(x), ifff(X) =Y.
Fakta: IfX 6 =∅(och soja 6 =∅), en functionf:X→Y är injektiv iff det är en funktioner:Y →X(rätt inverseorsection) så att
f◦s= idY.
10 kapitel 2. GRUNDERNA I FORMELLA SPRÅK TEORIN
EN relationR⊆X×Xissymmetricif för allx,y∈X, om (x,y)∈R, då (y,x)∈R
En relationR⊆X×Xis symmetrisk iffR− 1 ⊆R.
GivenR⊆X×X(ett förhållande onX), defineRnby
R 0 =IXRn+1=R◦Rn.
Thetranstive closureR+ofRis ges av
R+=
⋃
n 1
rn.
faktum.R + är det minsta transitiva förhållandet som innehållerr.
Thereflexive och transitive closureR bisexuell ofRis ges av
R∗=
⋃
n 0
rn = r + IX IX.
faktum.R är det minsta transitiva och reflexiva förhållandet som innehållerr.
en relationR 2xubbixubbixär en ekvivalensrelationom den är reflexiv, symmetrisk och transitiv.
faktum. Det minsta ekvivalensförhållandet som innehåller ett förhållande tillxcorixxcorix anges med
(Rcorix R− 1 )corix.
En relationR⊆X×Xisantisymmetricif för allx,y∈X, om (x,y)∈Rand (y,x)∈R,thenx=y.
En relationR⊆X×Xis apartial för om det är reflexiv, transitiv, och antisymmetic.
en delbeställningr X X X är entotal ordning om för allx, y x X, antingen(x,y) ror (y,x) R.
2.2 alfabet, strängar, språk
vår syn på språk är detAtt språk är en uppsättning strängar. I sin tur är en sträng en finsekvens av bokstäver från något alfabet. Dessa begrepp definieras noggrant enligt följande.
Definition 2.1.Analphabet bisexuell är anyfiniteset.
2.2. Alfabet, strängar, språk 11
vi skriver ofta Xiaomi ={a 1,…, ak}. Theaiare kallas thesymbolsof alfabetet.Exempel:Σ ={a}Σ ={a,b,c}Σ ={ 0 , 1 }Σ ={α,β,γ,δ,lim,λ,φ,ψ,ω,m,n,q,σ,η,ξ,ζ}en sträng är En ändlig sekvens av symboler. Tekniskt är det bekvämt att definiera strängar somfunktioner. För alla heltal 1, låt
={ 1 , 2 ,…, n},
och forn= 0, let =0.
Definition 2.2. Med tanke på ett alfabet, Astrid över(eller helt enkelt en sträng) av längd Nisany funktion
u:.
heltalet är längden på stringu, och det betecknas som / u/. Whenn = 0, thespecial stringu: bisexuell längd 0 kallas theempty string, eller null string, och benämns som bisexuell.
med tanke på en stringu: 6BL av lengthn 1BL,u(i) är thei-th bokstaven i stringu. För SIM-plicity av notation skriver viuistead ofu(i), och vi betecknar stringu=u(1)u(2)···u(n)som
u=u 1 u 2 ···un,
med varjeuuj.
till exempel,om XXL ={a,b}Ochu: XLG definieras så Attu(1) =a, u(2) =b, Ochu(3) =a, vi writeu=aba.
andra exempel på strängar är
work, fun, gabuzomeuh
strängar av Längd 1 är functionsu: saucic helt enkelt plocka några elementu(1) =aiin Australia.Således kommer vi att identifiera varje symbolai Macau med motsvarande sträng av Längd 1.
uppsättningen av alla strängar över ett alfabet, inklusive den tomma strängen, betecknas som.
2.2. Alfabet, strängar, språk 13
för basen casen = 0, sedaneu 0 =GHz, vi har
u 0 u=IE=IE 0.
för induktionssteget har vi
un + 1u= (unu)u per definition ofun+ = (uun)u genom induktionshypotesen =u(unu) genom associativitet =uun+1 per definition ofun+1.
Definition 2.4.Med tanke på ett alfabet, med tanke på vilka två strängar som helst, v, definierar vi följande anmärkningar enligt följande:
uär ett prefix avviff det finns något sådant att
v=uy.
uis ett suffix ofviff det finns somex bisexuell sådan att
v=Xu.
uis en substring ofviff det finns somex, y GHz sådan att
v=XUY.
vi säger attuär ett korrekt prefix (suffix, substring) avviffuär ett prefix (suffix, substring)avvandu 6 =v.
till exempel gais ett prefix avgabuzo,zois ett suffix avgabuzoochbuzär en substring avgabuzo.Kom ihåg att en partiell beställning av bisexuell på en uppsättning är en binär relation till den som är flexibel, transitiv och antisymmetrisk.
begreppen prefix, suffix, och substring, definiera binära relationer på Taiwan i obviousway. Det kan visas att dessa relationer är partiella beställningar.
en annan viktig beställning på strängar är lexikografisk (eller ordbok) beställning.
Definition 2.5. Med tanke på ett alfabet Asia = {en 1,…, ak}antas helt beställt så attata 1 < a 2 <···< ak, med tanke på alla två strängaru, v IC, definierar vilexikografisk beställningsenligt följande:
UV
(1) ifv=uy, för someycogniz, eller (2) IfU=xaiy,v=xajz,ai< aj,withai,ajcogniz, och för somex,y,zcogniz.
14 kapitel 2. Grunderna i formell språkteori
tanken är att vi scanuandvsamtidigt från vänster till höger, jämföra demthsymboluminuto themth symbolvminv, börjar medm= 1. Om ingen skillnad uppstår, detär, om dem-TH symboluminuagreeswith dem-TH symbolvminvform= 1,…,| u/, denuär ett prefix avoch vi förklarar detöverträffarav den lexikografiska ordningen. Annars, för ett taguandvagree längs en gemensam prefixx(möjligen den tomma strängen), och sedanDet finns ennästa avvikelse, vilket betyder attuis av formu=xaiyandvis avformv=xajz, witai 6 =aj(andx,y,z acuis godtycklig). Då måste vi bryta slipsen, ochför att göra detta använder vi det faktum att symbolernaa 1 < a 2 <···< ak antas vara (helt)beställt, så vi ser vilken ofaiandajcomes först, sayai< aj, och vi förklarar thatu=xaiyprecedesv=xajzin den lexikografiska beställningen.
Observera att fall (1) och (2) utesluter varandra. I fall (1), uis ett prefix ofv. I fall (2)v6uandu 6 =V.
till exempel abb, gallhagergallier.
det är ganska tråkigt att bevisa att den lexikografiska beställningen faktiskt är aparti-beställning.I själva verket är det entotal beställning, vilket innebär att för alla två stringsu,v exporterar, eitheruv,orvu.
Därövergripande en strängdefinieras induktivt enligt följande:
oskyl=oskyl,(ua)r=auR,
där oskälig och oskälig.
till exempel reillag=gallierR.
Av settingu=ǫin (ua)R=auR,
sinceǫR=ǫanda=ǫa, vi får
aR= (ǫa)R=aǫR=aǫ=a,
namelyaR=aför alla∈Σ.
det kan visas genom induktion på / v / att
(uv) R=vRuR.
ett användbart trick som skär ner på besvärlig notation när man gör induktion på strängarär observationen att anonempty stringw 0 kan skrivas som
w=ua, för someu och vissa Symbola, med|u|=n.
16 kapitel 2. Grunderna i formell språkteori
IfXis inte den tomma uppsättningen, sincef: X megapixlar Nis en injektion iff det finns en surjectionr: n megapixlar xsuch thatr megapixlar f= idX, den setXis countable iff det finns asurjectionfromNontoX.
faktum. Det kan visas att en setXis kan räknas om den antingen är ändlig eller om den är i bijectionwithN(i vilket fall den är oändlig).
vi kommer att se senare thatn bisexuell NIS räknas. Som en konsekvens är uppsättningenqof rationella siffrorär räknbar.
en uppsättning kan inte räknas om den inte kan räknas.
till exempel är R(uppsättningen reella tal) otaliga.På samma sätt
(0,1) ={x II R / 0 < x < 1 }
är oräkneliga. Det finns dock en bijection mellan (0,1) andR(hitta en!) Den inställda 2Nof alla delmängder ofNis oräkneliga. Detta är ett speciellt fall av Cantors teoremdiskuteras nedan.
Antag|Xiaomi|=kwith Asia ={a 1 ,…, ak}. Observera först att det finnsknängder av längdoch(kn+1-1)/(k−1) strängar av längd som mestöver 0x; närk= 1, den andra formelnbör ersättas medn+ 1. Faktum är att eftersom en sträng är en functionu: {1 ,…, n}, dåantal strängar av längdär antalet funktioner från{ 1 ,…, n}till Xxl, och sedankardinalitet av ISK, det finnsSådana funktioner (detta visas omedelbart genom induktion onn). Då antalet strängar av längd som mestär
1 + k + k 2 +···+kn.
om k = 1, är detta tal n+ 1, och om k 2, som summan av en geometrisk serie, är den(kn+1-1)/(k−1).
om 6 = 6, Då är uppsättningen av alla strängar över 6, oändlig och räknbar, som vi nu visar genom att konstruera en explicit bijection från onton.
Ifk = 1 writea = a 1, och sedan
{a} https: / /
vi har bijektionenn7 bisexui anfromNto {a}.Ifk 2, då kan vi tänka på strängen
u=ai 1 ···ain
som en representation av integerv(u) i basekshifted av (kn−1)/(k−1), med
2.2. Alfabet, strängar, språk 17
brasilianskt (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.
(och withv(POV) = 0), där 1 ij 1 ij= 1,…, n.
vi lämnar det som en övning för att visa thatv: Bisexuell Nis en Bijection. Findingexplicit (thatis, en formel) för det omvända ofvis förvånansvärt svårt.
i själva verket motsvarar exporten till uppräkningen av exporten där uprecedesv if|u| < |v|, ochuprecedesvin den lexikografiska ordningen if|u|=|v|. Det är lätt att kontrollera att ovanståendeförhållande (uprecedesv) är en total order.
till exempel, ifk= 2, och om vi skriver ig = {a, b}, börjar uppräkningen med
ig,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
för att få nästa rad, sammanfogapå vänster och sedan sammanfogapå vänster. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.
det fungerar!
å andra sidan, om 6 = 6.Faktum är att vi kan visa att det inte finns någon överskottfrån 2 till 2 till att börja med kommer vi att visa att det inte finns någon överskottering från 2 till 2 till att börja med. Detta är ett speciellt fall av Cantors teorem.Vi hävdar att om det inte finns någon surjection från 2 till 2 , då finns det ingen surjection från 2 till 2 heller.
bevis. Antag med motsägelse att det finns en surjectiong: N 2 2 . Men om 6 = 6, då är 6 oändligt och räknbart, så har vi bijectionv: n. Då är kompositionen
Bisexuell / / n
g / / 2 msk
en surjektion, eftersom bijectionvis en surjection,GIS en surjection, och compositionof surjections är en surjection, vilket strider mot hypotesen att det inte finns någon surjection från Bisexuell till 2 msk .
2.3. Operationer på språk 19
2.3 operationer på språk
ett sätt att bygga mer komplexa språk från enklare är att kombinera dem medolika operationer. Först granskar vi de uppsatta teoretiska operationerna för union, korsning ochkomplementering.
Gett några alfabetet Σ, för två språkl 1 ,L 2 Σ, theunionL 1 ∪L 2 il 1andL 2 är det språk
L 1 ∪L 2 ={w∈Σ∗|w∈L 1 eller w∈L 2 }.
TheintersectionL 1 msk.L. 2 avl 1 ochL 2 är språket
L 1 msk. L. L. 2 ={w msk. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l. l.
ThedifferenceL 1 −L 2 ofL 1 ochL 2 är språket
L 1-L 2 ={w Baccarat|w Baccarat l 1 och w /Baccarat L 2 }.
skillnaden kallas ocksårelativt komplement.
ett speciellt fall av skillnaden erhålls närl 1=https:|/
l = {W.
ovanstående operationer använder inte strängarnas struktur. Följande operationer använderkonkatenation.
Definition 2.8.Med tanke på ett alfabet Σ, för två språkl 1 ,L 2 Σ, theconcatenationL 1 L 2 il 1 samt 2 är det språk
L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , v=uv}.
för vilket språk som helst definierar vienligt följande:
l 0 ={0},Ln+1=LnL (n 0 0).
genom att inställann= 0 inLn + 1=LnL, sinceL 0 ={oc.} får vi
L 1 =l0+1=L 0 l={oc.} l=l,
soL 1 =L.
20 kapitel 2. GRUNDERNA I FORMELLA SPRÅK TEORIN
följande egenskaper är enkelt kontrolleras:
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.
i allmänhet, L 1 L 26 =L 2 L 1.So långt, de operationer som vi har infört, utom komplementering (sinceL= Bisexual−Lis Infinite iflis finite och Macau är nonempty), bevara finiteness av språk. Detta är intefallet för de kommande två operationerna.
Definition 2.9.Med tanke på ett alfabet, för vilket språk som helstlover, denkle-slutningl-stängningl avl-språket
L-språket =