GOS-262-talen

Inleiding tot de Theorie van de Berekening

Jean GallierDepartment van Computer en Informatie ScienceUniversity van PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]

©c Jean GallierPlease, doen notreproducewithout toestemming van de auteur

Maart 5, 2020

4 INHOUD

• 6.4 Het Pumping Lemma
• 6.5 Een Snel Algoritme voor het Controleren van de Staat van de Gelijkwaardigheid
• 7 Context-Vrije Grammatica ‘ s En Talen
• 7.1 Context-Vrije Grammatica ‘s
• 7.2 Afleidingen en Context-Vrije Talen
• 7.3 Normale Vormen voor Context-Vrije Grammatica’ s
• 7.4 Reguliere Talen Context-Vrije
• 7.5 Nutteloos Producties in Context-Vrije Grammatica ‘ s
• 7.6 De Greibach normaalvorm
• 7.7 Minste Vaste-Punten
• 7.8 Context-Vrije Talen-in ieder geval de Vaste-Punten
• 7.9 Minste Vaste Punten en de Greibach normaalvorm
• 7.10 Boom Domeinen en Gorn Bomen
• 7.11 Afleidingen Bomen
• 7.12 Ogden Lemma
• 7.13 Pushdown Automaten
• 7.14 Van Context-Vrije Grammatica ’s Voor PDA’ s
• 7.15 Van PDA ’s Op de Context-Vrije Grammatica’ s
• 7.16 De Chomsky-Schutzenberger Stelling
• 8 Een Enquête ofLR-Parsing Methoden
• 8.1 LR(0)-Karakteristieke Automaten
• 8.2 Shift/Reduce Parsers
• 8.3 Berekening van de EERSTE
• 8.4 De Intuïtie Achter de Shift/Reduce-Algoritme
• 8.5 De Grafiek Methode voor het berekenen van de Vaste Punten
• 8.6 Berekening van de FOLLOW
• 8.7 AlgorithmTraverse
• 8.8 meer onLR (0)-karakteristieke automaten
• 8.9 LALR(1) – Lookahead Sets
• 8.10 Computing FIRST, FOLLOW, etc. in de aanwezigheid vanǫ-regels
• 8.11 LR(1)-karakteristieke automaten

Inleiding

de rekentheorie houdt zich bezig met algoritmen en algoritmische systemen: hun ontwerp en representatie, hun volledigheid en hun complexiteit.

het doel van deze noten is om enkele van de basisbegrippen van de rekentheorie in te voeren, waaronder concepten uit de formele talen en de automatentheorie, de theorie van de rekenbaarheid, enkele basisbegrippen van de recursieve functietheorie en een inleiding tot de complexe theorie. Andere onderwerpen zoals juistheid van programma ’s zal hier niet worden behandeld (er justisn’ t genoeg tijd!).

de noten bestaan uit drie delen. Het eerste deel is gewijd aan formele talen en automaten. Het tweede deel behandelt rekenmodellen, recursieve functies en onbekwaamheid. Het derde deel gaat over computationele complexiteit, in het bijzonder de classesPandNP.

5

Basics of Formal Language Theory

2.1 Overzicht van enige elementaire wiskundige notatie en

N,Z,Q,R,C.

denatuurlijke getallen, n={ 0 , 1 , 2 ,…}.

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

onderdanen,

=

{

pq

/ p, q∈Z, q 6 = 0

}

null

Dereals, R. Thecomplex numbers, C = {a + ib/a, b R R}.

gegeven een setX, wordt de machtsverzameling vanxis de verzameling van alle deelverzamelingen vanxand 2x aangeduid.de notatie f: X→Y

geeft een functie aan metdomainx enrange(orcodomain)Y.

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

is degraphoff.

7

8 hoofdstuk 2. BASICS of FORMAL LANGUAGE THEORY

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

is theimageoff.

meer in het algemeen is ifA X X, dan

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

de(directe) imageofA.

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

is de omgekeerde afbeelding(orpullback) vanb.

f− 1 (B) is een verzameling; het kan zelfs leeg zijn alsb 6 =∅.Gegeven twee functiesf: X→Y eng: Y→Z, is de functieg f f:X→Zgiven door

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

de samenstelling offandg.

de functie idX: X→Xgiven by

idX (x) = x voor allx∈X

is de Identity function(ofX).

een functief: X→Y isinjectief (oude terminologieone-To-one)als voor allx 1, x 2 ∈X,

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

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

feit: IfX 6 =∅(en soY 6=∅), een functief:X →Y is injectief iff er is een functier:Y →X(aleft inverse) zodanig dat

r◦f= idX.

opmerking: ris surjectief.Een functief: X→Y issurjectief(oude terminologieonto)als voor bondgenoot Y Y, er iets xuch Xszoalsy=f(x), ifff(X) =Y.

feit: IfX 6 =∅(en soY 6 =∅), een functief:X→Y is surjectief iff er zijn een functies:Y →X (Rechte inverseorsectie) zodanig dat

f◦s= idY.

10 hoofdstuk 2. BASIS VAN de FORMELE TAAL THEORIE

EEN relationR⊆X×Xissymmetricif voor allx,y∈X, als (x,y)∈R, dan is het (y,x)∈R

Een relationR⊆X×Xis symmetrische iffR− 1 ⊆R.

GivenR⊆X×X(een relatie onX), defineRnby

R 0 =IXRn+1=R◦Rn.

de Transactieafsluiter+ofRis gegeven door

R+=

⋃

n≥ 1

Rn.

feit.R+is de kleinste transitieve relatie die R bevat.

de flexibele en transitieve closureR*ofri ‘ s gegeven door

R∗=

⋃

n≥ 0

Rn = R + IX IX.

feit.R∗is de kleinste transitieve en reflexieve relatie die R bevat.

een relatie r×x × Xis een equivalentieverhouding als deze reflexief, symmetrisch en transitief is.

feit. De kleinste equivalentieverhouding die een relatie R⊆X×X bevat, wordt gegeven door

(R∪R− 1)*.

een relatier⊆X × Xisantisymmetriek voor allx, y∈X, if (x,y) R Rand (y,x)∈R,thenx=y.

een relatier⊆X×X is een aparte orde als het reflexief, transitief en antisymmetisch is.

een partiële orde R ⊆X×X is een totale orde als voor allx, y ∈x, ofwel(x,y)∈ Ror (y,x)∈R.

2.2 alfabetten, Strings, talen

onze kijk op Talen is dat een taal een reeks strings is. Op zijn beurt is een string een eindexamen van letters uit een alfabet. Deze begrippen worden als volgt nauwkeurig gedefinieerd.

definitie 2.1.AnalphabetΣ is anyfiniteset.

2.2. Alfabetten, STRINGS, talen 11

we schrijven vaak Σ = {a 1,…, ak}. Ze worden de symbolen van het alfabet genoemd.Bijvoorbeeld:Σ ={a}Σ = {a, b, c} Σ = { 0, 1 }Σ ={α, β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ, ζ}een string is een eindige reeks symbolen. Technisch is het handig om strings te definiëren alsfuncties. Voor elk geheel getal≥1, laat

={ 1 , 2 ,…, n},

en forn = 0, let=∅.

definitie 2.2. Gegeven een alfabet Σ, astring overΣ (of gewoon een string) van lengte nisany functie

u: →Σ.

het geheel is de lengte van de stringu, en het wordt aangeduid als|u/. Wanneern = 0, wordt de speciale stringu: →Σ Van Lengte 0 de lege string of null string genoemd, en wordt aangeduid alsǫ.

gegeven een stringu: →Σ van lengte≥1,is u(i) de i-de letter in de stringu. Voor SIM-pliciteit van de notatie schrijven we in plaats van u(i), en geven we de stringu=u(1)u(2)···u(n)aan als

u=u 1 U 2 ···un,

met elk van beide.

bijvoorbeeld,als Σ ={a,b}andu: →Σ zo is gedefinieerd Datu(1) =a, U(2) =b, andu(3) =a, we writeu=aba.

andere voorbeelden van strings zijn

work, fun, gabuzomeuh

Strings van lengte 1 zijn functionsu: →Σ gewoon wat elementu(1) =aiin Σ kiezen.Zo zullen we elke symbolai Σ Σ identificeren met de corresponderende string van lengte 1.

de verzameling van alle tekenreeksen over een alfabet Σ, inclusief de lege tekenreeks, wordt aangeduid als Σ∗.

2.2. Alfabetten, STRINGS, LANGUAGES 13

voor de basis casen = 0, sinceu 0 = ǫ, hebben we

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

voor de inductiestap hebben we

un + 1u = (unu)u per definitie ofun+ =(uun)u door de inductiehypothese =u (unu) door associativiteit = uun+1 per definitie ofun+1.

definitie 2.4.Gegeven een alfabet Σ, gegeven twee stringsu, v Σ Σ∗definiëren we de volgende noties als volgt:

uiis een voorvoegsel van VIFF er is eeney Σ Σ zodanig dat

v=uy.

uiis een achtervoegsel van VIFF er is iets x Σ Σ∗zodanig dat

v=xu.

uis een substring van VIFF zijn er somex, Y Σ Σ∗zodanig dat

v=xuy.

we zeggen datuis een juist voorvoegsel (achtervoegsel, substring) ofviffuis een voorvoegsel (achtervoegsel, substring)ofvandu 6 =v.

bijvoorbeeld,gais een voorvoegsel ofgabuzo,zois een achtervoegsel ofgabuzo en Buzis een substring ofgabuzo.Bedenk dat een gedeeltelijke ordening≤ op een verzameling is een binaire relatie≤ S S×S die isreflexive, transitief, en antisymmetrisch.

de begrippen voorvoegsel, achtervoegsel en substring definiëren binaire relaties op Σ∗in de obviousway. Het kan worden aangetoond dat deze relaties deelordingen zijn.

een andere belangrijke volgorde op strings is de lexicografische (of woordenboek) volgorde.

definitie 2.5. Gegeven een alfabet Σ = {a 1,…,ak}verondersteld volledig besteld dergelijke thata 1 < een 2 <···< ak, gegeven twee stringsu,v∈Σ∗, definiëren we thelexicographic orderingas volgt:

uv







(1) ifv=uy, voor somey∈Σ∗, of(2) gebruiksaanwijzing=xaiy,v=xajz,ai< aj,withai,aj∈Σ, en voor somex,y,z∈Σ∗.

14 hoofdstuk 2. BASICS of FORMAL LANGUAGE THEORY

het idee is dat we simultaan van links naar rechts scanuandvsimultaan, waarbij we de thsymboluminuto de thsymboluminuto symbolvminv vergelijken, beginnend metm = 1. Als er geen discrepantie ontstaat, datis, als ze-het symbool is het met hen eens – het symbool vminvform = 1,…,| u/, thenuis a prefix OFV and we declarate thatuprecedesvin the lexicographic ordering. Anders, voor een tijdje vagree langs een gemeenschappelijk voorvoegselx (mogelijk de lege string), en dan is er eeneftmost discrepantie, wat betekent datuis van de formu=xaiy envis van de formv=xajz,metai 6 =aj(ENX,y, z Σ Σ∗arbitrair). Dan moeten we de band verbreken, en om dit te doen gebruiken we het feit dat de symbolsa 1 < a 2 <···< ak wordt verondersteld (volledig)geordend te zijn, dus we zien welke vanaiandajkomt als eerste, sayai< aj, en we verklaren Datu=xaiypreccedesv=xajzin de lexicografische ordening.

merk op dat de gevallen 1) en 2) elkaar uitsluiten. In geval (1),uis een prefix ofv. In geval (2) v6uandu 6 =v.

bijvoorbeeld abb, gallhagergallier.

het is vrij vervelend om aan te tonen dat de lexicografische ordening in feite een afzonderlijke ordening is.In feite is het atotale ordening, wat betekent dat voor elke twee stringsu, v Σ Σ∗, eitheruv, orvu.

het omgekeerde van een stringwordt inductief gedefinieerd als volgt:

rr = ǫ, (ua)R=auR,

wherea Σ Σ ENU Σ Σ∗.

bijvoorbeeld reillag=gallierR.

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

sinceǫR=ǫanda=ǫa, we krijgen

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

namelyaR=awant alla∈Σ.

door inductie op|v|kan worden aangetoond dat

(uv) R=vRuR.

een nuttige truc die de omslachtige notatie bij inductie op strings vermindert, is de waarneming dat een lege stringw Σ Σ∗van lengthn+ 1 (n≥0) kan worden geschreven als

w=ua, voor sommige U Σ Σ∗en sommige symbola Σ Σ, met|u|=n.

16 hoofdstuk 2. BASICS of FORMAL LANGUAGE THEORY

IfXis not the empty set, sincef: X→Nis an injection iff there is a surjectionr: N→Xsuch thatr f f = idX, the setXis telbaar iff there is aurjectionfromnontox.

feit. Het kan worden aangetoond dat een setXis aftelbaar is als het eindig is of als het in bijectiewithn is(in welk geval het oneindig is).

later zullen we zien datn×Nis telbaar is. Als gevolg daarvan is de setqvan rationale getallen aftelbaar.

een verzameling is onaandeelbaar als deze niet aftelbaar is.

bijvoorbeeld, R (de verzameling van reële getallen) is ontelbaar.Evenzo

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

is ontelbaar. Er is echter een bijectie tussen (0,1) Enr (vind er een!) De set 2nvan alle deelverzamelingen vanis uncountable. Dit is een speciaal geval van Cantor ‘ s hieronder besproken.

stel dat|Σ|=k met Σ ={a 1 ,…, ak}. Merk eerst op dat er snaren van lengte en (kn+1-1)/(k−1) snaren van lengte hoogstens Over Σ zijn; wanneer K= 1, zou de tweede formule dooryn+ 1 moeten worden vervangen. Inderdaad, omdat een string een functionu is: {1 ,…, n} →Σ, het aantal strings van lengthis het aantal functies van{ 1 ,…, n}Aan Σ, en aangezien de kardinaliteit van Σ isk, zijn er knsch functies (dit wordt onmiddellijk getoond door inductie onn). Dan is het aantal Tekenreeksen met een lengte ten hoogste

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

indien k = 1, is dit getal n+ 1, en indien k ≥ 2, als de som van een geometrische reeks, is het(kn+1-1)/(k−1).

Als Σ 6=∅, dan is de verzameling Σ∗van alle tekenreeksen over Σ oneindig en aftelbaar, zoals we nu laten zien door een expliciete bijectie Uit Σ∗ontoN te construeren.

Ifk = 1 writea = a 1, en dan

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

we hebben de bijectien7→anfromNto{a}*.Ifk≥2, dan kunnen we de string

u=ai 1 ···ain

zien als een representatie van het gehele getal v(u) in basekshifted door (kn−1)/(k−1), met

2.2. Alfabetten, tekenreeksen, talen 17

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

=

kn-1 k− 1

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

(en MeTV (ǫ) = 0), waarbij 1≤ij≤kforj = 1…, n.

we laten het als een oefening om aan te tonen datv: Σ∗→Nis een bijectie. Het vinden van expliciet (datis, een formule) voor de inverse vanvis verrassend moeilijk.

in feite komt ν overeen met de telling van Σ * waar uprecedesv if|u| < |v|, en uprecedesv in de lexicografische volgorde if|u|=|v|. Het is gemakkelijk om te controleren of de aboverelation (uprecedesv) is een totale orde.

bijvoorbeeld, ifk = 2 en als we Σ ={a,b} schrijven,dan begint de telling met

ǫ, 0a,b , 1 ,2, aa, ab, ba,bb , 3 , 4 , 5 ,6, aaa, aab, aba, abb, baa, bab, bba, BB7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

om de volgende rij te krijgen, concatenateaon de linkerkant, en dan concatenatebon de linkerkant. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

het werkt!

aan de andere kant, als Σ 6 =∅, is de verzameling 2Σ ∗ van alle deelverzamelingen van Σ∗(alle talen) niet meetbaar.Inderdaad, we kunnen laten zien dat er geen surjectie is van naar 2σ ∗ eerst, zullen we laten zien dat er geen surjectie is van Σ∗naar 2Σ∗. Dit is een speciaal geval van de stelling van Cantor.We beweren dat als er geen surjectie is van Σ∗naar 2Σ ∗ , er ook geen surjectie is van naar 2σ∗.

bewijs. Neem door tegenstrijdigheid aan dat er een surjectieg is:N→ 2 Σ ∗ . Maar als Σ 6=∅, danσ∗is oneindig en aftelbaar, dus hebben we de bijectiev: Σ∗→N. Dan is de samenstelling

Σ∗ ν // n

g // 2 Σ ∗

een surjectie, omdat de bijectievis een surjectie,gis een surjectie, en de samenstelling van surjecties is een surjectie, in tegenspraak met de hypothese dat er geen surjectie vanσ∗naar 2Σ ∗ .

2.3. Operaties op Talen 19

2.3 operaties op Talen

een manier om complexere talen uit eenvoudigere te bouwen is door ze te combineren met verschillende operaties. Eerst bespreken we de settheoretische operaties van vereniging, kruising en complementatie.

gegeven een alfabet Σ, voor elke twee talenl 1, L 2 gedeeld door Σ, is de eenheidl 1 ∪L 2 of L 1 en L 2 de taal

L 1 ∪L 2 ={w Σ Σ∗ / w∈L 1 of w∈L 2 }.

de intersectie L 1 ∩L 2 van L 1 en L 2 is de taal

L 1 ∩L 2 = {w Σ Σ∗ / w∈L 1 en w∈L 2 }.

het verschil 1-L 2 van L 1 en L 2 is de taal

L 1 −L 2 = {w Σ Σ∗ / w∈L 1 en w /∈L 2 }.

het verschil wordt ook wel het relatieve complement genoemd.

een speciaal geval van het verschil wordt verkregen wanneer L 1 = Σ∗, in welk geval we het complement van een taal definiëren als

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

bovenstaande bewerkingen maken geen gebruik van de structuur van tekenreeksen. De volgende operaties gebruiken concentratie.

definitie 2.8.Gegeven een alfabet Σ ,voor elke twee talenl 1, L 2 gedeeld door Σ, is de concatentiel 1 L 2 van L 1 en L 2 de taal

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

voor elke taal hebben we de volgende definities:

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

door in te stellen n = 0 inLn+1 = LnL, sinceL 0 = {ǫ}, krijgen we

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

soL 1 = L.

20 hoofdstuk 2. BASIS VAN de FORMELE TAAL THEORIE

De volgende eigenschappen zijn eenvoudig te controleren:

L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L, L-1 ∪{ǫ})L 2 =L 1 L 2 L ∪L 2 ,L 1 L 2 ∪{ǫ}) =L 1 L 2 L ∪L 1 ,LnL=LLn.

in het algemeen, L 1 L 26 = L 2 L 1.So de bewerkingen die we hebben geïntroduceerd, behalve complementatie (sinceL= Σ∗−Lis infinite ifLis eindig en Σ is niet-leeg), behouden de eindigheid van talen. Dit is niet het geval voor de volgende twee operaties.

definitie 2.9.Gegeven een alfabet Σ, voor elke taal boven Σ, theKleene∗-closureL∗ofLis de taal

L∗ =