- Introducere în teoria calculului
- 4 cuprins
- Introducere
- 5
- Bazele teoriei limbajului Formal
- 2.1 revizuirea unor notații matematice de bază și
- N,Z,Q,R,C.
- {
- }
- 7
- 8 capitolul 2. Elementele de bază ale teoriei limbajului FORMAL
- 10 Capitolul 2. Elementele DE BAZĂ ale LIMBAJULUI FORMAL TEORIA
- R+=
- ⋃
- R∗=
- ⋃
- 2.2. Alfabete, siruri de caractere, limbi 11
- 2.2. Alfabete, siruri de caractere, limbi 13
-
-
-
- 14 Capitolul 2. Bazele teoriei limbajului FORMAL
- 16 capitolul 2. Elementele de bază ale teoriei limbajului FORMAL
- 2.2. Alfabete, siruri de caractere, limbi 17
- 2.3. Operații pe limbi 19
- 20 Capitolul 2. Elementele DE BAZĂ ale LIMBAJULUI FORMAL TEORIA
Introducere în teoria calculului
Jean Gallierdepartamentul de informatică și știința Informațieiuniversitatea din Pennsylvania, Pa 19104, USAe-mail:[email protected]
XCC Jean Galliervă rugăm să nu reproducețifără permisiunea autorului
Martie 5, 2020
4 cuprins
- 6.4 lema de pompare
- 6.5 un algoritm rapid pentru verificarea echivalenței de stare
- 7 gramatici și limbi fără Context
- 7.1 gramatici fără Context
- 7.2 derivări și limbi fără Context
- 7.3 forme normale pentru gramatici fără Context
- 7.4 limbile obișnuite sunt fără Context
- 7.5 producții inutile în gramatici fără Context
- 7.6 forma normală Greibach
- 7.7 cele mai puține puncte fixe
- 7.8 limbaje fără context ca cele mai puține puncte fixe
- 7.9 cele mai puține puncte fixe și forma normală Greibach
- 7.10 domenii de arbori și arbori Gorn
- 7.11 arbori derivați
- 7.12 Lema lui Ogden
- 7.13 automate de împingere
- 7.14 de la gramatici fără Context la PDA-uri
- 7.15 de la PDA-uri la gramatici fără Context
- 7.16 Teorema Chomsky-Schutzenberger
- 8 Un sondaj Allr-metode de analiză
- 8.1 LR(0)-automate caracteristice
- 8.2 Shift/reduce Analizoare
- 8.3 calculul primului
- 8.4 intuiția din spatele algoritmului Shift/reduce
- 8.5 metoda graficului pentru calcularea punctelor fixe
- 8.6 calculul urmării
- 8.7 algoritmtravers
- 8.8 mai onLR (0)-automate caracteristice
- 8.9 LALR(1) – Seturi Lookahead
- 8.10 calcul mai întâi, urmați etc. în prezența regulilor de circulație
- 8.11 LR(1)-automate caracteristice
Introducere
teoria calculului se referă la algoritmi și sisteme algoritmice: proiectarea și reprezentarea lor, completitudinea și complexitatea lor.
scopul acestor note este de a introduce unele dintre noțiunile de bază ale teoriei calculării, inclusiv concepte din Limbaje formale și teoria automatelor, teoria calculabilității, unele elemente de bază ale teoriei funcției recursive și o introducere în complexitateteorie. Alte subiecte, cum ar fi corectitudinea programelor nu vor fitratate aici (nu este suficient timp!).
notele sunt împărțite în trei părți. Prima parte este dedicatălimbi formaleși automate. A doua parte se referă la modele de calcul, funcții recursive șinedecidabilitate. A treia parte se ocupă de complexitatea computațională, înîn special claselespandnp.
5
Bazele teoriei limbajului Formal
2.1 revizuirea unor notații matematice de bază și
N,Z,Q,R,C.
numere naturale, n={ 0 , 1 , 2 ,…}.
Theintegers, Z = {…,− 2 ,− 1 , 0 , 1 , 2 ,…}.
naționale,
Q=
{
pq
|p,q, z, q 6 = 0
}
null
Theals, R. numerele complexe, c = {a + ib/a, b, r}.
având în vedere orice setX, setul de putere xxeste mulțimea tuturor subseturilor de xși este notat 2X.notația f:X Y
denotă o funcțiecu domeniulxandrange(saucodomain)Y.
grafic (f) = {(x,f(x)}|x x X} X X Y
este thegraphoff.
7
8 capitolul 2. Elementele de bază ale teoriei limbajului FORMAL
Im(f) =f(X) ={Y x |x x x x, y=f(x)} y
suntimagineoff.
Mai general, ifA⊆X, atunci
f(A) ={y∈Y |∃x∈A, y=f(x)}⊆Y
este(direct) imageofA.
IfB Y, atunci f-1 (B) = {x x|f(x) b} x
este imaginea inversă(saupullback) ofB.
f− 1 (B) este un set; ar putea fi gol chiar dacăb 6 =Irak.Dat două functionsf:X→Y andg:Y→Z, functiong◦f:X→Zgiven de
(g◦f)(x) =g(f(x)) pentru allx∈X
este thecompositionoffandg.
funcția idX:X Xxxxdat de
idX(x) =x pentru toțixx x x
estefuncția de identitate(ofX).
a funcțief: X xxx Y isinjective(vechea terminologie unu la unu)dacă pentru toatex 1 ,x 2 XXX,
iff(x 1 ) =f(x 2 ), thenx 1 = x 2 ;
echivalent ifx 16 =x 2 , thenf(x 1 ) 6 =f(x 2 ).
fapt: IfX 6 =0x(și soia 6 = x Xx), o funcțief:X X X X este injectiv iff există o funcțier:Y X X(invers aleft) astfel încât
r 0x f= idX.
notă:ris surjective.Un functionf:X→Y issurjective(vechi terminologyonto)dacă pentru ally∈Y, există somex∈Xsuch thaty=f(x), ifff(X) =Y.
Fapt: IfX 6 =∅(și soia 6 =∅), un functionf:X→Y este surjective iff există funcții:Y →X(corect inverseorsection), astfel încât
f◦s= idY.
10 Capitolul 2. Elementele DE BAZĂ ale LIMBAJULUI FORMAL TEORIA
O relationR⊆X×Xissymmetricif pentru allx,y∈X, dac a (x,y)∈R, atunci (y,x)∈R
O relationR⊆X×Xis simetrice iffR− 1 ⊆R.
GivenR⊆X×X(o relație onX), defineRnby
R 0 =IXRn+1=R◦Rn.
închizătorul Transtiv+ofRis dat de
R+=
⋃
n 1
Rn.
fapt.R + este cea mai mică relație tranzitivă care conținer.
prin urmareflexiv și tranzitiv closurer oifris dat de
R∗=
⋃
n 0
RN=R+VIII IX.
fapt.R-x este cea mai mică relație tranzitivă și reflexivă care conține r.
o relațier-X-X-X-X-O relațiedacă este reflexivă, simetrică și tranzitivă.
fapt. Cea mai mică relație de echivalență care conține o relație R X X X X X X X X este dată de
(R R− 1).
O relationR⊆X×Xisantisymmetricif pentru allx,y∈X, dac a (x,y)∈Rand (y,x)∈R,thenx=y.
O relationR⊆X×Xis apartial scopul dacă este reflexivă, tranzitivă și antisymmetic.
o comandă parțialărxtoxtoxx este o comandă totală dacă pentru toțix,yxtoxtoxx, fie (X,y) ror(y,x) R.
2.2 alfabete, șiruri, limbi
viziunea noastră asupra limbilor este căo limbă este un set de șiruri. La rândul său, un șir este un finitsecvență de litere dintr-un alfabet. Aceste concepte sunt definite riguros după cum urmează.
definiția 2.1.Analphabet XV este anyfiniteset.
2.2. Alfabete, siruri de caractere, limbi 11
noi scriem de multe ori ={A 1 ,…, ak}. Sunt numite simboluri ale alfabetului.Exemple:Σ ={o}Σ ={a,b,c}Σ ={ 0 , 1 }Σ ={α,β,γ,δ,ǫ,λ,φ,ψ,ω,µ,ν,ρ,σ,η,ξ,ζ}Un șir este o secvență finită de simboluri. Din punct de vedere tehnic, este convenabil să se definească șirurilefuncții. Pentru orice integern 1, să
={ 1 , 2 ,…, n},
și forn= 0, let =Irak.
definiția 2.2. Având în vedere un alfabet de la SEC.
integruleste lungimea șirului și este notat ca|u|. Whenn = 0, șirul specialu: lungimea 0 de la 0 se numește șirul gol sau șirul nul și este denotatca fiind de la 0.
având în vedere un stringu: XlX de lungimen xlxx1,u(i) este a treia literă din stringu. Pentru sim-plicitatea notației,scriemeuiîn loc de U (i), și denotăm stringu=u(1) u(2)···u(n) ca
u=u 1 u 2 ···un,
cu fiecareui inkt.
de exemplu, în cazul în care XL ={a,b}andu: XL este definit astfel încât u(1) =a,u(2) =B, XL(3) =A, we writeu=aba.
alte exemple de siruri de caractere sunt
munca, distractie, gabuzomeuh
siruri de caractere de lungime 1 sunt functionssu: pur și simplu alege un elementu(1) =aiin inec.Astfel, vom identifica fiecare simbol cu lungimea corespunzătoare a șirului 1.
mulțimea tuturor șirurilor de caractere de pe un alfabet, inclusiv șirul gol,este notată cu numărul de caractere de pe un alfabet.
2.2. Alfabete, siruri de caractere, limbi 13
pentru baza casen= 0, sinceu 0 =hectolix, avem
u 0 U=eluxuu=u=u_ulux=u 0.
pentru etapa de inducție, avem
un+1U= (unu)u prin definiție ofun+ = (uun)u prin ipoteza de inducție =u(unu) prin asociativitate =uun+1 prin definiție ofun+1.
definiția 2.4.Având în vedere un alfabet, având în vedere oricare două șiruri, v, v, v, v, v, v, v, v, v, v, v, v, v, 3439, v, 7996, UIS un prefix al CFF, există un anumit număr de caractere, astfel încât
uis un sufix ofviff există somex XV astfel încât
v=Xu.
uis un subșir ofviff există somex,y XV astfel încât
v=XUY.
spunem astaueste un prefix propriu (sufix, subșir) ofviffueste un prefix (sufix, subșir)ofvandu 6 =v.
de exemplu,gaeste un prefix ofgabuzo,zoeste un sufix ofgabuzo șibuzeste un subșir ofgabuzo.Reamintim că o ordonare parțială pe un set este o relație binară pe un set, care este reflexivă, tranzitivă și antisimetrică.
conceptele de prefix, sufix, și subșir, definesc relațiile binare pe Inextract în mod evident. Se poate demonstra că aceste relații sunt ordonări parțiale.
o altă ordonare importantă pe șiruri este ordonarea lexicografică (sau dicționar).
definiția 2.5. Având în vedere un alfabet XV = {a 1,…, ak}presupus total ordonat astfel încâta1 < a 2 <···< ak, având în vedere oricare două șirurisu, v inkt, definimordinareaexicograficădupă cum urmează:
UV
(1) ifv=uy, pentru somey-uri,sau(2) IFU=xaiy,v=xajz,ai< aj,withai, aj-uri,iar pentru someyx,Y, Z-uri.
14 Capitolul 2. Bazele teoriei limbajului FORMAL
ideea este că scanămșivsimultan de la stânga la dreapta, comparându-lethsymboluminuto themth symbolvminv, începând cum= 1. Dacă nu apare nicio discrepanță, astaeste, dacă ei-simboluluminuagreescu ei-simbolvminvform= 1,…,| u/, thenueste un prefix alvși declarăm că fără precedent în ordonarea lexicografică. În caz contrar, pentru o vremeuandvagree de-a lungul unui prefixx comun(posibil șirul gol), și apoiexistă cea mai mare discrepanță, ceea ce înseamnă căuis al formu=xaiyandvis alformv=xajz,withai 6 =aj(șix,y, z arbitrar). Apoi trebuie să rupem cravata șipentru a face acest lucru folosim faptul că simbolurilea1 < a 2 <···< ak sunt presupuse a fi (total) ordonate, așa că vedem care ofaiandajvine mai întâi, sayai< aj, și declarăm cău=xaiyprecedesv=xajzin ordonarea lexicografică.
rețineți că cazurile (1) și (2) se exclud reciproc. În cazul (1), uis un prefix ofv. În cazul (2) v6uandu 6 =V.
de exemplu abb, gallhagergallier.
este destul de obositor să demonstrăm că ordonarea lexicografică este de fapt ordonare apartială.De fapt, este o comandă atotală,ceea ce înseamnă că pentru oricare două stringsu, v inkt,fieruv, orvu.
Perereversalul unui șir este definit inductiv după cum urmează:
ectr=sectr,(ua)R=auR,
unde se află urc și URC.
de exemplu reillag=gallierR.
De settingu=ǫin (ua)R=auR,
sinceǫR=ǫanda=ǫa, vom obține
aR= (ǫa)R=aǫR=aǫ=o,
namelyaR=afor alla∈Σ.
se poate demonstra prin inducție pe|v|că
(uv)R=vRuR.
un truc util care reduce notația greoaie atunci când se face inducția pe șirurieste observația că șirulw anonim de lungime n+ 1 (n 0ctct) poate fi scris ca
W=UA, pentru someu inktctct și unele Symbola inktct, cu|u|=n.
16 capitolul 2. Elementele de bază ale teoriei limbajului FORMAL
Dacăx nu este setul gol, deoarecef:X INX este o injecție dacă există o surjecție.
fapt. Se poate arăta că un setxeste numărabil dacă este finit sau dacă este în bijectionwithN(caz în care este infinit).
vom vedea mai târziu căn NIS NIS numărabil. Ca o consecință, setQof numere raționaleeste numărabilă.
un set nu poate fi numărat dacă nu poate fi numărat.
de exemplu,r(mulțimea numerelor reale) este nenumărabilă.În mod similar
(0,1) ={x r| 0 < x < 1 }
este nenumărat. Cu toate acestea, există o bijecție între (0,1) andR(găsiți unul!) Setul 2n din toate subseturile de nenumărate. Acesta este un caz special al teoremului lui Cantordiscutate mai jos.
să presupunem|inkt / =KCU inkt ={a 1 ,…, ak}. În primul rând, observați că există șiruri de lungimenși (kn+1-1)/(k−1) șiruri de lungime cel multnover-uri; cândk= 1, a doua formulă ar trebui înlocuită cu N+ 1. Într-adevăr, deoarece un șir este o funcțienu: {1,…, n} int, numărul de șiruri de lungimeeste numărul de funcții din {1,…, n}Până La XV, și din moment ce cardinalitatea ISK-ului de la XV, existăastfel de funcții (acest lucru este arătat imediat prin inducerea onn). Apoi numărul de șiruri de lungime cel mai multeste
1 + k + k 2 +···+kn.
dacă k = 1, acest număr este n+ 1, iar dacă k 2, ca sumă a unei serii Geometrice, este(kn+1-1)/(k−1).
dacă XTX 6 = XTX, atunci setul XTX al tuturor șirurilor peste XTX este infinit și numărabil, așa cum se arată acum prin construirea unei bijecții explicite din XTX Onton.
Ifk= 1 writea=a 1 , și apoi
{a}} {A,A,aa,AAA,…, o,…}.
avem bijectionn7 si de la{a}.Ifk 2, atunci ne putem gândi la șirul
u=ai 1 ···ain
ca o reprezentare a integerv(u) în basekshifted de (kn−1)/(k−1), cu
2.2. Alfabete, siruri de caractere, limbi 17
(u) =i 1 kn− 1 +i 2 kn− 2 +···+în− 1 k + în
=
kn-1k− 1
- (i 1 -1) kn− 1 +···+ (în− 1 -1)k+în− 1.
(și Cuv(XV) = 0), în cazul în care 1 CTF IJ CTF kforj= 1,…, n.
îl lăsăm ca un exercițiu pentru a arăta thatv: Inqc este o Bijecție. Findingexplicit (thatis, o formulă) pentru inversulvis surprinzător de dificil.
de fapt,în cazul în care numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere de la numărul de numere. Este ușor să verificați dacă cele de mai susrelație (uprecedesv) este o comandă totală.
de exemplu, ifk = 2 și dacă scriem Inktific ={a,b}, atunci enumerarea începe cu
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
pentru a obține rândul următor, concatenațipe stânga și apoi concatenațipe stânga. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.
funcționează!
pe de altă parte, în cazul în care XTX 6 = XTX, setul 2 XTX din toate subseturile XTX(toate limbile) nu poate fi calculat.Într-adevăr, putem arăta că nu există nici o surjecție de la 2 la 2, vom arăta că nu există nici o surjecție de la 2 la 2. Acesta este un caz special al teoremei lui Cantor.Pretindem că dacă nu există nici o surjecție de la 2 la 2, atunci nu există nici o surjecție de la 2 la 2.
dovadă. Să presupunem prin contradicție că există o surjecțieg: N .2. Dar, dacă Xtx6 = XTX, atunci XTX este infinit și numărabil, deci avem bijecția v: xtxn. Apoi compozitia
/ / n
G // 2
este o surjectie, deoarece bijectia este o surjectie,GIS o surjectie, iar compozitia surjectiilor este o surjectie, contrazicand ipoteza ca nu exista o surjectie de la 2 la 2 .
2.3. Operații pe limbi 19
2.3 operații pe limbi
o modalitate de a construi limbi mai complexe din cele mai simple este de a le combina folosind diverse operații. În primul rând, revizuim operațiunile teoretice ale Uniunii, intersecției și completării.
Dat un alfabet Σ, pentru orice două languagesL 1 ,L 2 peste Σ, theunionL 1 ∪L 2 ofL 1andL 2 este limba
L 1 ∪L 2 ={w∈Σ∗|w∈L 1 sau w∈L 2 }.
Intersecțiunea L 1, L 2, L 1 și l 2 este limba
L, L 1, L 2 ={W, L|L, L 1 și L, L 2 }.
Differencel 1 −L 2 ofL 1 andL 2 este limba
L 1 −L 2 ={w.
diferența este, de asemenea, numităcomplement relativ.
se obține un caz special al diferenței atunci cândl 1 = XV, caz în care definim completarea unei limbi la fel de
L={w|w /L / W / L}.
operațiile de mai sus nu utilizează structura șirurilor. Următoarele operații utilizeazăconcatenare.
definiție 2.8.Având un alfabet Σ, pentru orice două languagesL 1 ,L 2 peste Σ, theconcatenationL 1 L 2 ofL 1 si 2 este limba
L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , w=uv}.
pentru orice limbă, definimdupă cum urmează:
L 0 ={}, Ln+1=LNL (n 0).
prin setaren= 0 inLn+1=LnL, sinceL 0 ={XV}, se obține
L 1 =L0+1=L 0 l={XV}l=l,
soL 1 =L.
20 Capitolul 2. Elementele DE BAZĂ ale LIMBAJULUI FORMAL TEORIA
următoarele proprietăți sunt ușor de verificat:
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=Sln.
în general, L 1 L 26 =L 2 L 1.So de departe, operațiile pe care le−am introdus, cu excepția complementării (sinceL= Infinite Iflis finite și infinite iflis finite și netulburate), păstrează finitudinea limbilor. Acest lucru nu este cazul pentru următoarele două operațiuni.
definiția 2.9.Având în vedere un alfabet, pentru orice limbă, pentru orice limbă, pentru orice limbă, pentru orice limbă, pentru orice limbă, pentru orice limbă, este limba
l, pentru orice limbă, este limba