TECHNISCHE HOGESCHOOL EINDHOVEN
Afdeling Algemene Wetenschappen
Onderafdeling der Wiskunde
TOEGEPASTE LOGICA II
'
van
Prof. Dr. W. Peremans
Lentetrimester 1985
·=-=
Technische Hogeschool Eindhoven Dictaatnummer 2.357.0 Prijs 1.5,50
-·A T C ·· o· -1
T HE
Onderafdeling der Wiskunde en Informatica Toegepaste logica 11 Syllabus bij het college van prof.dr. W. Peremans (28850)
I
t 1\
2
0
00
01
10
11
200
201
202
---------------------- ---
Inhouds beschrijving TOEGEPASTE LOGICA 11 W. Peremans Lentetrimester 1985
HOOFDSTUK 0: INLEIDING
1
§0.
Producties
1
§1.
Grammatica's
4
HOOFDSTUK 1: REGULIERE TALEN
9
§2.
Eindige automaten
9
§3.
Stelling van Mythill-Nerode
11
§4.
Operaties op talen. Reguliere expressies
16
§5.
Talen van type 3
23
HOOFDSTUK 2: CONTEKSTVRIJE TALEN
29
§6.
Inleiding
29
§7.
Afleidingen en afleidingsbomen
35
§8.
Operaties op talen. Pompstelling
47
§9.
Beslisbaarheid. Ambiguïteit
54
§10.
Stapelautomaten
64
HOOFDSTUK 3: SEMANTIEK
74
§11.
Inleiding
74
§12.
Partiële functies
77
§13.
Partiëel geordende verzamelingen
81
JdG, 31 Juli 2005
TECHNISCHE HOGESCHOOL EINDHOVEN Onderafdeling der Wiskunde en Informatica
TOEGEPASTE LOGICA II Syllabus bij het college van Prof.dr. W. Perernans (28850)
Lentetrimester 1985
-
HOOFDSTUK § 0.
o.
1 -
INLEIDING
PRODUKTIES Het college Toegepaste logica II is geen vervolg op het college Toegepaste logica I. Weliswaar wordt op bescheiden schaal van resultaten uit Toegepaste logica I gebruik gemaakt, maar dat hoeft geen beletsel te zijn om het college zonder kennis van Toegepaste logica I te volgen. Het college is ook minder 'fundamenteel' dan Toegepaste logica I: er zal met minder schroom van resultaten
uit de gangbare wiskunde gebruik worden gemaakt.
We beginnen met een beknopte bespreking van produkties in de
Zln
van E. Post.
Stel S een eindige verzameling; de elementen van S heten symbolen. We vormen eindige rijen van elementen van S, die we symboolrijen noemen. Hierbij is ook de lege rij inbegrepen, die we met A aanduiden. De symboolrijen inclusief A vormen de verzameling
s*
(exclusief A: S+). Op
s*
is een binaire operatie
gedefinieerd, die aan symboolrijen u en v de symboolrij toevoegt, die ontstaat door v achter u te schrijven; we duiden die symboolrij met uv aan en noemen de operatie concatenatie. Het is duidelijk dat concatenatie associa-
. .. tief is; dit drukken we uit door te zeggen dat S + en S * sernlgroepen ZlJn. Verder is A een neutraal element (Au= uA =u); daarom heets* een monoide. Soms worden de elementen van S letters en de elementen van S * woorden genoemd; voor sommige toepassingen is dit echter onpraktisch. Zo stellen in de theorie van natuurlijke talen de elementen van S soms woorden en de elementen van
s*
zinnen voor.
Een produktie wordt vastgelegd door
gekozen. Bij deze produktie gPhQk ~
gPhQk,
6 elementen vans*: g,h,k,g,h,k vast
horen produktieregels:
waarln P
Es*,
Q Es* variabel.
- 2 -
Speciale gevallen: g = k = g
= A;
k
dan is dè produktie semi-Thue; de
-
regel is dan PhQ ... PhQ; h = k = g = h = A· dan is de produktie normaal ; de
'
regel heeft dan de gedaante gP -+ Pk, Om een combinatorisch systeem te verkrijgen kiezen we een T c S en verder één vaste symboolrij, die we axioma noemen, benevens een. eindige verzameling
produkties. Een afleiding 1n dit systeem is een rij X , .•. ,Xm van elementen 0 van S * zo, dat x
0
het ax1oma 1S en X. .... x. voor i E {O, ..• ,m-1} een pro1 1+1
duktieregel 1S behorende bij een der produkties van het systeem. Een element X vanS * heet
afleidbaar in het systeem , als er een afleiding
in het systeem bestaat zo, dat X m
= X.
x0 , •.. ,Xm
De taal van het systeem is de verza-
meling {X E T*[x afleidbaar} • De symboolrijen in de taal bevatten uitsluitend symbolen in T; daarom heten de elementen van T eindsymbolen (Engels: terminal symbols). De elementen van
S\T heten hulpsymbolen (Engels: non-terminal symbols). Als alle produkties in een combinatorisch systeem semi-Thue (resp. normaal) zijn, dan noemen
we het systeem zelf ook semi-Thue (resp. normaal). Een eenvoudig voorbeeld van een semi-Thue systeem is het volgende: S = {A,a,b}, T = {a,b}; produktieregels PAQ-+ PaAbQ en PAQ-+ PQ; axioma A. Voorbeeld van een
afleiding: A,aAb, aaAbb, aaaAbbb, aaabbb.
De taal van het systeem is {anbn[n E W }; hierin stelt un de symboolrij voor die ontstaat door u
n
maal met zichzelf te concateneren: u
0
A, u
n+1
n
=u u.
Een van de vragen die men zich kan stellen is, bij gegeven T, welke deelverzamelingen van T* als taal bij een combinatcrisch systeem kunnen worden ver-
kregen. Let wel dat daarbij de keuze van S\T nog vrij is; men mag net zo veel hulpsymbolen toevoegen als men zelf wil. Post heeft aangetoond dat
- 3 -
iedere taal van een combinatorisch systeem ook te krijgen
j
s als de taal
van een normaal combinatoriscb systeem. Verder heeft Post combinatorische
systemen gebruikt voor een formele behandeling van het begrip beslisbaarheid; in het college Toegepaste logica I zijn daarvoor andere hulpmiddelen gebezigd. Daarop gaan we hier niet verder in. Een beroemd voorbeeld
van een combinatorisch systeem
1s
door Post geïntro-
duceerd en wordt in het Engels tag system genoemd. Kies S
= T = {0,1}.
Een
rij wordt nu als volgt gewijzigd: als met 0 begint: voorste drie schrappen en achteraan 00 toevoegen, als met
begint: voorste drie
schrappen en achteraan 1101 toevoegen.
Als de rij minder dan drie symbolen bevat, stopt het proces. Dit voorschrift kan worden beschreven met de volgende acht produktieregels: DOOP -+ POO
lOOP -+ P1101
001P-+ POO
101P-+ P1 101
010P -+ POO
110P-+ P1101
011P-+ POO
111P-+P1101
De keuze van het axioma lS vrij. Enkele voorbeelden van afleidingen:
1010, 01101, 0100, 000, 00; hierna stopt het. 1101, 11101, 011101, 10100, 001101, 10100; hier wordt na drie en na vijf stappen dezelfde rij verkregen. Dit heeft als gevolg dat na drie stappen het proces periodiek wordt met periode 2: de 6e is gelijk aan de 4e, 7e aan de
58 enz.
Een ingewikkelder geval van hetzelfde verschijnsel krijgen we als we starten met 10010. Dan komt er na de 16e en na de 22e stap dezelfde rij, namelijk 011011101110100 •. Na de 16e stap 1s het proces periodiek met periode 6. De
- 4-
vraag kan worden gesteld of iedere rij tot een stoppend, dan wel periodiek p_!.oces leidt; het antwoord op deze vraag is onbekend.
§ 1. GRAMMATICA'S
Een speciaal geval van een combinatorisch systeem is een grammatica.
Definitie grammatica
Een 4-tupel G =
heet een grammatica, als geldt: I is een eindige verzameling,
IT c I,
Z E I\IT, Ris een eindige verzameling paren (u,v), waarvoor u Er*, vEr*. Deze definitie van grammatica is afkomstig van N. Chomsky. De elementen van I heten symbolen, die van IT eindsymbolen, die van I\IT hulpsymbolen; we schrijven vaak IN:= I\IT. De elementen van R worden produkties of herschrijfregels genoemd. Van de regel (u,v) heet u het linkerlid, v het rechterlid, Z heet het startsymbooL We maken de afspraak in de theorie van de grammatica's voor de eindsymbolen Griekse letters en voor de hulpsymbolen Latijnse hoofdletters te gebruiken. Symboolrijen geven we aan met Latijnse kleine letters, Uiteraard kunnen in voorbeelden en toepassingen andere keuzen, bijvoorbeeld voor eindsymbolen worden gedaan.
Als p E I*
'
q E I*
bestaan zo, dat p er een eindige rij
'
dan schrijven we
= rus,
'l = rvs,
als er r, s, u, v, alle in I *
p~q
G
(u,v) E R. We schrijven p
Po'· · • ,pn bestaat zo, dat p 0 = p, Pn
voor i E {O, ... ,n-ll. Men zegt wel dat de relatie
transitieve afsluiting is van de
relat~ie
* ""G
=q
'**G
en P· l
q
als
""G pi+l
op r* de reflexief-
""· Let wel dat het in de definitie G
- 5 -
toegestaan is dat n = 0: p •* p geldt voor alle p E I * , Als bet G ~ duidelijk is op welke grammatica de relaties betrekking hebben laat men de
van
*
~
G in de notat·ie wel weg:
===>
en
*
~
in plaats van
..
G
en
*
=>
G
We noemen de bierboven gegeven rij p , ••• ,pn een afleiding van q uitpin G, 0 Definitie taal gegenereerd door grammatica
Stel G =
>
een grammatica. De taal L( G), gegenereerd door G wordt
gedefinieerd door L(G):= {x E IT*I Z
* x} G
Een afleiding van x uit Z wordt wel kortweg een afleiding van x genoemd. Alvorens voorbeelden te geven behandelen we enkele begrippen met betrekking tot symboolrijen. Definities en bewijzen betreffende symboolrijen kunnen vaak gevoerd worden met recurrentie langs de opbouw van symboolrijen: we behandelen f.. en voor een symboolrij x en een symbool t; gaan
1o1e
uit van x en
stappen over op x~. Zo kunnen we de gespiegelde xT van een symboolrij x
T
T
definiëren door A := A en (x~) := ~x
T
·
en de lengte l(x) van een symboolrij
door l(A):= 0 en l(xs):= l(x) + 1. Er geldt dan: (xy)T = yTxT, (xT)T =x,
~T = ~. l(xy) = l(x) Voorbeeld 1. Dan is L(G)
+
t(y), l(s) = 1, l(xT) = l(x).
IT= {a,S}, IN= {Z}, R = {(Z,aZS), (Z,A)},
= {ansnln
E n }. (Evenals in bet college Toegepaste logica I
wordt in dit college bet getal nul tot de natuurlijke getallen gerekend.) Voorbeeld 2.
IT = {a,S}, IN= {Z}, R = {(Z,aZa), (Z,SZS), (Z,A)} .
Dan is L(G)
{xxTix
x
T
Er;}.
Men noemt een symboolrij, waarvoor geldt
= x, wel een palindroom. Nu bestaat L(G) precies uit de palindromen van
- 6 -
even lengte, want voor y E y
T
Voorbeeld 3.
r; geldt namelijk:
= y en l(y) even
IT
= {a,6},
H
3xEI;[y
T
XX ],
IN = {Z,A},
R = {(Z,AZ),(A,aA6),(A,a),(Z,A)}, Voorbeeld van een afleiding:
Z,AZ, AAZ, AAAZ, AaA6AZ, aaA6AZ, aaa6AZ, aaaSaZ, aaa6a • Opgave 1.
Bepaal de taal die gegenereerd wordt door de grammatica van
Voorbeeld 3. Opgave 2.
Construeer een grammatica, die de palindromen van oneven lengte
genereert, De hierboven gedefinieerde grammatica's, die door Chomsky phrase-structure grammars zijn genoemd, zijn zeer algemeen en zelfs voor vele doeleinden te algemeen. Men legt daarom aan de grammatica's beperkingen op; deze hebben vaak betrekking op de gedaante van de herschrijfregels. Chomsky heeft bepaalde
beperkingen~
genoemd en deze met de nummers 0, 1, 2, 3 aangeduid;
deze aanduidingen zijn gangbaar geworden. Type 0 is het algemene geval zonder beperkingen. Wij geven nu een overzicht van een aantal beperkingen en hun consequenties, voorlopig zonder bewijzen. We nemen daarbij aan, dat de verzameling IT van eindsymbolen vast gekozen is. Het feit dat hierop volgende definities van de keuze van IT afhangen, brengen we niet in de notatie tot uitdrukking. Een deelverzameling van
r;
noemen we een taal. Talen worden met hoofdletters
aangeduid. Een verzameling van talen (ook wel klasse van talen genoemd) duiden we aan met een schrijfhoofdletter. Zo Zal
L0
de klasse zijn van de
talen, waarvoor een grammatica bestaat die hem genereert: de talen van type 0.
- 7 -
Als B een beperking voor grammatica 1 s voorstelt, dan is LB de klasse van de talen, die gegenereerd kunnen worden door een grammatica, die aan de beper-
king B voldoet. Bijzondere klassen van talen zijn R, de klasse
der~-
sieve talen en RE, de klasse der recursief-opsombare talen. Intuïtief betekent L E R, dat er een effectieve methode bestaat om voor iedere x E I; uit te maken of x EL dan wel
x~
L. Evenzo betekent L ERE, dat er een ef-
fectieve methode bestaat om een (eventueel oneindige) lijst te maken, waar precies de elementen van L in staan. Voor formele definities van R en RE verwijzen we naar Toegepaste logica I. De algemeenheid van de definitie van grammatica blijkt uit het feit dat L
0
= RE.
We beginnen nu met de beperking S: alle regels hebben de gedaante
(rAs,rqs), A E IN en r,q,s
alle in I*. Triviaal is dat LS c L ; er geldt 0
echter LS = L • Deze beperking helpt dus nog niet veel. 0
Een geheel andere beperking is ND: alle regels hebben de gedaante (u,v) met l(u) ~ l(v). Nu geldt LND c R. Dit levert wel een wezenlijke beperking. Bekend is namelijk R 1 RE, dus LND
1 L0
(ND staat voor: non-decreasing).
Leggen we de beperkingen S en ND beide op, dan ontstaat cs : alle regels 0 hebben de gedaante (rAs, rqs),A E IN, q EI+, rE I*, sE I*. Triviaal is
Les c LND; er geldt echter Les 0
dan A
LND" Verder is triviaal dat als L E LND' 0
~
L. Dit is vervelend, omdat we ook talen wensen te beschouwen, die
wel de lege symboolrij bevatten. Een kleine modificatie bewerkstelligt dit en leidt tot een belangrijke klasse. We beschouwen de beperking CS of type 1 (contekstgevoelig; Engels: context-sensitive) .. aan regels die alle van de gedaante (rAs, rqs), A E IN' qE I+, rE I*, sE r* zijn, kan eventueel nog worden toegevoegd de regel (Z,A); als deze laatste regel voorkomt wordt ook nog geëist, dat in alle regels (u,v) het symbool Z niet in v voorkomt.
.;
.
- 8 -
De bijbehorende klasse van talen heet L (talen van type 1 of contekstge1 voelige talen). Triviaal is echter ook L1
1
Les
R, dus ook L1
1 L1,(#
a
volgt uit {A} €
L1 ).
Er geldt
1 La.
De volgende beperking is CF of type 2 (contekstvrij; Engels: context-free): alle regels hebben de gedaante (A,q), A E ~· q Er*. De bijbehorende klasse van talen heet L · (tiüen van type 2 of contekstvrije talen). Triviaal 2 is
L2
c
La.
Er geldt echter ook
L2 1 L1 •
De laatste beperking die we hier bespreken, is type 3 of rechtslineair: alle regels zijn van de gedaante (A, qB) of (A,q), waarin A E IN,BEIN, q€r;.De bijbehorende klasse van talen heet L3 (talen van type 3). Triviaal is L c L ; er geldt zelfs L3 2 3
1 L2.
De hierboven gedane beweringen zullen in dit college niet allen worden bewezen. We ontlenen R 1 RE aan Toegepaste logica I. De volgende tabel geeft aan wat in het vervolg wel en niet zal worden aangetoond. bewijs van
geen bewijs van
LND
La
= RE
Ls
::>
c R
L c R 1
L2
1 L,
L3 'f L2
Les
La ::>
a
LND
L 'f R 1
Voor de klassen die bij de typen van Chomsky horen (de zogenaamde hiërarchie van Chomsky) geldt:
- 9 -
HOOFDSTUK 1. REGULIERE TALEN
§~.
EINDIGE AUTOMATEN We bespreken nu een heel andere methode om talen te verkrijgen dan de 1n Hoofdstuk 0 besproken grammatica's. Definitie eindige automaat Een 5-tupel A
~
<S ,I ,6 ,s 0 ,F >heet
S is een eindige verzameling
eindige automaat als geldt:
(elementen van S heten toestanden) ,
I is een niet-lege eindige verzameling (elementen van 1 heten symbolen), 6 1s een afbeelding S x I s
0
E S
F c S
--+
S,
(begintoestand), (elementen van F heten toegelaten toestanden).
De afbeelding 15 wordt wel overgangsfunctie genoemd (Engels: transition function of next state function). We breiden 6 uit tot een afbeelding 6': S >
~
S en wel met recurrent ie
langs de opbouw van de elementen van I*. Stel x EI*,~ EI, sE S, dan o'(s,A):= s, 6'(s,x~):= 6(6'(s,x),~)
Deze functie correspondeert met het beeld dat de automaat een doos is, die zich in een toestand s bevindt en bij invoer van een. symbool t; overgaat in
toestand 6(s,~). Een symboolrij wordt symbool voor symbool van links naar rechts ingevoerd; 6' beschrijft het effect op de toestand bij invoer van de symboolrij.
- 10 -
Dat 6' inderdaad een voortzetting van 6 is volgt uit 6'(s,~)
= 6'(s,A~) = 6(6'(s,A),~) = 6(s,~).
We laten voortaan het accent weg en schrijven voor 6' ook ó, Definitie taal geaccepteerd door eindige automaat Stel A= <s,r,ö,s ,F>een eindige automaat. De taal L(A), geaccepteerd door 0
A wordt gedefinieerd door
L(A):= {x E r*/o(s ,x) E F}. 0 Bij het vergelijken van talen die door een grammatica gegenereerd zijn met talen, die door een automaat geaccepteerd zijn, dient men te bedenken dat de symboolverzameling in het ene geval IT en in het andere geval I heet, Voor de functie 6 geldt een concatenatieformule: als x Er*, y Er*, sE s, dan ö(s,xy) = ó(ö(s,x),y). Dit
bewijst men met recurrent ie naar de opbouw van y: ó(s,xA) ó(s,xyn)
= ó(s,x)
~
ó(ó(s,x),A) ,
= ó(ó(s,xy),n) = ó(ö(ó(s,x),y),n)
ó ( ó ( s ,x) ,yn) •
Definitie reguliere taal Stel I een verzameling symbolen. Een deelverzameling L van r* heet een reguliere taal als er een eindige automaat A met I als verzameling symbolen bestaat zo, dat L
= L(A).
- 11 -
§3. STELLING VAN MYHILL-NERODE We maken in het vervolg gebruik van equivalentierelaties. Bij een equivalentierelatie r op een verzameling R hoort een partitie, waarvan de elementen de equivalentieklassen van r zijn. Deze partitie noteren we R/r; als x E R, dan noteren we de equivalentieklasse die x bevat als [x]
r
of kort-
weg [x]. Het aantal equivalentieklassen noemen we de index van de equivalentierelatie: index(r) = #R/r. Als R een semigroep is dan is een congruentierelatie e op R een equivalen-
tierelatie op R waarvoor bovendien geldt: als x ER, y ER, zE R, u ER, x s y, z s u, dan xz s yu. Een iets zwakker begrip is een rechtsinvariante (resp. linksinvariantè) equivalentierelatie:
als x ER, y ER, zE R, x • y, dan xz
~
yz (resp. zx • zy).
Een equivalentierelatie die zowel rechtsinvariant als linksinvariant is, ls een congruentierelatie: als x • y en z XZ S
=u
dan xz s yz en yz
= yu,
dus
yu.
We passen dit nu toe op talen. Stel ·I een eindige verzameling en L c I*. We definiëren
een relatie eL op I * door voor x E I * en y E I * te stellen:
Het is triviaal dat e 1 een rechtsinvariante equivalentierelatie
lSo
Verder
geldt: als x € L en xe1 y, dan y € L. Immers, uit x € L volgt xA =x € L; uit xe y volgt dan y = yA € L. 1
-
12 -
Anders geformuleerd: als x E L, dan [x]
c L, dat wil zeggen dat L vereL eniging is van equivalentieklassen. Nog anders geformuleerd: een equiva-
lentieklasse ligt geheel in L of heeft een lege doorsnede met L. Stelling 3.1
(Myhill-Nerode)
Stel I eindige verzameling, L c I*. Dan
geldt: L is regulier • index(eL) is eindig. Bewijs:
Stel L regulier. Dan is er een eindige automaat
zo, dat L
= L(A).
A
=<S,I,6,s ,F> 0
Stel x EI*, y EI*, dan geldt: als 6(s ,x) 0
= 6(s 0 ,y),
dan xeLy. Immers, als zE I*, xz EL, dan ö(s ,xz) E F, maar 0 6(s ,xz) = 6(6(s ,x),z) = 6(6(s ,y),z) 0 0 0
= 6(s 0 ,yz), dus 6(s 0 ,yz) E
F, dus
yz E L. Omgekeerd volgt op analoge wijze uit yz E L, dat xz E L. Dus xeLy. We definiëren nu S':= {sE S\~xEI*[6(s 0 ,x) = s]) (de elementen van S' worden wel bereikbare toestanden genoemd). De afbeelding<;>: sI ... I* /eL' wordt gedefinieerd door cp(s):= [x]
, als sE s• en ö(s ,x)
0
eL
= s.
Dit 1s een fatsoenlijke definitie. Omdat sE S', bestaat er namelijk een x
E I* zo, De afbeelding lP is echter ook surjectief want als x EI*, [x]
eL
• Omdat S' eindig is, volgt daaruit dat I*/e
1
en dus
index( e ) eindig 1s. 1
Stel nu omgekeerd dat index (e automaat A =<s ,I,6 ,s 0
0
verzameling. Als K E
,F
0
1
)
>.
eindig is. We definiëren een eindige We kiezen s := I*/eL; dit is een eindige 0
0
00
s0
en ~ E I, dan definiëren we 6 0 (K,~) door een x E K
'
- 13 -
te kiezen en hankelijk
lS
o0 (K,é)
= [xé]
te stellen, We moeten aantonen dat dit onafeL van de keuze van x in K. Stel y EK, dan xeLy' dus xéeLyé en = [yé]eL' We definiëren s := [A] 00 eL eL Dit levert dus een eindige automaat. We bewijzen
(rechtsinvariant), dus [xé] F := {K E s 1K n L f 0 0
Wl .
nu eerst voor x Er*, dat o (s 00 ,x) 0
=
[x]eL.
We doen dat door recurrentie naar de opbouw van x. Nu is = s
00
=[A]
eL
• Stel
o0 (s 00 ,x)
= [x]
eL
o0 (s 00 ,A) =
, dan
Nu tonen we aan dat
= [x]
eL dus [x]
E F , dus x 0
eL
n L f W, dus [x]
eL
c L, dus
x E L. Hieruit volgt dat L regulier I
lS,
Uit het bewijs van Stelling 3.1 valt nog wat meer te halen. AlsLeen reguliere taal is en A een eindige automaat, die L accepteert, dan levert het eerste deel van het bewijs, dat #S ~ #S' ~ #I*/eL = index(eL). Het tweede deel van het bewijs levert het bestaan van een eindige automaat, die L accepteert, met een aantal toestanden = index(eL). Conclusie: index(eL) is het minimum van de aantallen toestanden van L accepterende eindige automaten.
We kunnen echter ook nog afleiden dat er 'op isomorfie na' slechts
~~n
L
accepterende eindige automaat bestaat met dat minimale aantal toestanden.
Daartoe moeten we isomorfie van eindige automaten definiëren.
Definitie isomorfe eindige automaten
- 14 -
Dan heet A1 isomorf A2 als er een bijectie vsEs 1
v;Er
[~(o,(s,~ll
= 0 2(~(sl,;lJ
~:
s
1
~
s
'~(s,ol
2
bestaat zo, dat geldt:
s20
en {~(slis E F } = F • 2 1 Uiteraard is isomorfie een equivalentierelatie. Als nu L een reguliere taal
= L(Al,
is en A een eindige automaat waarvoor L
en het aantal toestanden
van A is index(eLl' dan volgt uit het eerste deel van het bewijs van Stelling 3.1 dat index(eLl = #S ~ #S' ~ index(eLl. Daaruit volgt dat S' = S e'n dat de in dat bewijs gedefinieerde~ een bijectie S ~ I*/eL = s
is. Deze
0
brengt nu een isomorfie van A en A0 tot stand. Stel namelijk s E S en
~
E I.
Omdat S' =Sis er een x Er* zo, dat s = 6(s ,x) en ~(ö(s,~)) = 0
= ~(6(6(s ,xl,~ll = ~(6(s 0 ,x;ll = [x<Je
0
0
~(s l
0
= ~(6(s ,All = [A]eL = s
00
1
o0 ([x]
. Stel sE F, s
eL'
0
= 6(s 0 ,xl,
dan
x EL en
E F ; omgekeerd stel K E F 0 , dan K n L # 0, dus er is een 0 eL x EK n L enK= [x]eL = ~(6(s 0 ,xll en ö(s 0 ,xl E F. Daarmee is de isomorfie
~(s)
= [x]
aangetoond. Dit levert de volgende stelling.
Stelling 3.2. Stel L een reguliere taal, A en A eindige automaten zo, dat 1 2 L = L(A 1 l
= L(A 2 l
en van A1 en A is het aantal toestanden= index(eLl. Dan 2
zijn A en A isomorf. 1 2 Opmerking. Myhill werkte in plaats van met de relatie eL met fL gedefinieerd door
Algebraïsch is deze relatie mooier dan eL' omdat het een congruentierelatie is. Verder geldt een analoge stelling , omdat
- 15 -
index(fL) eindig~ index(eL) eindig, Het moole verband tussen index (eL) en het aantal toestanden van een accepterende eindige automaat heeft geen tegenhanger bij fL. We geven nu enkele voorbeelden van talen, waarvan
we de regulariteit met
behulp van de stelling van Myhill-Nerode onderzoeken. We merken eerst op
I VwEI*
dat als L een taal is, de verzameling {x E I* tieklasse bij eL is. Kies nu a E I*, .t(a) =
.e
[xw !/. L]} een equivalen-
en L = {a} • De
t + 1 begin-
stukken van a vormen elk een klasse met één element; alle andere woorden
vormen ook een klasse, Dus
= i+ 2
index( eL)
en L is regulier, Om een auto-
maat voor L te maken, schrijven we a in letters uit: a= ó ••• ót_ 0
en
1
kiezen S:= {O, •• ,,t+1}, a(j
.n
j+1 als
={
voor alle
l+1 ~
~
=
~j
} voor j E {O, ... ,.t-1} , ê(.t,!;)
ê(t+1 ,!;)
.t+1
als~ i~-
J
E I. Tenslotte s
0
Een speciaal geval lS a= A, voor j E S, ó E I, s
0
= 0, F = {,f.),
.e
= 0, L ={A}. Dan is S = {O,l}, o(j,ó) =
O,F={O}.
Voor een eindige taal L geldt index(e ) 1
<1
L (.t(a)
+
talen zijn regulier. Een speciaal geval lS L = maat metS= {0}, ê(O,!;)
=0
voor
~
EI, F =
+
1); alle eindige
a EL
0, met index eL = 1 en auto-
0.
Stel nu I = {a, e}, L = {amen I m E JN ,n E JN } • Deze taal heeft de eigenschap dat, als x EL, ook ieder beginstuk van x in L zit. Daaruit volgt: VwEI* [xw !/. L] • x !/. L • Het complement van L is dus een equivalentieklasse. Als x= am
dan VwEI* [xw EL~ wE L] •. Als x= amen met n ~ 1, dan
k V wEI* [xw E L"' 3kEJN [w = 8 ]] ,
Dus index(eL) = 3; L is regulier. Voor een automaat kiezen we S
{0,1,2}.
- 16 -
ö(O,a)
=0
ö(O,S) =
Stel nu 1
ö(l,a) = 2
)
ö(1,S) =
= {cx,S},
ê(2,a) =
)
ê(2,il)
2
=2
l·
so = O, F
= {0,1}.
L = (anSn In E lN} • Nu geldt voor k E lN, .tE JN, k # .t,
dt . . . t volgt index ( e ) a a ke a.t. n1et geldt, 1rnmers a kkE S L, a .tk" 8 .. L. H1eru1 1
1
oo,
L is niet regulier. Op analoge wijze toont men aan, dat {anS"n In E JN} niet regulier is. We zullen later aantonen (Stelling 5.2), dat een taal regulier is dan en slechts dan als hij van type 3 is. De zojuist behandelde niet-reguliere talen zijn echter wel talen van type 2 op grond van de volgende grammatica's: IT = {a,S}, IN= {Z}, R = {(Z,aZS),(Z,h)} , resp. R
= {(Z,aZa),(Z,S)}.
Het bovenstaande
levert dus een bijdrage tot de be-
§4. OPERATIES OP TALEN. REGULIERE EXPRESSIES Als de symboolverzameling I gegeven is, zijn talen deelverzamelingen van
r*.
Op
talen kunnen de gebruikelijke verzamelingstheoretische operaties
worden toegepast zoals ·veréniging, doorsnede en complement. We kunnen echter ook concatenatie van talen definiëren als volgt: als L c I * , M c I * , dan LM:= {xy I x E L, y E M} • Deze concatenatie definieert dus een binaire operatie op P(I*), die assoc1atief is. Er is verder een neutraal element, namelijk {h} : {A}L
L{h} = L
voor alleL E P(I*). Op grond hiervan is P(I*) een monoide. Naast het neutrale element is er ook een nulelement,
namelijk~
:
~L
=
L~ =~voor
alle
L E P(I*). Zoals 1n iedere monoide kunnen we nu machten van talen definiëren, n 0 n+l n 1 2 L voor alle n E lN door L := {h}, L = L L. Inderdaad is dan L = L, L = LL.
- 17 -
Nog een operatie op talen is de overgang van L naar 1*; stelLE P(I*), L*:= \x 0 ••• x _ In E lN, V.E{O _ } [x. E L]J. Het gebruik van de ster n 1 J , ••• ,n 1 J moet gerechtvaardigd worden; we hadden namelijk al eens een ster gebruikt voor de overgang van een symboolverzameling I naar de verzameling van alle
symboolrijen I*. Nu is I c I*, zodat bovenstaande definitie ook op I toepasselijk is; het·is echter duidelijk dat het resultaat dan de verzameling van alle symboolrijen is en beide opvattingen van de ster tot hetzelfde resultaat voeren en verwarring dus niet te vrezen .is. 00
=
"'U
Ln. Er geldt A E 1* n=O n=1 en L* = L+ U {A}. Het is echter mogelijk, dat A E L en dan geldt L* = L+ •
Het is duidelijk dat 1*
U Ln; we definiëren L+
Algemener geitdt L*
= L+ ~A
çj* = {A},
E L .. VjEJN [Lj c Lj+ 1 J •
In= {x E I* if(x) = n} •
Dit alles tonen we niet aan. De steroperatie wordt ook wel Kleene-ster genoemd.
Stelling 4. 1 •
Stel I symboolverzameling, L c I * , M c I * • Dan geldt
als L en M regulier, dan L U M, L n M en LM regulier; als L regulier, dan I*\L en L* regulier. Bewijs:
Stel de eindige automaten A = <s1 ,I,öL's ,F > zo, dat L = L(A ) 1 10 1 1
= <sM,I,cM,sMO'FM> zo, dat M = L(AM). We definiëren nu <s ,I,ö 1 ,s 10 ,F 1> door s 1 := s xsM,o ((s,t),~):= (ö (s,s),öM(t,~)) 1 1 1 1
en AM A1 =
voor
s E s1 , t E SM, ~ E I; s 10 = ( s 10 , sMO) ; F 1 : = { ( s, t) Is E F of t E FM}. Met 1 recurrentie naar de opbouw van x E 1* bewijst men dat
- 18 -
en daaruit volgt o 1 (s 10 ,x) E F • o1 (s 10 ,x) E F of 6M(sM ,x) E FM • x EL 1 0 of x E M *x EL U M, dus L(A 1 ) =LU M. Een automaat A2 voor L n M, krijgt men door in A de F te vervangen door 1 1 F := {(s,t) Is E F ent E FM} • Een automaat A voor r*\1 krijgt men door 2 1 3 in A de F te vervangen door F := 1 1 3 automaat A4 door
s4 := s1xP(SM).
s1 \F1 •
Voor s E
We definiëren nu een eindige
s1 ,
V c SM'
o ((s,v),t;):= (o (s,t;),{oM(t,t;) I tE V} 4 1
E;
E I stellen we
u c) '
waarin
als o (s,t;) E F1 , 1
{ {sMO}'
c:=
r/J
als o1 (s,E;) f/_ FL
'
·-l''w•'""'ll,
als SLO E FL '
s4o·-
<8 Lo •
als SLO
r/J)
f/_
FL
Met recurrentie naar de opbouw van x Er* bewijst men dat o 4 (s 40 ,x) =(ö .(s ,x),{oM(sM0 ,w) 1 10
I wE
r*
A
3yEL [yw =x])). Hieruit volgt
o4(s40'x) E F4 • 3wEI* 3yEL [yw =x A oM(sMO'w) E FM] • 3wEM 3yEL [yw =x] ~x
E LM, dus L(A ) = LM. We definiëren nu een eindige automaat A door 4 5
s 5 :=
P(S ). Voor V c 1
b:= {o (s,t;) 1
c:=
{{s10 } r/J
s
50
:= \s
Is
enE; EI stellen we o (V,E;):= b U c, waarin 5
E V} ,
als b n F1 # r/J, als b
10
s1
n F1
= r/J.
l, F = {V E P(S ) I v n F # r/J} 5
1
1
Met recurrentie naar de opbouw van x E r* bewijst men, dat
- 19 -
is ook 1* regulier.
I
We zullen aantonen dat alle reguliere talen te verkrijgen zijn uitgaande van eindige talen door herhaaldelijke toepassing van vereniging, concatenatie en steroperatie. Daarbij.zijn echter niet alle eindige talen nodig, omdat sommige eindige talen uit andere eindige talen verkrijgbaar zijn met behulp van genoemde operaties. Allereerst is een niet-lege eindige verza-
meling vereniging van singletons (verzamelingen met één element): {a , ••• ,an_ l= {a } U ••• U {an_ }.Verder is een singleton van een niet-leeg 1 0 0 1 woord concatenatie van singletons van éénletterwoorden:, {~f- }.
1
men dat we kunnen volstaan
Bedenkt men ook nog dat {A} = '/J * , dan ziet
met~
en {é} voor
alle~
E I.
Definitie Ree Ree is de kleinste onder de verzamelingen ~ E
F van
talen, die voldoen aan:
F
{;;} E Fvoor alle
~
als L E Fen ME
F, dan LU ME Fen LM E F,
E I,
als L E F, dan 1* E F. Met het woord kleinste is bedoeld dat voor alle elsen voldoen, geldt Ree c
F en
F,
die aan bovenstaande
dat Ree zelf ook aan die eisen voldoet.
We tonen eerst aan dat Ree bestaat. Dit kan op twee manieren. 1.
Er bestaan verzamelingen van talen, die aan de eisen voor F voldoen, bijvoorbeeld P(I*), de verzameling van alle talen. Verder is het zo, dat de doorsnede van een collectie van F's, die alle aan de eisen vol-
- 20 -
doen, ook aan de e1sen voldoet. We vinden nu Ree als de doorsnede van
alle F's die aan de eisen voldoen. 2.
Neem de verzameling van alle talen, die ontstaan door een eindig, maar
onbegrensd aantal malen operaties (L,M),... LU M, (L,M) toe te passen, uitgaande van de talen
~
1-+
LM en L
t+
1*
en (é} voor é E I. Dat levert
een verzameling talen, die aan de eisen voldoet en kennelijk ook de kleinste. Stelling 4.2. Be'Wi,js:
Ree = verzameling der reguliere talen.
Op grond van de resultaten van §3 en Stelling 4.1 is de verzameling
der reguliere talen een verzameling die aan de eisen voor F in de definitie van Ree voldoet, dus Ree c verzameling der reguliere talen. Stel nuL een reguliere taal en A= <s,I,6,s ,F> een eindige automaat zo, dat L 0
L(A).
We nummeren de elementen vanS: stel #S = n en S = {s 0 , ••• ,sn_ 1}; ook hier is s
0
de begintoestand. We definiëren nu talen L(i,j,k) voor {i,j}c{O,.,.,n-1}
enk E {O, ••• ,n}, als volgt L(i,j,k):= {x E r*l6(s. ,x) 1
We be'Wijzen dat alle L(i,j,k) EReeen 'Wel met volledige inductie naar k. Als x E L(i,j,O), dan f(x) ~ 1, dus L(i,j,O) eindig, dus L(i,j,O) E Rec. Stel nu de bewering juist voor zekere k < n. Er geldt L(i,j,k+1)
L(i,j,k) U L(i,k,k)(L(k,k,k))*L(k,j,k).
Dat ieder element van het rechterlid ook element is van het linkerlid, is duidelijk. Een element x van het linkerlid voeren we door de automaat A
- 21 -
beginnend in toestand s .• Het eindigt dan in toestand s .• Als alle toestanJ
1
den nummers< k hebben dan x E L( i ,j ,k). Zijn er tussentoestanden met nummer k~
dan verknippen we het woord tot een concatenatie van woorden bij iedere
plaats waar een toestand met nummer k optreedt. Het voorste woord in deze concaterratie zit in Lli,k,k), het achterste 1n Llk,J,k) en eventuele tussengelegen woorden in L(k,k,k). Dus x E rechterlid. Volgens inductieveronderstelling zijn alle talen in het rechterlid elementen van Ree, dus ook L(i,j,k+l) E Rec. Nu is L(i,j,n) = {x EI*[ ó(s. ,x) l
L
s.} en dus J
I
U L(O,j,n). Daaruit volgt L E Rec. s .EF J
In Stelling 4.2 wordt een zogenaamde recurrente karakterisering van de reguliere talen tot stand gebracht. Op grond daarvan kan men van een eigenschap van talen aantonen dat zij voor alle reguliere talen geldt, door aan te tonen
dat~
en
{~}voor alle~
EI de eigenschap hebben benevens dat als
L en M de eigenschap hebben, dit ook geldt voor LU M, LM en L*.
Een voor-
beeld hiervan levert de gespiegelde LT van een taal L, gedefinieerd door L T := {x Tf x E L} •
Stelling 4.3.
Als de taal L regulier is, dan is LT regulier.
Men kan dit bewijzen door het·.bovenstaande toe, te passen o-p de eigenscha-p "LT 1s . regu1·1er " • 0~.
Voer dit uit.
Als men een reguliere taal opbouwt met een recurrent proces, dan kan men dit proces weergeven met een expressie, die uitdrukt welke operaties suc-
cessievelijk zijn toegepast. Zo is {am~n[mEJN,nEJN} "{cd*{~}*. We laten nu de accolades weg en komen zo tot reguliere expressies.
- 22 -
Definitie reguliere expressie Stel I een verzameling symbolen, I n {( ,),0,U,*} =
~.
Als a € I, dan is a een reguliere expressie;
m is
een reguliere expressie;
als E en F reguliere expressies zijn, dan zijn (E U F) en (EF) reguliere expressies; als E een reguliere expressie is, dan is E* een reguliere expressie;
alleen hetgeen op grond van bovenstaande voorschriften is gevormd, is een reguliere expressie.
Voorbeelden van reguliere expressies zijn 0, 0*, (a U 8), ((a U 8)(8 U y))* • We definiëren nu de taal L(E) van een reguliere expressie E door recurrentie langs de opbouw van E. Definitie taal van een reguliere expressie L( 0) : = ~
;
als a EI, dan L(a):= {a}; alsEen F reguliere expressies zijn, dan L((E U F)):= L(E) U L(F) en L((EF)):= L(E)L(F); als E een reguliere expressie is, dan L(E*) = (L(E)) * Stelling 4.4, Lis
Stel I symboolverzameling,L c I * Dan geldt:
(Kleene).
regulier~
er bestaat een reguliere expressie zo, dat L = L(E).
Dit volgt direct uit Stelling 4.2. Bij verschillende reguliere expressies kan dezelfde taal behoren; noem deze equivalent: E
~
F:
~
L(E)
= L(F).
- 23 -
Enkele voorbeelden van equivalente reguJ.iere expressieS!
(a U ~ )* - (a * S * )* , (a US)*- ((a* S *)*a*) (a*~)*- (~*U ((a US)* S))
§5. TALEN VAN TYPE 3 Een grammatica is van type 3 als alle regels van de gedaante (A,qB) of (A,q)
* • Voor afleidingen bij een grammatica van zijn met A E 111 , B E IN' q E IT type 3 geldt het volgende: Als p
*
~
r, dan is het aantal voorkomens van hulpsymbolen 2n r
~het
aantal
voorkomens van hulpsymbolen in p.
* of r Als Z . *::::. r, dan r E IT Als sing
z =>*
= sB
* BE met s E IT'
Iw
* dan bestaat een afleiding uit een aantal malen toepasr, r E IT'
van een regel van de gedaante (A, qB) (dit aantal kan nul zijn) , ge-
volgd door één toepassing van een regel van de gedaante (A,q). We willen nu aantonen dat we ons kunnen beperken tot het geval dat voor alle regels varc de gedaante (A,qB) geldt de gedaante (A,q) geldt i(q)
= O,
~(q)
= 1 en voor alle regels van
zonder dat daardoor de klasse der gege-
nereerde talen wordt verkleind. We zullen zulke regels tijdelijk "toegelaten" regels noemen: (A,aB) of (A,A) met A E IN' B E IN, a E IT. De overige regels noemen we "verboden": (A,qB) met i(q);;. 2, (J\,q) met Stelling 5.1.
~(q);;. 1,
(A,B).
Bij iedere grammatica G van type 3 bestaat een grammatica G'
van type 3 zo, dat L(G') = L(G) en alle regels vanG' de gedaante (A,aB) of (A,A) hebben met A E I , B E IN, a E IT. 11
- 24 -
Bewijs: 1.
We onderscheiden twee gevallen.
Alle verboden regels van G zijn van de gedaante (A,B). We passen dan volledige inductie toe naar het aan1ial hulpsymbolen, die in rechterleden van verboden regels voorkomen.Als dit aantal nul is, dan zijn er geen verboden regels en kiezen we G'
= G.
Als het aantal
>o
is kiezen we een hulpsym-
bool C, dat in een rechterlid van een verboden regel voorkomt. We construeren een grammatica
G", die alleen in de verzameling regels vanG ver-
schilt. Deze verzameling
regels krijgen we door wijziging van de verza-
meling regels van G en wel dc.or voor iedere regel van de gedaante (P,C) in G deze regel weg te laten en voor iedere regel van de gedaante (C,r) met r # C in Geen overeenkomstige regel (P,r) toe te voegen. Het is duidelijk dat ook in G" alle verboden regels van de gedaante (A,B) zijn en dat het aantal hulpsymbolen, die in rechterleden van verboden regels voorkomen één minder is dan bij G. Op grond van de inductieveronderstelling is er een grammatica G' met uitsluitend toegelaten regels zo, dat L(G')
= L(G"),
We tonen aan dat L(G")
= L(G).
Stel eerst x E L(G") en
beschouw een afleiding van x behorend bij G". Als bij een stap van die afleiding een regel is toegepast, die geen regel van G is, dan is dat een regel van de gedaante (P,r) als hierboven ingevoerd en de afleidings-· stap is uP, ur. Bij G kan dit door twee afleidingsstappen worden vervangen: uP, uC, ur. Zo kan de afleiding omgezet worden in een afleiding bij G, zodat x E L(G). Gaan we omgekeerd uit van x E L(G) met een afleiding bij G, dan mogen we aannemen dat bij de afleiding geen regels van de gedaante (A,A) zijn"toegepast, omdat zo'n toepassing de symboolrij niet verandert en de bijbehorende stap dus overgeslagen kan worden.Een toepassing van een regel die niet in G" voorkomt, gebruikt een regel (P,C) en de afleidingsstap is uP, uC. De volgende afleidingsstap levert dan ur, met toepassing van een regel (C,r) met r ~ C.
- 25 -
In
kunnen deze twee stappen tot f~n samengetrokken worden:
G"
uP, ur met toepassing van de regel (P,r). Zo wordt de afleiding omgezet in een afleiding bij G", zodat x E L(G"). Daarmee is L(G") getoond en dus ook L(G') 2.
= L(G)
aan-
= L(G),
In G komt een verboden regel voor die niet van de gedaante (A,B) is. We passen nu volledige inductie toe naar het aantal verboden regels.We beschouwen eerst het geval dat er een regel is van de gedaante (A,qB)
alle in IT. We definiëren nu ee:n grammatica G". De verzameling hulpsym-
bolen bestaat uit de hulpsymbolen van G met daaraan toegevoegd f-1 nieuwe
x0 , ••• ,xf_ 2 •
hulpsymbolen
De verzameling regels ontstaat uit de verzame-
ling regels vanG door de regel
(A,~
0
•••
1
~f_ B)
weg te laten en de vol-
gende regels toe te voegen: (A,~OXO)
x.
(X.,~. ) J J+ 1 J+ 1
voor jE {O, ••• ,f-3},
(Xf-2'~f-1B) Het is duidelijk dat in G" het aantal verboden regels één minder is dan in
G, zodat op grond van de inductievenonder-stelling of op grond van geval een grammatica G' met uitsluitend toegelaten regels bestaat zo, dat L(G') = L(G"). We tonen aan dat L(G") = L(G). Stel eerst x E L(G) en beschouw een afleiding van x bij G, Een toepassing van de regel (A,~
0
•••
1
~f_ B)
kan bij G" door i stappen vervangen worden die successie-
velijk de bij deze regel oeherende i regels gebruiken. Daaruit volgt dat x E L(G"). Omgekeerd stel x E L(G") met een afleiding bij G", Toepassing van regels van G kan nooit één van de nieuwe hulpsymbolen opleveren. Als
- 26 -
in de afleiding regels worden toegepast die niet in G voorkomen, dan moet dit de eerste maal dat dit gebeurt de regel (A,I; x ) zijn. Er is 0 0 slechts één regel die
x0
in het linkerlid heeft enz. Zo voortgaande
ziet men, dat het bovenstaande rijtje regels in volgorde achter elkaar moet worden toegepast. In G kunnen deze
t stappen vervangen worden
door de ene stap met toepassing van (A,i; ••• 1;t_ B). Door herhaalde 1
0
toepassing vinden we een afleiding bij Gen dus x E L(G). Daarmee is L(G") = L(G) aangetoond en dus ook L(G') = L(G). Het geval dat we een verboden regel hebben van de gedaante (A,1; met
t
~ 1
wordt op analoge wijze behandeld met
0
••• 1;t_ ) 1
t nieuwe hulpsymbolen
(A,I;OXO) ' (X.,I;.
x.
J+ 1 J+ 1
J
) voor jE {O, ••• ,t-2}
,
(Xt-1 ,A) • I
We werken dit niet verder uit. Als een grammatica G van type 3 uitsluitend toegelaten regels heeft, dan bestaat een afleiding van een woord x E L(G) uit t(x) + 1 stappen. Na k stappen (k
~
t(x)) is een woord verkregen van de gedaante
uA
* met u E IT'
l(u) = k, A E IN en u is een beginstuk van x. Stelling 5.2. Bewijs:
L3 = verzameling der reguliere talen.
Stel 1 E L3. Op grond van Stelling 5.1 bestaat er dan een gram-
rnatic a G van type 3 zo, dat L = L(G) en alle regels van G zijn van de ge-
daante (A,aB) of (A,A) met A E IN' B E IN, a E IT. We definiëren een eindige automaat A = <S,IT,ó ,s ,F> door S:= P( IN), ó (V ,I;):= {B E IN/3CEV[( C,I;B) ER]) 0 voor V ES, I; E IT' s := {Z}, F:= {V E S/3CEV[(C,A) ER]). Met recurrentie 0
- 27 -
langs de opbouw van x E IT* bewijst m<en dat ó(s ,x) 0 daaruit volgt ê(s ,x) E F 0
L(A)
~
* xB 3BEI [Z ~ N G
A
= {BE
(B,A) t R] ,
~
Z
INiz
* xB} G
*G x,
dus
~
en
= L(G) = L.
Stel nu omgekeerd L regulier. Er bestaat dan een eindige automaat A= <S,I,ó, s
0
,F> zo, dat L
= L(A). We mogen veronderstellen dat
Sn
*
I=~;
anders vervangen we S door een andere verzameling met aanpassing van ó, s
0
en F. We definiëren nu een grammatica G als volgt: IN:= S, IT:= I, Z:= s , 0 R:= {(s,~ó(s,~llls ES,~ E IT} U {(s,Alls E F}. Het is duidelijk datGeen grammatica van type 3 is. Verder geldt voor s E S, x E IT*
dat
(ê(s,x),~ó(s,xé)) ER. Stel nu x.= 1; ••• ~!'.- EL(A), dan levert Xj:= 1 0
: = ~ ••• ~ j- ó ( s .~ •• • r; j-, ) voor j E { 0, ••• 1 0 0 0 1
x0 , ••• ,Xf+ 1 van
x
,0 en Xl'.+ 1 :=1; 0 ••• ~f- 1 een afleiding
bij G. Stel nu omgekeerd x , ••• ,Xf+ 0
1
van ~o···~f_ , dan geldt Xj
1
= ~ 0 ••• ~j_ 1 ó(s 0 ,~ 0 ••• ~j_ 1 )
een afleiding bij G voor jE {O, ••• ,f}
0
en ó(s 0 ,~ ••• ~f- 1 ) E F.
1
Samenvattend kunnen we stellen dat de Stellingen 3.1, 4.2, 4.4 en 5.2 ons in totaal vijf verschillende karakteriseringen van reguliere talen hebben opgeleverd (inclusief de als definitie gekozen karakterisering). Het voordeel is, dat we in elk voorkomend geval kunnen kiezen welke karakter1sering ons het beste uitkomt. Dat het complement van een reguliere taal regulier is volgt gemakkelijk uit de definitie of uit Stelling 3.1 (index(eL)
= index( er*\L)).
=
Dat de gespiegelde van een reguliere taal regulier is ·Jolgt
gemakkelijk uit Stelling 4.2 of 4.4 (zie ook Stelling 4.3). Dat een reguliere taal contekstvrij is volgt direct uit Stelling 5.2. Men kan ook een grammatica spiegelen: een grammatica·Gveranderen in een gram-
T T
matica G' door iedere regel (p,q) te vervangen door (p ,q ) • Het is duide·lijk dat L(G') = (L(G) )T. Doet men dit met een grammatica van type 3 dan
- 28 -
ontstaat een grammatica, waarvan de
re~els
van de gedaante (A,Bq)
of~,q)
* zijn; een dergelijke grammatica wordt linkslinemet A E JN' B E IN' q E IT air
genoemd, Omdat grammatica's van type 3 reguliere talen opleveren en
gespiegelden van reguliere talen weer regulier zijn leveren linkslineaire grammatica's ook
reguliere
talen op. Stopt men echter rechtslineaire en
linkslineaire regels in één grammatica, dan hoeft dit niet meer het geval te zijn, Zo genereertdegrammaticametiN={Z,A},IT = {a,S}, R = ={(Z,aA),(A,ZS),(Z,A)} de taal {anSn!n E lN }, die niet regulier is. Het is duidelijk dat de gespiegelde van een contekstvrije grammatica contekstvrij is. Dit levert de volgende stelling, Stelling 5.3. taal.
Als L een contekstvrije taal is, dan is LT een contekstvrije
- 29 -
HOOFDSTUK 2. CONTEKSTVRIJE TALEN
§6. INLEIDING In §1 is vastgesteld wat een contekstvrije grammatica is: alle regels zijn van de gedaante (A,~) met A E IN' q E I * , Bij een afleidingsstap wordt een hulpsymbool A vervangen door
~.
ongeacht de rest van de symboolrij waarin
deze A voorkomt; dit verklaart de term "contekst vrij". Dit contekstvrije
karakter maakt het mogelijk om een afleiding op een andere wijze te beschouwen. We leiden dat in met een voorbeeld van een afleiding, waarin we de optredende symboolrijen onder elkaar schrijven en met streepjes aangeven,
hoe de regels worden toegepast. Toegepaste regel:
f·"" s B
(Z,eAB)
A
I s I s I s I s
~~
(A,yo;A)
I I t"- \ T ïï ~~ y a e c a I I I I I I I
(A,o;o;)
y a AB
(l
ï
(B,SCo;)
(l
(c, y)
yo;ao;Syo;
Als men deze "boom" bekijkt, krijgt men de neiging de overgangen waarbij .niets verandert weg te laten en kortweg de volgende figuur te tekenen:
z
/I""'
s IÎ\ ~
yo;ASCa
/\Iy
(l
(l
Aan deze boom is wel te zien welke regels zijn toegepast en hoe de regels zijn toegepast, maar niet in welke volgorde, Deze boom kan dan ook een andere afleiding·horen, bijvoorbeeld:
b~j
- 30 -
Toegepaste regel:
z
~~B
(Z,BAB)
lil~ A B C <>
(B,BC<>)
S
~I ~~~~>-" I I I I I I
B
y
B
y
I
I
(A, ye>A)
(c 'y)
A
B y " "I " ~~~"'y~
(A,<><>)
Het eindresultaat is hetzelfde, maar de symboolrijen die in de tussenstappen optreden, zien er heel anders uit. We wensen nu deze twee afleidingen als niet essentieel verschillend te beschouwen; Dit betekent, dat we de hierboven afgebeelde
ingekorte boom als datgene opvatten, waarin alle essentiële
informatie betreffende de afleiding is weergegeven. Onder meer volgt daar-uit ook het afgeleide woord SyaaaBya , We willen een dergelijke afleidingsboom nu ook formeel beschrijven. Voordat we dit doen willen we nog op een verschijnsel wijzen. Hierboven hebben we gezien, dat bij verschillende afleidingen dezelfde afleidingstoom kan behoren. Het is echter ook mogelijk dat bij verschillende afleidingstomen dezelfde afleiding hoort. In een afleidingsstap X. • X. J
J+ 1
wordt een afleidingsregel toegepast: XJ. =rAs,
rqs, (A,q) een regel. De vraag is of het mogelijk is om in X. op een J
andere plaats een regel toe te passen zo, dat dezelfde X.
J+ 1
Als voorbeeld nemen we een regel (A,A) en een overgang Als k
> 1,
wordt verkregen. k
k-1
rA s =>rA
s.
is niet vast te stellen op welke A de regel 1s toegepast. Een
ander voorbeeld krijgen we als we beschikken over regels (A,AaB) en (B,B<>B). Nu gaat rAaBs met de eerste regel over in rAa8e>Bs, maar met de tweede regel eveneens. Aan deze voorbeelden zien we, dat bij gegeven afleiding de plaats, waar de regel bij een stap wordt toegepast, niet hoeft vast te liggen; bij zulk een afleiding behoren verschillende afleidingsbomen.
- 31 -
Het is mogelijk om aan de regels beperkingen op te leggen, waardoor bovengenoemd verschijnsel onmogelijk wordt gemaakt. Als voor een regel (A,q) geldt q # A en het voorste en het achterste symbool van q zijn # A, dan ligt bij toepassing van deze regel de plaats waar een regel wordt toegepast vast. Immers, stel
rAs~
rijs en hetzelfde effect kan worden verkregen door
toepassing van een regel op een andere plaats. Als die plaats in r valt, blijft het gedeelte rechts van die plaats onveranderd in strijd met het feit dat het achterste symbool van q #A is. Analoog als de plaats in s valt. Voor de beoogde toepassingen is het echter niet gewenst om de genoemde beperking op te leggen. Men noemt regels van de gedaante (A,Ar) linksrecursief en regels van de gedaante (A,rA) rechtsrecursief; dergelijke regels en ook regels met leeg rechterlid komen in toepassingen veel voor.
Men kan echter het verschijnsel ook bestrijden door het begrip afleiding te verfijnen en in de afleiding zelf aan te geven, waar de regel wordt toegepast. Dit leidt tot een gespecificeerde afieiding. Ter inleiding schrijven we een afleiding als volgt: Z ~ r0
= u 1A1v 1 •
u 1r 1v 1
= u 2 A2v 2
• u 2 r 2 v 2 • ••• ~ ~-lrk-lvk-l
~ ~rkvk met toepassing van de regels (z,r ), (A r
0
1 1
= ~~vk ~
), ••• ,(~,rk). Om de
eerste stap geen uitzonderingspositie te geven voeren we nog in A ··- Z, 0
u
0
= v 0 = A.
Verder geldt
~rkvk
E IT* . Dit leidt nu tot de volgende formele
definitie. Definitie gespecificeerde afleiding Stel een contekstvrije grammatica G
=
• Een gespecificeerde af-
leiding bij G bestaat uit k E lli, uo,··· ,~, VO'" .. ,vk, alleE I
*'
- 32 -
(A ,r ), ••• ,(~,rk), alleE R', 0 0 A0 " Z, 'lo
= v0
" A, '\.rkvk E IT* ,
ujrjvj ~ uj+lAj+lvj+l voor jE {0, ... ,k-1} Bij een gespecificeerde afleiding behoort een afleiding
x0 = Z,
x0 , ••• ,~+l'
waar1n
Xj+l = ujrjvj voor jE {O, •.. ,k} . Het woord '\.rkvk heet het ~fge
leide woord van de gespecificeerde afleiding. We kunnen bij een afleiding de keuze van het te vervangen hulpsymbool vastleggen door de afspraak steeds het meest linksstaande hulpsymbool te kiezen. De gespecificeerde afleiding wordt dan linkspreferent genoemd; aan de
ei~en
* voor een gespecificeerde afleiding wordt dan toegevoegd: u , ••• ,'\. alleE IT. 0 We verwachten dan een bijectieve betrekking tussen linkspreferente gespecificeerde afleidingen en afleidingsbomen. De laatste gaan we nu definiëren. Een boom is een speciaal geval van een graaf en bestaat uit knopen en takken. In ons geval is er een knoop, waar de afleiding begint, die we de wortel van de boom kunnen noemen. Bij iedere knoop hoort een symbool, maar hetzelfde symbool kan meermalen voorkomen. We kunnen de symbolen dus niet als namen voor de knopen gebruiken; de knopen zijn echter wel gemerkt (Engels: labeled) met symbolen. Uitgaande van de wortel zijn de knopen te verdelen in horizontale lagen, waarin ook een volgorde van links naar rechts is vastgelegd. Dit beschrijven we door de knopen te coderen met rij en natuurlijke getallen, waarbij de met een knoop met code r verbonden volgende knopen als code krijgen r gevolgd door 0,1, • • • • De wortel geven we de lege rij A. Let wel dat deze codering ook de takken van de boom vastlegt. Voor de formele beschrijving noemen we
m*
de verzameling van de eindige rijen natuurlijke getallen
~
33 -
inclusief de lege rij A. We schrijven zulke rijen met een komma als scheidingssymbool, bijvoorbeeld 2,6,13,4. Ook voor de concatenatie van zulke rijen gebruiken we een komma: als r en s zulke rijen zijn, dan is r,s de concatenatie van beide. Voor een afleidingaboom is er nog een functie f
nodig, die vastlegt welke symbolen aan de knopen worden gehecht; tenslotte moet de vertakking bij iedere knoop corresponderen met de toepassing van regels uit de grammatica en moet de boom een uit eindsymbolen bestaand woord opleveren.
Allereerst definiëren we nog twee afbeeldingen. AlsBeen eindige deelverzameling van lN * is definiëren we DB : lN*
-+
P( JN) en v B : lN*
-+
lN door
voort E lN * te stellen DB(t):= {n E lN lt,n EB} en vB(t):= #DB(t). Definitie afleidingaboom Stel een contekstvrije grammatica G = . Dan heet T =met B c lN * en f : B ~
-+
I een afleidingaboom als geldt:
0 ,
1•
B eindig, B
2.
als t E lN * ' n E lN en t,n E B, dan t E B,
3.
als t E B, dan DB(t)
4.
f( A) = Z
5.
6.
= {n
E JNI n < vB(t)}
'
' als t E B, f( t) E IT' dan vB(t) = 0 ' als t E B, f( t) E IN' dan (f(t) ,f(t ,o) ... f(t>rB(t)
-
1)) E R.
- 34 -
We maken enkele opmerkingen over deze definitie. Als t E lN *
s E lN * en
t,s E B, dan t E B. Dit volgt met recurrentie langs de opbouw van s uit voorwaarde 2. We noemen t een antecedent van t,s,, mits s f. A. Omdat B f. !/!, geldt dus ook A E B; dit zorgt er voor dat f( A) in 4. gedefinieerd is. Voorwaarde 3. garandeert dat de in 6. voorkomende toepassingen van f gedefinieerd zijn. Als tE Ben u een antecedent van t, dan f(u) E IN. Immers, er is eens#- A zo, dat t = u,s, dus er is een j C lN zo, dat u,j een ante-
cedent van t of t is. In ieder geval is u,j E B en u E B; nu levert voorwaarde 5., dat f(u) E IN. Het is toegestaan, dat als f(t) EINde vB(t) in dat geval onstaat er in
= 0;
6. een regel met een leeg rechterlid: (f(t),A).
Soms geeft men een wat zwakkere definitie, waarbij men niet de eis stelt
dat de knopen, die met een gegeven knoop door een dalende tak zijn verbonden, opeenvolgende nummers krijgen: men laat daarin lacunes toe. Dit bete-
kent, dat voorwaarde 3.vervalt, maar dit leidt ertoe dat voorwaarde 6. anders geformuleerd moet worden. Daartoe hebben we de behoefte aan een rangschikkingsfunctie, die we ook voor andere doeleinden kunnen gebruiken. We nemen daarbij als bekend aan, dat men een eindige totaal geordende verzameling zo kan nummeren, dat de ordening van de nummers correspondeert met de
ordening in de verzameling. Formeel: als
een
eindige totaal geordende
verzameling is, dan bestaat er één en slechts één bijectie
rD: (n E JNj n<#D}-+ D zo, dat als k E JN,i E lN, k rD(k)
< rD(.e).
< .e < #D,
dan
In het bijzonder geldt dit als D c lN, D eindig. De afbeel-
ding rD hangt behalve van de verzameling D ook van de ordening van D af. We vervangen
6. nu door
6'. als tE B, f(t) E IN' dan(f(t),f(t,rD (t)(O)) .•• f(t,rD {t)(vB{t) -1)) ER. B
B
- 35 -
Als we in de definitie van afleidingsboom de zes voorwaarden vervangen door
1.,2.,4.,5.,6'. dan spreken we van een quasi-afleidingsboom. Het is mogelijk om een quasi-afleidingsboom om te zetten in een afleidingsboom; daarbij verandert het straks te definiëren afgeleide woord niet. Dit gaan we niet na. In JN * voeren we de bekende lexicografische ordening 1n. Voor r E JN * , s E JN * geldt r < s dan en slechts dan als: t,i,u en s
t,j,v en i< j]
of 3tEJN* [t
# A en
s
r,t] •
Dit is een totale ordening van JN *
Om het afgeleide woord van een afleidings-
boom te vinden, nemen we de verzameling E:= {tE B[f(t) E IT} en vormen een woord door de labels van de knopen in E achter elkaar te zetten corresponderend met de lexicografische volgorde van de elementen van E:
f(r (0)) .•• f(rE(#E- 1)) • Het zal blijken, dat dit woord in L(G) zit. 8
§1. AFLEIDINGEN EN AFLEIDINGSBOMEN We leggen nu een verband tussen afleidingsbomen en gespecificeerde afleidingen. We beschrijven daartoe twee constructies. Constructie I maakt bij een gegeven afleidingsboom een linkspreferente gespecificeerde afleiding, waarbij hetzelfde afgeleide woord behoort. Constructie II maakt bij een gegeven gespecificeerde afleiding een afleidingsboom, waarbij hetzelfde afgeleide woord behoort. We tonen echter ook nog aan, dat de twee constructies in zekere zin elkaars inverse zijn. Passen we op een afleidingsboom construc-
tie I toe en op de daaruit verkregen afleiding constructie II, dan krijgen we de gegeven afleidingsboom terug. Gaan we uit van een linkspreferente
- 36 -
gespecificeerde afleiding, passen we daarop constructie II toe en op het resultaat daarvan constructie I dan komt er de gegeven afleiding uit. Het uit te voeren programma kan worden weergegeven in het volgende schema. constructie I afleidingsboom constructie II gespee. afl.
afleidingsboom I
afl. boom
linkspref. gespec.afl.(zelfde afgeleide woord)
--+
(zelfde afgel.woord)
II
gespec.afl. --+afl. boom I
linkspref.gespec.afl.
-+
(zelfde afl. boom)
II
afl.boom
~
gespec.afl. (zelfde gespec. afleiding)
Als dit voltooid is, is het onverschillig of men met een afleiding dan wel met een afleidingsboom werkt, omdat men desgewenst van de ene op de andere kan overstappen. De keuze geschiedt op pragmatische gronden. We gaan nu constructie I beschrijven. Er is dan een afleidingsboom gegeven en we moeten komen tot een gespecificeerde afleiding u , •••• De letters, 0 die in die woorden voorkomen, worden verkregen door de labels te nemen van knopen uit B. Als tussenstap voeren we daarom rijen knopen u , ••• 0 zijn in feite elementen van ( lN * ) *
in, dat
Om verwarring te voorkomen gebruiken
we bij de laatste rijvorming de puntkomma als scheidingssymbool. Voorbeeld: 0,2,1;1,0;3,1 ,2;1;A;2,3. Wat tussen de puntkomma's staat zijn elementen van lN * ; deze zullen we in het vervolg in oneigenlijke zin ook letters noemen. Ook de concatenatie in ( lN * ) * wordt met puntkomma aangeduid. Er is nog een moeilijkheid met het lege woord. In lN * zit het lege woord A dat dus als letter in een rij uit ( lN * )* kan worden gebruikt, zoals trouwens in het gegeven voorbeeld ook gebeurd is. Daarnaast is er ech-
- 3\ -
ter ook het lege woord in ( lN * ) *
ter onderscheiding zullen we dat met A
aanduiden.
Laat nu een afleidingsboom
en dus ook een contekstvrije grammatica
gegeven zijn. Definieer no:= vB(A), dan no E lN
-
* ro E B
. Verder Ao:=
A, uo:= !:_, -vo:= !:.· We
gaan
-
en ro:= O; ••. ;n -1, dan 0 nu een inductief proces
toepassen, waarvan we de inductiestap beschrijven. Stel j E lN, j u.
r
1
,r.
r
1
,v.
J- 1
>0
en
, A. 1' n. 1 verkregen zo' dat u. 1; r. 1; v. 1 E B* , JJJJr
--;::-:--1 E B , f ( --;::-:-- ) E IN' nj-1 = vB(Aj-1) en voor alle letters t in u. 1 r J- 1 r
geldt f(t) E IT' Merk op, dat dit bij het begin van het proces voor j = geldig is. Als voor alle letterstin u.
r
1
; r.
J- 1
; v.
r
1
geldt, dat f(t) E IT
dan stellen wek:= j-1 en breken het proces af, Zo niet, laat dan A. de meest linkse lettert in
J
--u. ; r. ; J- 1
v. zijn, waarvoor f(t) E IN en maak r 1 J- 1
--
= ~; ; r. ; v · de concatenatie u. J- 1 J- 1 J- 1 J
A":; -;-:. J
J
Dit definieert u. en v .. J J
Verder definiëren wen.:= vB(~) en -r:-:= ~.o; ... ;~,n.-1. Dit alles volJ J J J J J doet aan de voorwaarden van de inductiestap met j vervangen door j+1.
Bij een inductiestap kan het proces afbreken of doorgaan. We willen aantonen dat het proces na eindig veel stappen afbreekt, We doen dit door te laten zien dat steeds "nieuwe" knopen van de boom worden gebruikt. In het bij-
zonder blijken de ~ verschillend te zijn. Om dit te bereiken hebben we J
enkele hulpstellingen nodig, die zelf weer met inductie worden aangetoond. We zullen deze hulpstellingen echter later nogmaals willen gebruiken en maken ze daarom los van de constructie, waar we nu mee bezig zijn. We formu-
leren eerst een aantal voorwaarden voor de drie hulpstellingen gezamenlijk; deze voorwaarden zijn bij de nu in het geding zijnde constructie vervuld, Deze voorwaarden luiden:
- 38 -
j doorloopt lN of de natuurlijke getallen .;; k; n . E 1i, A . E JN * , r . en u. en v . alle E J
A0
J
= A, uo
J
=V
0
J
J
(lN *) *
= -A A., n.-1
J
voor j
J
1 0: ~1; ;:-1; -;;:-1 Jr J-
=
Hulpstelling 7.1. In u.; r.; v. zijn de letters lexicografisch opklimmend J
J
J
geordend; geen der letters in de rij is antecedent van een letter in die rij.
Bewijs:
Volledige inductie naar j; j " 0 is triviaal. Stel nu j > 0 en
de bewering juist voor j-1. Er geldt nu
l
(*)
u.; r j; v. = u.; A.,o; •.. ; A.' n .-1; J
J
u 0; A.; V. J J J
J
J
J
J
V.
J
uj-1; r j-1; V. 1
r
De inductiestap is nu eenvoudig U:it te voeren. In de volgende hulpstellingen zijn er
l
I
en j, die beide aan de hierboven
geformuleerde voorwaarden voor j voldoen, Hulpstelling 7.2. A. en alle antecedenten van A. komen niet als letter voor l
in u.; r.; v. voor alle j J
J
J
1
~i,
Als i # 0 dan komt A. als letter voor in 1
ui-1; ri-1; vi-1· Bewijs:
De tweede bewering is triviaal. De eerste bewering bewijzen we met
volledige inductie naar j, Voor j =i gaan we uit van u .; r 1
.; 1
v . =u.; A. ,0; ,.. ; A., n.-1; v., 1
~1.
1.1.
Als n. > 0 dan volgt de bewering ~
1
direct uit hulpstelling 7.1. Als echter n. = 0, dan is r. =~·Als nu i> O, 1
dan
l
volgt de bewering uit ui; Ai; vi = ui_ 1 ; ri_ 1 ; vi_ 1 en hulpstelling 7.1 .
.... ·, " ....
- 39 -
Als echter i nu j lS
>i
= 0,
dan u. l
=v. = ~
en de bewering is triviaal. We stellen
l
en nemen aan dat de bewering voor j-1 geldig is. De inductiestap
nu eenvoudig uit te voeren met de in het bewijs van hulpstelling 7.1 I
opgeschreven formules(*). Hulpstelling 7.3. Bewijs:
Als i
~
Ai~
j, dan
Stel i< j, dan levert hulpstelling 7.2:
A. komt niet als letter voor in u.
J- 1
l
A. komt wel als letter voor in u.
J- 1
J
Dus
Aj.
; r.
J- 1
; r.
J- 1
; v.
J- 1
; v.
J- 1
,
•
A.# A:. l J
I
We keren terug tot het constructieproces. Uit hulpstelling 7.3, uit het feit dat alle
A: J
knopen van B zijn en B eindig is, volgt dat het proces af-
breekt en ons oplevert een k E JN en u , ••. , ~, v , ••• , vk, r , • •• ,rk, 0 0 0
A , ••• ,Ak. We krijgen nu de overeenkomstige u , ••• 0 0
zonder
overstreping
door letter voor letter de afbeelding f toe te passen. Dat dit een linkspreferente gespecificeerde afleiding oplevert is eenvoudig na te gaan. We moeten nog aantonen dat
~rkvk
het afgeleide woord van de afleidingsboom
is. In~; rk; vk zijn de letters lexicografiech geordend (hulpstelling 7.1) en hun labels zijn eindsymbolen op grond van de constructie. We zijn klaar, als we aantonen, dat als tE B, f(t) E IT' dan komt t
als letter voor
in~; rk; vk. Dit volgt uit hulpstelling 7.4, die wel afhangt van de be-
schreven constructie.
Hulpstelling 7. 4.
Stel t E B, t 1/. { A , ••• ,~}. Als j E JN , j ,.; k, dan komt 0
t of een anteceà.ent van t als letter voor in u. ; r. ; v .. ,l
J
J
- 40 .
.:
Bewijs: t
i
:
~\
We passen volledige inductie naar j toe; eerst j ; 0. Omdat
A ; A, 0
'is er' een h E lN zo, dat h antecedent van t of t is. Omdat
tE B, geldt hEB, h
>0
Stel nu j
en
< vB(A),
-~e·· bewering
dus h komt
juist voor j-1. We gebruiken weer de formulen
(*) uit het bewijs van·· hulpstelling 7.1. Als t of een antecedent van t als
letter in u. of~ zit zijn we klaar. Als dat echter niet zo is, volgt uit J
J
t # A. en de inductieveronderstelling dat A. J
J
Dan 1s er een i E lN zo, dat A.,i J
A."", i ,,1
E Bt
n u. ; r J
ct~ tS
:
i
< vB(Aj)
een antecedent is van t.
een antecedent vantaft is. Maar dan geldt
n., dus A.,i komt als letter voor in r. en dus J
J
J
I
"J • ~
J
Uit hulrc,t.ell ing 7. 4 volgt, dat als t E 3 en f( t) E IT, df'n\. van '/~.n
,,,
1•
1
::....~~.s
t
of een antece-
ietter voorkomt in uk; rl:; vk, meer voor een antecedent s
geldt :·{~;) E ii~
--
1
K_;.,r'l~~n_. tl.1::t i::· du::. t
()',_, .-'" . :n goe{: einc'
hr:::tgeer) niet geldt voor de letters, die in'\.; rk; vk zelf die daarir. voorkomt. Hiermee is constructie I
.;':...•!'C.-:!!"1~·.
\'oor "'.ater gebru2..k tonen we nog aan dat A0 , •. • ,~
\I
o; .. L
·.... ri.
v 1..aa.1.. è:cel
r'!U
f\ t)
- .:.N
·,· rJ <: k • jf.lN ' '
'*
t -' 7\:]. Nu ,. J
I
- 41 -
We gaan nu constructie II beschrijven. Daartoe willen we definiëren wat de J.e letter in een woord is, zowel voor de woorden in I * als die in ( lN* ) * met
betrekking tot ; als scheidingssymbool. Stel S een verzameling symbolen; we definiëren s.(x) voor x f S* , jE lN, J
j
< ~(x)
door recurrentie langs de opbouw van x:
Stel x E S* , é E S, dan definiëren we [ sj(x) als j
s .(xé) ;; J
l
é
als j
<~(x) , = ~(x).
i <
,<
Let wel dat voor A niets gedefinieerd hoeft te worden; s (é) 0
s (én) ; n, enz. 1
Bij constructie II 1s een gespecificeerde afleiding gegeven, die niet linkspreferent hoeft te zijn. Het doel is het definiëren van een afleidingsboom. Als tussenstap gaan we weer overstreepten ·u , ... 0
invoeren, dat zijn
elementen van (JN * ) * van dezelfde lengte als de overeenkomstige u , ••. 0 Dit gaat als volgt.
;! i'
We doen een inductiestap. Stel jE lN, 0 < j
~ken
Aj_ , uj_ , vj_ , rj_ 1 1 1 1
reeds gedefinieerd en van de goede lengte. Er geldt uj_ rj_ vj_ ; u.A.v .. 1 1 1 J J J Omdat de lengtes bij de index j-1 goed zijn, kunnen we stellen u. 1; r. 1 ;
J-
J-
J- 1
V.
;
u.; Aj; v. en daarmee u. en A. en v. van goede lengte ,)
J J J J definiëren. Daarna definiëren we r. := ~,0; ... ;~,f(r.)- 1. Daarmee zijn J J J J de overstreepten gedefinieerd. De definitie garandeert, dat ze voldoen aan
devoorwaardenvanhulpstellingenT.1,
"(.2
en 7.3 met n. = f(r.) dus ook aan J
J
die hulpstellingen zelf. In het bijzonder zijn de A , ... ,Ak verschillend. 0
- 42 -
We gaan nu de boom definiëren. In B nemen we op A en alle letters, die in r 0 , ••• ,rk
voorkomen. Dan geldt dat alle letters die in u , .•• 0
,~,
v , ••• ,vk voorkomen in B zitten en dat A , •.• ,~ in B zitten. Dit is een0
0
voudig met volledige inductie in te zien. De letters die in verschillende ~voorkomen zijn echter verschillend, en verschillend van A. Immers, stel J
dat t voorkomt in ri en u in rj, dan zijn er h E lN en mE lN zo, dat en u= A.,m. In ieder geval is dan t #A ent= u leidt tot A~ =A.
t =A. ,h
J
1
1
en dus tot i = j. Op grond hiervan en van het feit dat een letter ten hoogste één maal in r.
J
voorkomt, is de volgende definitie van f gerecht-
vaardigd. f(A):=Z
= s.(r.) 1 J
f(s.(i=":")) 1
J
voor i< t(r.), j J
Dan geldt echter ook f( s. (\l:") ) = s. (u.) voor i
voor j " k
.
Dit bewijst men met volledige inductie naar j. Daarbij levert j = 0 alleen f(A ) = f(A) = Z = A • Stel nu j > 0 en de bewering waar 0
0
voor j-1. Dan is
;r.-
; -;;-:--- )) = s.(u. r. v. ) = s.(u.AJ.v.). f(s.(\l:";A.;V.) = f(s.(u.1 J J J 1 J- 1 J- 1 J- 1 1 J- 1 J- 1 J- 1 1 J J Op grond van de goede lengtes geldt dan ook f( s. (\l:")) = s. (u. l, r(A.l = A. 1 J 1 J J J en f( s. (V.)) = s. ( v.) 1
J
1
J
We tonen nu aan dat een afleidingaboom is. Voorwaarden 1. en 4. zijn triviaal. Stelnut € lN * , n € lN en t,n € B, dan is t,n # A, dus is er een j € lN zo, dat t ,n als letter voorkomt 1n r. • Daaruit volgt direct J
J
- 43 -
dat t
= A.J
en n
< i(r.). J
volgt eruit dat vB(Aj)
Hieruit volgen voorwaarden 2., 3. en 5. Verder
= i(r.).
We tonen nu aan dat als t E B en f( t) E IN
J
= AJ.•
er een j E lN bestaat zo, dat t
= h,
Als narnelijkt
dan t
= Aa·
Als
# A, dan bestaat er een h E lN, 1 .; h .; k, zo, dat t als letter
echter t
voorkomt in ~- 1 ; rh_ ; vh_ 1 en niet als letter voorkomt in~; rh; vh. 1
Dit is zo, omdat, wegens f(t) E IN' t niet als letter voorkomt in ~;rk;vk en wel in
dat t =
~én
------= ~; ~; vh volgt
der r .. Omdat ~- ; rh_ ; vh_ 1 1 1 J
hieruit
~·
Stel nu t E B, f(t) E IN en kies
= AJ..
zo, dat t
j
Dan geldt
(f(t),f{t,O) ••• f(t,vB{t)- 1)) = (f(A.),f{s 0 (r.)) ..• f(sn( ) 1 (r.))) = J J ~ rj J = (A.,s (r.) ••• st( ) (r.)) = (A.,r.)ER. 0 J J rj - 1 J J J
Daarmee is ook voorwaarde 6. aangetoond. Dus
is een afleidingsboom.
We moeten nu nog aantonen dat het afgeleide woord hetzelfde is. Bij de gespecificeerde afleiding is het
~rkvk. Beschouw~;
rk; vk. Hierin zijn de
letters lexicografisch geordend (hulpstelling 7.1); het zijn knopen van de boom en f voert ze over in de overeenkomstige letters van
~rkvk'
hetgeen
elementen van IT zijn. Het enige dat we nog moeten aantonen is, dat iedere
t EB waarvoor f(t) E IT' als letter in~; rk; vk voorkomt. Voor zulk een t
geldt t # A, dus er is een h E lN zo, dat
t
als letter in rh voorkomt.
Dan komt t ook als letter voor in u.; r.; v. voor alle j E lN met h .; j .; k. J
J
J
Dit bewijzen we met volledige inductie naar j. Voor j h
<j
=h
klopt het. Stel
.; k en de bewering waar
V. •
J
Wegens f(t) E IT is t # Aj. Op grond van de inductieveronderstelling komt t
als letter voor in u.; v. J J
en dus 1n u.; r.; v .. Het geval dat j = k is
levert de gewenste bewering. Hiermee
J
lS
J
J
constructie II voltooid,
- 44 -
Nu moeten we bij boom
l
afleiding
Y boom
laten zien dat de bomen hetzelfde
zijn. We krijgen notatieproblemen: bij beide constructies ontstaan overstreepten en in II ontstaat een nieuwe boom. We lossen dit op door bij II accenten te gebruiken: we noemen de overstreepten uQ,··· en de nieuwe
.
boom
We bewijzen eerst dat de overstreepten bij beide constructies
0 = u0 , enz. Dat k' dan r 0 = O; ••• ;f(r0 )-1,
hetzelfde zijn: u i(r 0 )
= n0
en
A'= A = ~ ~ 0 O' 0
= -A = v 0 ,
vj_ 1 • = vj_ 1 , rj-l
1
=kis triviaal. r dus r
0= r0•
Aj-l
= Aj_ 1 ,
dan is
= O; ••• ;n0-1
Verder u
Nu de inductiestap. Stel 0
= rj_ 1 ,
0
<j
0 = ~ = u0 ,
~ k en ~ J-1
uj;Aj;vj
en
= u j-1'
= uj_ 1 ;rj_ 1 ;vj_ 1
1 = ï:î":';A:';v·.•, J J J
1
maar R.(li.) = i(u.) = R.(\î":'), dus J J J =A ~= v. en r. = A.,O; ... ;A.,n.-1 = A:',o; ... ;A.•,t(r.)-1 = j' J J J J J J J J J
u:--•;;-:----•;~• Jr r
--, u. J
=
= u.'
J
-A.' J
r--' j .
Omdat de overstreepten hetzelfde zijn kunnen we het eerste deel van contructie I uitvoeren en op het resultaat daarvan het tweede deel van constructie II. Triviaal is dan dat B' c Ben dat voort EB' geldt dat f'(t) = f(t). We behoeven dus alleen nog B c B' te bewijzen, Daartoe is voldoende dat iedere tE Bals letter in één der overstreepten voorkomt. Als f(t) E IT is dat bij constructie I aangetoond en als f(t) E IN volgt het uit hulpstelling 7.5. Nu moeten we nog laten zien dat bij linkspref .af'l.
:IJ
boom
.!; afl. de gespeci-
ficeerde afleidingen hetzelfde zijn. Notatieverwarring voorkomen we nu door bij constructie I zowel de overstreepten als de gevonden afleiding I van accenten te voorzien: u • , .•• en uo-, ... 0
, Ook hier tonen we eerst aan
dat de overstreepten hetzelfde zijn. Bij constructie II is aangetoond dat
- 45 -
= A = v 0 ,A 0 '=A=
v0 '
t in r 0
A0 •
=0
Als k
dat f(t) E IT' dus k' =
dan r E IT. Dan geldt voor alle letters
o.
We bewijzen met volledige inductie naar j
datals OIIÖj<;;k. dan j.;; k' en~=~.~=-;;-:, J
= k,
j
dan k
1
= k.
J
J
J
V=
A.·,~=;-:- en als
J
J
J
J
Voor j = 0 klopt dit. Stel nu 0 < j <;; k en de bewering
waar voor j-1. Nu is uj_ 1rj_ 1vj_ 1 = ujAjvj en uj_ 1 ; rj_ 1 ; vj_ 1 = uj; Aj; vj met overeenkomstige lengtes. De gespecificeerde afleiding is linkspreferent verondersteld en dus geldt voor alle letterstin uj' dat f(t) E IT en verder f(Aj) = Aj E IN. Verder is uj_ 1 ; rj_ 1 ; vj_ 1 = volgt nu dat
ll."f J
=
ti." , A:' J
aangetoond dat vB(Aj) =
J
=
A., ;-:t J
J
u.-r-:-J- 1 r 1 1
1
;
; - : ; ; - : '- •
r
1
Daaruit
= ~. Verder is bij constructie II J
=
f(rj)' dus vB(Aj') = f(rj) en dus rj'
A:',o; ... ;A:',f(r.)-1 "A:",o; ... {A:;f(r.)-1:=;-:-.Tevens J J J J J ·J J
is j<;;k'. Als j=k,dan
u.r.v. E r*T , dat wil zeggen dat voor alle letters t in ~;;:t;Y:. =
JJJ
J
~;~;-;;-:geldt f(t) E IT' waaruit volgt dat k' = j
J
J
J
J
J
k.
Nu we aangetoond hebben dat de overstreepten hetzelfde zijn, kunnen we het eerste deel van constructie II uitvoeren en op het resultaat het tweede deel van constructie I. Dit levert dezelfde afleiding op. Allereerst is verder f (u. 1 ) = ,e(;:;-:-ï) = f (~) = f (u. ) en s. (u. 1 ) = f( s. (;:;-:-ï)) = J J J J l J l J = f(s.(~)) = s.(u.) voor i< f(u.) dus u.'= u .• Bijv., r. en A. gaat l J l J J J J J J J het analoog.
k'
= k;
Hiermee is het programma dat wederzijdse omzetting van afleidingabomen en gespecificeerde afleidingen beoogde, voltooid. We gaa."l dit nu gebruiken bij een uitsnijding uit een afleidingsboom. Stel in een afleidingaboom een knoop u en beschouw alle knopen in de boom, die u als. antecedent hebben of u zijn. Als f(u) E IT is dat alleen u en dus niet interessant. We beperken
ons daarom tot het geval dat f(u)
A E IN. De verzameling bestaat dan
- 46-
uit knopen , die als rij getallen u als beginstuk hebben. Knippen we er die u aan de voorkant af, dan krijgen we iets dat op een afleidingstoom lijkt, maar waarvan de wortel A als label heeft. Formeel definiëren we bij een grammaticaGen een hulpsymbool A een A-boom als een afleidingstoom behorende bij ,de grammatica, die uit G ontstaat door het startsymbool door A te vervangen. Gaan we nu_ uit van een afleidingstoom bij G, u EB en f(u) =A E IN dan definiëren weB':= {tElN * \u,tEB} en f'(t):= f(u,t) voort EB'. Het is eenvoudig in te zien, dat een A-boom bij Gis. Verder geldt voor het afgeleide woord x van deze boom, w
dat A ~ x. We zullen laten zien dat het bij behorende afgeleide woord G
de gedaante yxz heeft. Daarbij gebruiken we de volgende eigenschap van lexicografische ordening, Stel u E lN * , t E lN * , s E lN * , dan geldt: als u< s en u geen antecedent
van s, dan u,t
< s.
De verzameling knopen van B, waarbij een eindsymbool hoort, verdelen we op de volgende wijze in drie klassen: 1.
de knopen, die
lexicografisch aan u voorafgaan;
2.
de knopen, die u als antecedent hebben;
3.
de knopen, die lexicografisch op u volgen, maar u niet als antecedent hebben.
Lexicografisch gaan de knopen in 1, vooraf aan die in 2. en die in 2. aan die in 3. Als er respectievelijk de woorden y, x en z bij
horen, dan
is het afgeleide woord yxz en x het afgeleide woord van de A-boom . Veronderstel nu dat we nog een A-boom bij G hebben met afgeleid woord x' en dezelfde A als tevoren, We kunnen nu boomchirurgie bedrijven en de A-boom uitsnijden en vervolgens vervangen door de A-boom
. Dit levert
weer een afleidingstoom
op
met afgeleid woord
- 47 -
yx'z.
Form~el
betekent dit de volgende definitie:
B"' := (B\{u,tjt E lN * }) U {u,tjt EB"} • Let wel dat de twee verzamelingen in het rechterlid disjunct zijn. Dit rechtvaardigt de volgende definitie van f" 1
f"' (s):= f(s)
:
B'" _. I
als sE B\{u,tlt E lN * } ;
f"' (u, t): = f" ( t) als t E B" • Het is gemakkelijk te bewijzen dat
een afleidingaboom is met af-
geleid woord yx'z •
§8. OPERATIES OP TALEN. POMPSTELLING Stelling 8.1.
* M c IT. * Dan geldt: Stel IT verzameling symbolen, L c IT,
als L en M contekstvrij, danLUMen LM contekstvrij , als L contekstvrij, dan L* contekstvrij. Bewijs:
Stel de contekstvrije grammatica's G = zo, dat 0 0 0 0
L = L(G ) en G = zo, dat M = L(G ). 0 1 1 1 1 1 Voor ION= I \IT en I N = I \IT mogen we zonder beperking van de algemeen1 0 1 heid veronderstellen dat ION n I N = ~- Als dat namelijk niet zo is ver1 vangen we de hulpsymbolen bij G door andere met overeenkomstige aanpassing 1 van
z1 en
R
1
en zo, dat de gegenereerde taal niet verandert. We kiezen nu
een nieuw hulpsymbool, dat we Z noemen. We definiëren nu de grammatica G = 3
= door I 3N:= ION U IlN U {Z} , z 3 := Z, R := R U R U {(Z,Z ),(Z,z )}. Dan is a een contekstvrije grammatica; 1 0 1 3
0
3
- 48 -
we tonen aan dat L(G ) = L U M. 3
'G* x, 0 Z 'G z, * 'G3
Stel x € L U M. Als x € L dan zo dan x € M, dus z
1
a,*
x, ·dus
3
G
* G
x • Als x q. L 3 3 x. In beide gevallen geldt x € L( G ). 3 dus
Z
z0
Hieruit volgt LU M c L(G ). 3 Stel omgekeerd x € L(G ). De eerste stap in een afleiding van x is Z • z 0 3 * of Z • z1 • In het eerste geval geldt z G x. Voor een afleiding 0 3 z 0 = X0 , .. .,~=xvanxuit Z0 geldtnudat vooralle j € {O, ... ,k-1} in Xj uitsluitend hulpsymbolen uit r 0 N voorkomen en bij de afleiding Xi een regel uit
R 0
)
0
Xi+l
wordt toegepast. Dit bewijst men eenvoudig met inductie
n I 1N
naar j; hierbij wordt I 0 N dus x € L(G
~
~
gebruikt, Hieruit volgt z
cL U M. In geval de afleiding met
Z ~
z
1
0
* x G
en
0
begint vinden we
op analoge wijze x € L(G 1 ) cL U M. Daarmee is ook L(G ) cL U M aangetoond. 3 Dus L(G ) =LUMen LU Mis contekstvrij, We definiëren nu de grammatica 3 G4 = door I 4N:= ION U I 1N U {Z}, z 4 := Z, R
4:=
R 0
U
R
U {(z,z z
1
0 1
)}.
Dan is G een contekstvrije grammatica; we tonen
4
aan dat L(G ) = LM.
4
Stel x € LM, Dan zijn er y € L, z € M zo, dat x= yz. Dan z en dus Z
* z 0z 1 G *y G
z
* yz G 1
0
*
~
y en
Z
1
* z
~G
Go 1 =x, dus x € L(G ). Hieruit.volgt LM c L(G 4 ). 4
Stel omgekeerd x € L(G ). Omdat(z,z z ) de enige regel bij G is met z in 4 4 4 0 1 het linkerlid.ziet de bovenkant van een afleidingsboom voor x bij G4 er als volgt uit: /1.
0/\,
met 'f(/1.) = Z, f{O) = z , f( 1) = z • De uitsnijding 1 0 van 0 levert een z -boom met afgeleid woord y en de 0 uitsnijding bij 1 levert een z -boom met afgeleid 1
woord z en x = yz. Met inductie naar de lengte van de getalrij bewijst men nu gemakkelijk dat in een z -boom aan iedere knoop een element van I 0 als 0
- 49 -
label
lS
toegevoegd en als bij die knoop
een hulpsymbool hoort, daar een
regel uit R is toegepast, Daaruit volgt dat een z -boom bij G een aflei4 0 0 dingsboom bij G is. Daaruit volgt y E L(G ) = L. Op analoge wijze toont 0
0
men aan dat z E M en dus x = yz E LM. Daarmee is L(G Dus L(G
4 ) = LM en LM
lS
4 ) c LM aangetoond.
contekstvrij. We definiëren nu de grammatica
G = door r N:= ION U {Z}, z := z, 5 5 5 5 5 5 R := R U {(Z,ZZ ),(Z,A)}. Dan is G een contekstvrije grammatica; we tonen 0 0 5 5
* Stel x EL, * Dan is ereennE lN, y , ... ,yn_ , alleE L aan dat L(G ) = L, 0 1 5 zo, dat x = y ... yn_ , dus 0 1
* z0 G
0
y , ••• ,z
0
0
* yn_ • G 1
Als n = o, dan x= A,
0
A, dus x E L(G ). Als n ~ 1, dan 5 * n-1 * * Zz 0 G ... G Zz no ~G zon G5 Yozo G5 .•• G5 Yo···Yn-1 =x, dus x E L(G5).
maar Z
:z>
G5
ZG
5
5
*
5
5
Hieruit volgt L c L(G ). Stel nu omgekeerd x E L(G ). Dan is er een aflei-
5
5
dingsboom bij G met afgeleid woord x. We bewijzen x E L* met volledige in-
5
ductie naar het aantal knopen in de afleidingsboom. Voor de regel die bij de wortel van de boom wordt toegepast zijn er twee mogelijkheden, Als dit
(Z,A) is dan is x = A E L* • Als het echter (z,zz ) is, dan ziet de bovenkant 0 van de boom er als volgt uit: met f(A) = f(O) =Zen f(1) = z • De uitsnijding 0
bij 0 is eenZ-boom met afgeleid woord y, maar een Z-boom is een afleidingsboom. Deze heeft minder knopen dan de gegeven boom; op grond van de inductieveronderstelling is y E L* • De uitsnijding bij 1 is een z -boom met afgeleid woord z. Op 0
analoge wijze als in het vorige geval bewijst men, dat deze zo-boom een afledingsboom bij G is en dus z E L(G ) 0
0
= L.
Dus x= yz E L*L cL * • Daar-
mee is L(G ) cL * aangetoond. Dus L(G ) = L* en L* is contekstvrij.
5
5
I
- 50 -
Vergelijken
we
Stelling 8,1 met Stelling 4,1 dan zien we dat nu L n M en
IT*\L ontbreken, Deze beho.even bij contekstvrije talen L en M ook nie-t contekstvrij te zijn, Neem bijvoorbeeld
L:= {anSnYmln E: JN, m E: JN} M:= {,pSnyn In E: JN, m E: JN} dan zijn deze contekstvrij, want L = {a n anl n E: JN}{y} * en M
*
n n In E lN},
{a} {8 y
Verder L 0 M = {an an y nl n E: JN }. Binnenkort zullen we aantonen dat deze taal niet contekstvrij is. Nemen we dit even als waar aan, dan volgt daaruit ook dat niet van iedere taal het complement contekstvrij is. Zou dit namelijk wel zo zijn, dan levert de verzamelingstheoretische ,, gelijkheid L 0 M
toegepast op bovengenoemde talen L en M op, dat het linkerlid niet en het rechterlid wel contekstvrij is, hetgeen tot een contradictie leidt. Dit levert nog geen expliciet voorbeeld van een contekstvrije taal met een niet-contekstvrij complement. In het rechterlid wordt namelijk drie keer een complement genomen en het is niet duidelijk bij welke camplementering het mis gaat. De volgende stelling bewijzen we niet. Stelling 8.2.
* M c IT. * Als L contekstStel IT verzameling symbolen, L c IT'
vrij en M regulier is, dan is L n M contekstvrij. Uit Stelling 8.2 volgt dat als men aan een contekstvrije taal eindig veel woorden toevoegt of er eindig veel elementen uit weglaat, er weer een contekstvrije taal ontstaat. Toevoegen aan een contekstvrije taal L betekent vorming van LU E met E eindig, maar een eindige taal is regulier en dus contekstvrij,
- 51 -
dus LU E is contekstvrij. Weglaten betekent de vorming van L
n
* met (IT\E)
* ook regulier, en dus L E eindig, maar omdat E regulier is, is IT\E
* n (IT\E)
contekstvrij. We leiden nu een eigenschap van contekstvrije talen af, die ons in staat zal stellen van bepaalde talen aan te tonen, dat ze niet contekstvrij zijn. Stel G = een contekstvrije grammatica en stel n:= #IN' m:= maxlmum van de lengtes van de rechterleden van de regels in R. Voor een afleidingsboom bij G geldt dan, dat alle getallen, die in een knoop van de boom voorkomen
<
m zijn. Verder noemen we bij een afleidingsboom het maximum van
de lengtes van de knopen de hoogte van de afleidingsboom. Hulpstelling 8.3.
Als een afleidingsboom bij G met hoogte h een afgeleid
woord w heeft, dan f(w) Bewijs:
~
h
m •
We behandelen eerst m = 0; dan zijn alle rechterleden van regels
leeg, w =A, f(w) = 0
~
h
0
(ook geldt h = 0). Stel nu verder m ~ 1. Stel
W = de verzameling van alle rijen natuurlijke getallen < m met rijlengte h. Dan #W is
h
m • Definieer nu een afbeelding
(j):
W-+ Bals volgt: als rE W,dan
qJ(r) het langste beginstuk van r of r, dat in B zit. Deze definitie
1s gerechtvaardigd omdat A E B. We tonen nu aan, dat iedere t E B met f(t) E IT in het beeld van qJ voorkomt. De lengte van zo'n
tie~
h; defini-
eer r = t,o, ••• ,o zo, dat f(r) = h, dan geldt rE W (hier wordt m ~ 1 gebruikt) en qJ(r) = t, want t EB en ieder langer beginstuk van r of r, dat in B ligt zout als antecedent hebben, hetgeen niet kan omdat f(t) E IT. h
Dus E c qJ(W) en f(w) = #E ~ #qJ(W) ~ #W = m Stel nu wE L(G), f(w)
> mn.
Dan is er een afleidingsboom bij G met afge-
leid woord w en dus ook zo'n boom met een minimaal aantal knopen; noem
I
- 52 -
deze boom . Laat h de hoogte van die boom zijn, dan volgt uit hulpstelling 8.3, dat n
< h.
Kies nut EB zo, dat f(t)
= h.
De antecedenten
van t geven h knopen van B waarbij een hulpsymbool behoort. Wegens h > n zijn er bij die knopen twee verschillende, waarbij hetzelfde hulpsymbool A behoort. Van deze twee is er één antecedent van de andere. Hierbij horen twee uitsnijdingen, die een Aboom opleveren. Laat de onderste afgeleid woord y hebben, dan heeft het afgeleide woord van de bovenste de gedaante uyv en w = xuyvz. We kunnen nu ook proberen de knopen waar A bijhoort zo laag mogelijk in de boom te kiezen. We nemen dan in de verzameling
antecedenten van t de n+l onmiddel-
lijke voorgangei-s van t en daaruit twee knopen, waarbij eenzelfde hulpsym-
bool A behoort. Dan is de hoogte van de uitsnijding bij zo'n Uit hulpstelling 8.3
volgt dan dat f(uyv)
~
knoop~
n+l.
n+l m •
We gaan nu boomchirurgie bedrijven en snijden de grote A-boom eruit en vervangen d.eze door de kleine A-boom. Dit levert een afleidingsboom met afgeleid woord xyz, dus xyz E L(G). Nu geldt uv dan u
= v = A,
dus w
= xuyvz = xyz.
1
A. Zou namelijk uv = A zijn,
De zojuist geconstrueerde boom zou dan
" als afgeleid woord hebben en minder knopen hebben dan de gegeven boom in strijd met de minimale keuze. We kunnen nu echter ook uit de gegeven boom de kleine
A-boom uitsnijden en deze door de grote A-boom vervangen. Dit
2 2 levert een afleidingaboom met afgeleid woord xuuyvvz = xu yv z E L(G). Dit proces kan herhaald worden. Er geldt: als k E lN , dan is er een afleidingsboom bij G met afgeleid woord xukyvkz en deze bevat een uitsnijding, die een A-boom is, die de in genoemde concatenatie voorkomendey als afgeleid woord heeft. Dit ziet men in met volledige inductie naar k. Het geval dat
- 53 -
k = 0 is al behandeld. Stel de bewering waar voor k. Snijd de A-boom, die y oplevert, uit en vervang deze door de A-boom die uyv levert. Dan ontstaat k+1
een afleidingstoom met afgeleid woord xu
yv
k+1
z. Hiermee is de volgende
stelling bewezen.
St~e~
Stelling 8.4. m
G = een contekstvrije grammatica, n
= #IN'
maximum van de lengtes van de rechterleden van de elementen van R,
wE L(G), f(w)
> mn.
Dan bestaan er x,y,z,u,v,alle E IT* zo, dat
w = xuyvz, uv# A, l(uyv)
< mn+ 1
oneindige verzameling. Hieruit volgt, dat als L(G) eindig is en wE L(G), dan l(w)
< mn.
We kunnen uit Stelling 8.4, die betrekking heeft op een contekstvrije grammatica, direct een stelling maken, die betrekking heeft op een contekstvrije taal en waarin niet expliciet sprake is van:een:grammatica. Deze stelling is in de literatuur als pompstelling (Engels: pumping lemma) bekend.
Stelling 8. 5
(pompstelling). AlsLeen contekstvrije taal is over een
verzameling symbolen IT, dan bestaat er een p E lN zo, dat voor iedere w E L met f(w)
>p
geldt, dat er x,y,z,u,v,alle E IT* bestaan zo, dat
w = xuyvz, uv ~ A, f(uyv)
< p,
i ':l
- 54 -
Bewijs:
Kies een contekstvrije grammatica G met L = L(G) en definieer n
1 · Stell1ng · 8 •• 4 K1es · en m -' ~s 1n nu p:= mn+ en pas Stelling 8 • 4 toe.
I
We gebruiken de pompstelling om aan te tonen, dat de taal (anBnynJn E R} niet contekstvrij is.
Noem deze taal
L en veronderstel dat L contekst-
vrij is. Kies bij L een p E E als in de pompstelling en n Nn8nyn E L en L•(Nn"nyn) ~ ~
"
> p. 2
ip , dan
De pomps t e11·1ng l evert nu x, y, z, u, v u
a,B,y bevat, dan bevat u
>
= uu
twee van de letters
die twee letters in de verkeerde volg-
2 . s t rlJ . "d me t xu2yv z E L. Dus u b evat ten h oogste een •• van de let t ers orde 1n
a,8,y. Voor v geldt op analoge wijze hetzelfde. Er is dus één der letters a,B,y (noem deze ö), die noch in u, noch in v voorkomt. Laat i het aantal malen zijn, dat ö in xyz voorkomt, dan is dat ook het aantal malen dat 6 in 2 2 xuyvz en in xu2yv2 z voorkomt. Daaruit en uit xuyvz E L, xu yv z E L volgt 2 2 dan l(xuyvz) = 3i = l(xu yv z), maar dit is in strijd met i(xuyvz)
< l(xu2yv 2 z). gevoelige
<
DusLis niet contekstvrij. Op te merken is, dat er een contekst-
grammatica bestaat, die L genereert. Daaruit volgt dat L2 i L1 •
Een ander voorbeeld krijgen we als we de taal (wywJw E (a,B} * } beschouwen. Met behulp van de pompstelling kan bewezen worden dat deze taal niet contekstvrij is, hetgeen we hier niet uitvoeren. Men kan ook aantonen dat het complement van deze taal wel contekstvrij is.
§9. BESLISBAARHEID. AMBIGUITEIT In dit college zullen wij de beslisbaarbeid van een taal slechts op intuitieve wijze behandelen. In §1 is al opgemerkt, dat het begrip beslisbaar of recursief in het college Toegepaste logica I formeel wordt behandeld. Wij
* beslisbaar beperken ons tot de vaststelling, dat we een taal L(L c IT)
- 55 -
noemen als er een effectieve procedure bestaat, die voor iedere x E IT*
uitmaakt of x € L dan wel x
~
L. Voor toepassingen is het van belang, dat
een taal beslisbaar is. Van een programmeertaal verlangen we, dat het ver1fieerbaar is of een gegeven tekst syntactisch correct is, dat wil zeggen ln overeenstemming met de grammaticale voorschriften. In de praktijk eisen we echter vaak meer, namelijk dat van een correcte tekst ook de grammaticale
structuur kan worden vastgesteld. Dit laatste correspondeert met een afleidingsboom bij de grammatica. '~
We noemen een grammatica G beslisbaar als er een effectieve procedure be-
staat, die voor iedere x € IT* oplevert: hetzij
x~
L(G), hetzij een afleiding
van x bij G. Ingeval G contekstvrij is kan de afleiding door een afleidingsboom worden vervangen, omdat afleidingen en afleidingsbomen wederzijds op effectieve wijze in elkaar kunnen worden omgezet.
Het doel van de nu volgende beschouwingen is om aan te tonen dat een contekstvrije grammatica beslisbaar is. We gaan daarbij uit van de vaststelling dat een niet-dalende grammatica beslisbaar is; dit betekent datvoor alle regels (u,v) van de grammatica geldt f(u) ~ i(v). Voor een afleiding Z =
x0 ,x 1 , ••• ,Xk
=x geldt dan i(Xj) ~ i(Xj+ ) voor j € {O, ••• ,k-1}. Bij
1
een gegeven grammatica is effectief vast te stellen of een rij elementen van I * wel of niet afleiding van een woord x is. Bovendien kan een afleiding van x vervangen worden door een afleiding zonder herhalingen, omdat
men bij een herhaling eenvoudig een deel van de afleiding weg kan laten. Men kan nu effectief een lijst maken van alle rijen woorden zonder herhalingen en met niet7dalende lengtes, die beginnen met Z en eindigen met het gegeven woord x. Van elk van die rijen kan effectief worden vastgesteld
----~-----
- 56 -
of het wel of niet een afleiding is, Op deze wijze wordt effectief vastgesteld of x een afleiding"bezit en wordt als dat zo is ook afleiding gevonden,
D~armee
eff~ctief
een
is de beslisbaarheid van een niet-dalende gram-
matica aangetoond. Een contekstvrije grammatica hoeft niet niet-dalend te zijn; de storende regels zijn die van de gedaante (A,A), Als zulke regels niet voorkomen, is het lege woord niet afleidbaar, Voor de afleidbaarheid van A is slechts de regel (Z,A) nodig. Om bij aanwezigheid van deze regel bovenstaande beslisbaarheidsredenering te kunnen handhaven, zouden we wensen dat deze regel alleen in de eerste stap van de afleiding kan worden toegepast, Dit kan bereikt wor.den door aan een grammatica G de volgende twee voorwaarden op te leggen: 1.
Het startsymbool Z komt niet voor in de rechterleden van de regels;
2,
alle regels, behalve eventueel (Z,A), zijn niet-dalend.
Een kleine modificatie van bovenstaande redenering leert, dat een grammatica die aan deze voorwaarden voldoet, beslisbaar is, In het bijzonder zijn grammatica's van type 1 beslisbaar: L c R. Bij contekstvrije grammatica's 1 komt voorwaarde 2. neer op: als (A,A) E R, dan A =
z.
Onze methode is nu, dat we een gegeven contekstvrije grammatica G0 (de "oude" grammatica) vervangen door een contekstvrije grammatica Gn (de "nieuwe" grammatica); de bedoeling daarbij is dat de beslisbaarheid vanG n gemakkelijker is vast te stellen
dan die van G • Dit helpt alleen als ook uit de beslis0
baarheid van Gn die van G volgt. Om dit laatste te bewerkstelligen leggen 0 we de volgende drie voorwaarden op aan de constructie van Gn uit G0 :
- 57 -
I.
Als G gegeven is, is de definitie van Gn (hulpsymbolen, startsymbool, 0 regels) effectief uitvoerbaar;
III.iedere afleiding{sboom) bij G kan effectief worden omgezet in een n
afleiding(sboom) bij G met hetzelfde afgeleide woord. 0 Stel namelijk dat I, II, III vervuld zijn en G beslisbaar is. We kunnen n
* De beslisbaarbeid bij gegeven G de Gn maken op grond van I. Stel x E IT. 0 van Gn levert hetzij x~
L(Gn), maar dan geldt wegens II ook x~ L(G ), 0
hetzij een afleiding van x bij G , die op grond van III in een afleiding n
van x bij G kan worden omgezet. 0 We maken nu eerst voorwaarde 1. in orde. Voor de definitie vanG
n
voegen
we aan de hulpsymbolen van G één nieuw hulpsymbool Z' toe, dat tevens start0 symbool van Gn is. De regels van Gn zijn de regels van G met daaraan toe0 g~voegd
(Z',Z). Het is gemakkelijk in te zien dat G een contekstvrije gramn
matica is, die aan voorwaarde 1. voldoet; bovendien is bij de constructie
voldaan aan I, II, III, We gaan nu een nieuwe grammatica definiëren die aan voorwaarde 2. voldoet en wel zo, dat als de oude grammatica aan voorwaarde 1. voldoet, dit ook
geldt voor de nieuwe grammatica. Uiteraard moeten ook I, II en III vervuld zijn.
Een contekstvrije grammatica G = is gegeven. Definieer 0 A}. De grammatica G heeft dezelfde hulpsymbolen en hetn
zelfde startsymbool als G • De verzameling, regels van Gn wordt, uitgaande 0 van R, door de volgende voorschriften bepaald.
- 58 -
Laat alle (A,A) met A iedere (A,q) E R met q
1 Z weg, Als ZE U, voeg (zo nodig) (Z,A) toe, Voor·
1 A doen
we het volgende,
Stel dat op m plaatsen in q een element van U staat. Als q ti U* , dan maak alle 2m woorden r, die uit q ontstaan door in een willekeurige deelverzameling van de m plaatsen, waar elementen van U staan, deze elementen weg
te laten en neem alle 2m regels (A,r) in de verzameling regels van G op. n
Als q E U* dan nemen we op analoge wijze de 2m-1 woorden met uitzondering van het lege woord en daarvoor de regels (A,r).In beide gevallen is de regel (A,q) er zelf
bij en hebben alle zo verkregen regels een niet-leeg
rechterlid, We behandelen een voorbeeld. Stel (A,AaBAC) E R met A E U, BE U, C ti U, a E IT. Nu is m = 3; we krijgen de 8 regels: (A,AaBAC), (A,aBAC), (A,AaAC), (A,AaBC), (A,aAC), (A,aBC), (A,AaC), (A,aC). Een ander voorbeeld is (A,ABA) ER, met A E U, BE U. Weer is m = 3; er komen nu 7 regels: (A,ABA), (A,BA), (A,AA), (A,AB), (A,A), (A,B), (A,A). We merken nog op dat er onder de verkregen regels gelijke kunnen zijn en dat het irrelevant is of het linkerlid van de regel al dan niet een element van U is. Hiermee is de definitie van G gegeven. Het is duidelijk, dat G contekstn n vrij is en aan de voorwaarde 2, voldoet. Eveneens duidelijk is dat als G aan voorwaarde 1, voldoet dit ook voor Gn geldt. Wat voorwaarde I betreft, 0 is het enige probleem om vast te stellen, dat U beslisbaar is: voor iedere A E IN uitmaken of A E U dan wel A
AE ~
U~
ti
U, Hiertoe stellen we het volgende vast:
er bestaat een A-boom bij G met f(t) E IN voor alle knopen t 0
~
er bestaat een A-boom bij G met f(t) E IN voor alle knopen t en een 0
minimaal aantal knopen.
- 59 -
Voor een boom van de laatste soort geldt dat de hoogte .,; n (aantal hulpsymbolen). Het opschrijven van alle A-bomen van hoogte .,; n bij een gegeven grammatica is effectief uitvoerbaar; men kan dan ook effectief vaststellen of daar een boom bij is, waar het lege woord als afgeleid woord bijhoort. Daarmee is vastgesteld of A E U. Voor het vervolg merken we nog op, dat als A E U, er tevens effectief een afleiding van A uit A is gevonden. Daarmee 1s I aangetoond. We behandelen nu II en III tezamen. Stel eerst x E L(G ). Dan is er een n
afleiding van x bij G • Beschouw een afleidingsstap, waarbij een regel is n
toegepast, die geen regel bij G is. Dat kan (Z,A) zijn, maar dan is ZE U 0 en kan de ene stap vervangen worden door een afleiding Z
* A. G
De regel
0
kan echter ook geweest zijn (A,r), waarbij r ontstaan is uit q door een aantal weglatingen van elementen van U en (A,q) E R. In de oude grammatica passen we nu eerst (A,q) toe, gevolgd door een afleiding X
* G
A voor elke
0
weggelaten X; dit resulteert samen in het effect van de toepassing van de regel (A,r). Op deze wijze kan de afleiding omgezet worden in een afleiding van x bij Go; deze omzetting is bovendien effectief uitvoerbaar en levert x E L(G ). We hebben daarmee III al aangetoond. Voor het bewijs van 0 L(G ) c L(Gn) 0
lassen we nog een intermediaire grammatica G. in, die dezelfde
hulpsymbolen en startsymbool heeft als
1
G en Gn. De regels zijn de regels 0
van G met daaraan toegevoegd alle (A,A) met A E U en A # n
z.
Dan zijn ook
alle regels van G regels van Gi. Iedere afleidingsboom bij G is dus ook 0 0 afleidingsboom bij G. en iedere afleidingaboom bij G is ook afleidings1 n boom bij G.• In een afleidingsboom bij G. noemen we een knoopt "verboden", l
l
als f(t) E IN en de afleidingsregel die bij t wordt toegepast niet in Gn zit. Het is effectief vast te stellen of een knoop al dan niet verbaden is.
We beweren nu dat iedere afleidingsboom bij
G. effectief kan l
- 60 -
worden omgezet in een afleidingstoom bij G met hetzelfde afgeleide woord. n
Van deze bewering geven we slechts een schets van een bewijs. We passen volledige inductie toe naar het aantal knopcm van de afleidingsboom. We onder-· scheiden twee gevallen: 1.
De boom heeft geen verboden knopen. Dan is de boom zelf al een afleidingsboom,bij G en zijn we klaar. n
2.
De boom heeft verboden knopen. Kies zo'n knoopt; dit is effectief uitvoerbaar. Stel f(t)
= A,
dan A# Z. Hieruit volgt, dat t niet de wortel van de boom 1s en dus t een onmiddellijke voorganger
u
heeft. Omdat t een verboden
knoop is zijn er geen knopen in de boom, die t
als antecedent. hebben. We proberen nu een
nieuwe boom te maken door de knoop
t
eenvou-
dig weg te laten. Dit hoeft echter geen afleidingstoom op te leveren, omdat er een lacune valt:
de knopen onder u "rechts" van t krijgen een verkeerde
code en eveneens alle knopen die deze knopen als antecedent hebben. Er ontstaat wat we in §6 een quasi-afleidingsboom hebben genoemd; de codering daarvan kan worden gewijzigd zo, dat deze aan de eisen van een afleidingsboom voldoet. We gaan dat niet na. We moeten echter nog controleren of het ook met de toepassing van de regels in orde is. De enige knoop waarvoor dat niet vanzelf spreekt is de knoop u. Bij deze knoop was in de gegeven boom een regel met niet-leeg rechterlid toegepast, die dus een regel van G was; verder A E n
u.
Laten we nu uit het rechterlid van die regel dit
voorkomen van A ook nog weg, dan krijgen we weer een regel van G en dus n
vanG. en die wordt in de nieuwe boom toegepast. Een uitzondering hierop 1 krijgen we als de weglating van die A tot een leeg rechterlid zou leiden.
- 61 -
:I
De situatie
lS
dan zo, dat er vanuit u slechts één tak naar bene-
den gaat en wel die naar t. In dat geval heeft de toegepaste regel de gedaante {B,A) en
lS
ontstaan uit een regel (B,qAs) E R
met q E U* , s E U* • Aangezien ook A E U, geldt dan ook B E U, Maar dan is (B,A) een regel ·ran G., want als B = l
z,
is {B,A) regel van G wegens Z EU, n
en als B # Z, dan is ook (B,A) regel vanG .• Ook in dit geval is het dus l
in orde voor de knoop u. De nieuwe boom levert een afleidingsboom bij G. l
met hetzelfde afgeleide woord en heeft één knoop minder, Volgens de inductieveronderstelling is deze boom effectief om te zetten in een afleidingsboom bij G met hetzelfde afgeleide woord. Dit voltooit het inductiebewijs, n
Neemt men nu een x E L(G ), dan bestaat er een afleidingsboom bij G met 0 0 afgeleid woord x. Deze is ook afleidingsboom bij G. en dus om te zetten l
in een afleidingsboom bij G met afgeleid woord x. Dus x E L(G ). Dit levert n
n
L(G ) c L(Gn) en daarmee is II aangetoond, 0 We hebben nog extra aangetoond dat een afleiding bij G effectief kán wor0 den omgezet in een afleiding bij G met hetzelfde afgeleide woord. Alles n
samen geeft dit de volgende stelling:
Stelling 9. 1.
Een contekstvrije grammatica is beslisbaar.
In de notatie van §3 is dit te schrijven als L c R. We hebben trouwens ook 2 bewezen dat L c L • 2 1 We noemen nog een aantal onbeslisbaarheidsresultaten, veelal zonder bewijs.
Het is onbeslisbaar of de talen gegenereerd door twee contekstvrije gramrnatica's
aan elkaar gelijk zijn, Dit moet als volgt worden opgevat. Men
kan zonder moeite paren grammatica's maken, waarvan men vast kan stellen
dat ze niet dezelfde talen genereren, Wat echter onmogelijk is, is het maken
- 62 -
van een effectieve procedure, waar men twee willekeurige contekstvrije grammatica's kan instoppen en die als antwoord levert of de bijbehorende talen al dan niet gelijk zijn. Eveneens onbeslisbaar is of de taal van een contekstvrije grammatica deelverzameling is van de taal van een andere contekstvrije grammatica. Wel . beslisbaar is of de taal van een contekstvrije grammatica leeg is en ook of deze eindig is. We geven een schets van het bewijs van deze beweringen. Uiteraard geldt: L(G)
#
~ ~
er bestaat een afleidingsboom bij G ~er bestaat een af-
leidingsboom bij G met een minimaal aantal knopen. Voor zo 1 n boom geldt echter weer, dat de hoogte Of zulk een afleidingsboom
~aantal
hulpsymbolen.
bestaat kan effectief worden vastgesteld. Voor
de eindigheid bedenken we, dat we bij het bewijs van Stelling 8.4 bij een contekstvrije grammatica G effectief een getal p hebben gevonden zo, dat als er een w E L(G) bestaat met !(w)
> p,
dan L(G) oneindig. We kunnen nu
ook bij een gegeven contekstvrije grammatica G en een getal p effectief
* een contekstvrije grammatica maken die de taal L(G) n {x E ITI!(x)
> p}
genereert. De beslisbaarbeid dat L(G) eindig is volgt dan uit L(G) eindig~ L(G)
n {x
* !(x) E ITI
> p}
= ~
Het is onbeslisbaar of een contekstvrije grammatica een reguliere taal genereert. Het is ook onbeslisbaar of het complement van een door een contekstvrije grammatica gegenereerde taal leeg is, of eindig is, of contekstvrij is. Onbeslisbaar is ook of de doorsnede van de door twee contekstvrije grammatica 1 s gegenereerde talen leeg is, of contekstvrij is.
- 63 Voor 3-type talen is veel meer beslisbaar. Een 3-type grammatica als generator en een eindige automaat als acceptor van een zelfde taal zijn effectief in elkaar om te zetten. Verder kan men voor door eindige automaten geaccepteerde talen ook effectief automaten maken voor vereniging, doorsnede en complement van talen, Dit zelfde geldt dus ook voor 3-type grammatica's,
Bedenk verder, dat L
= M~
* * (L 0 (IT\M)) U (M 0 (IT\L)) = ~.
Als 3-type grammatica's voor L en M gegeven zijn, dan is effectief een 3-type grammatica voor (L
n
* (IT\M)) U (M
n
* (IT\L)) te maken en is het dus
beslisbaar of deze taal leeg is. Het is dus ook beslisbaar of L
= M.
* gevalLcMbehandelt men op analoge wijze met behulp van L n (IT\M)
Het
=~.
Definitie ambigue grammatica Een contekstvrije grammatica G heet ambigu als er twee verschillende afleidingsbomen
bij G bestaan met hetzelfde afgeleide woord,
Neem als voorbeeld R
IN= {Z,A}, IT = {a,S} ,
= {(Z,aZS),(Z,aA),(Z,aS),(A,aZBS)}
• De volgende twee bomen
zijn afleidingsbomen bij deze grammatica, die hetzelfde afgeleide woord aaa666 hebben. De grammatica is dus ambigu, Het is gemakkelijk na te gaan, . dat de door deze grammatlca gegenereerde taal { a n+1 Sn+1l n E
m}
. ls. Deze
taal wordt echter ook gegenereerd door de volgende contekstvrije grammatica: IN= {Z}, IT
= {a,S},
R
= {(Z,aZS),(Z,aS)},
waarvan eenvoudig in te zien is
- 64 -
dat zij niet ambigu is. In de meeste toepassingen zijn ambigue grammatica's ongewenst. Men wil dus een contekstvrije taal graag genereren met een niet-ambigue contekstvrije grammatica. Dit kan echter niet altijd. Definitie inherent ambigue contekstvrije taal Een contekstvrije taal heet inherent ambigu als iedere contekstvrije grammatica die deze taal genereert ambigu is, De taal {an6nYml n E lN ,m E lN} U {<>mSnYnin E lN ,m E JN} is inherent ambigu. Dit bewijzen we niet. Het is van praktisch belang om van een contekstvrije grammatica vast te stellen of zij ambigu is en van een contekstvrije taal of hij inherent ambigu is. Een algemene methode daarvoor bestaat echter niet op grond
van het volgende, Het is onbeslistaar of een contekstvrije grammatica ambigu
lS
en ook of
een contekstvrije taal inherent ambigu is.
§10,
STAPELAUTOMATEN We bespreken nu een uitbreiding van de eindige automaat, die geschikt is om contekstvrije talen te accepteren. Om een echte uitbreiding te krijgen zal zo'n automaat een geheugen moeten hebben, waarin een onbegrensde hoeveelheid informatie kan worden opgeslagen, Dit betekent, dat deze hoeveelheid op ieder
moment eindig is, maar dat er voor deze hoeveelheid geen
bovengrens is. Dit wordt gerealiseerd met een stapel. Deze wordt fysisch beschreven met een verticaal geplaatste band, die in
hokjes verdeeld is.
- 65 -
In elk hokje staat een symbool geschreven. De stapel is alleen aan de bovenzijde toegankelijk. Daar kan een symbool worden gelezen en kan worden uitgeveegd of bijgevoegd; daarbij kan de hoogte van de stapel veranderen. Formeel doen we dit door het bovenste symbool
~
te lezen en te verwijderen en te ver-
vangen door een woord w. Als w veegd; als w ---L--~__
= ~~
= A,
dan is het symbool uitge-
dan is er niets veranderd; als w =
is er iets toegevoegd; als w =ny met n
1
~.
dan is
~
~y
dan
doorn
vervangen en y toegevoegd. Voor het overige verkeert de automaat in een toestand, leest een invoersymbool en het bovenste symbool van de stapel en gaat vervolgens over in een nieuwe toestand en schrijft op de stapel. We laten nu echter ook nog toe, dat de automaat een handeling verricht zonder een invoersymbool te lezen; hij verandert dan op grond van de
geldende toestand en het bovenste stapelsymbool zijn toestand en schrijft op de stapel. Hiermee hebben we een niet-deterministisch gedrag geintroduceerd: de automaat heeft keuze tussen het doen van een stap met lezen of zonder lezen van de invoer. We breiden dit nu uit door in elke situatie zowel bij lezen als bij niet-lezen meer dan één keuze toe te staan, waarbij we echter wel in elke situatie het aantal mogelijke keuzen eindig willen houden. Deze eindigheid is niet automatisch vervuld, omdat er voor
het op de stapel te schrijven woord w oneindig veel mogelijkheden zijn. Formeel wordt dit beschreven door als waarde van een afbeeldingsfunctie
een eindige deelverzameling van de verzameling.der mogelijke uitkomsten te nemen. We gebruiken daarbij de notatie, dat als V een verzameling is, P (V) de verzameling is van alle eindige deelverzamelingen van V. Dat een w actie van de automaat twee uitkomsten geeft, namelijk een toestand en een
- 66 -
woord op de stapel vangen we op met een Cartesisch produkt. Een stap waarbij niet gelezen wordt, wordt formeel beschreven met het lezen van A. Voor de symbolen op de stapel kiezen we een aparte verzameling symbolen, die overigens niet hoeft te verschillen van de verzameling invoersymbolen. Omdat de automaat zijn werking verricht
mede op grond van het bovenste
symbool op de stapel, zal er ook bij het begin van de werking iets op de stapel moeten staan; daartoe kiezen we een beginsymbool voor de stapel. Verder kan de hierboven genoemde eindige verzameling uitkomsten ook leeg zijn; als dat zo is, is de werking van de automaat geblokkeerd. Blokkade zal ook optreden als tijdens de werking van de automaat de stapel leeg raakt. De inhoud van de stapel zullen we formeel beschrijven met een symboolrij, die echter horizontaal is en de stapel verticaal. Voor deze overgang moeten we een afspraak maken; we stellen vast dat de bovenkant van de stapel overeenkomt met de linkerkant van de symboolrij. Een automaat, die met bovenstaande beschrijving correspondeert, wordt een
stapelautomaat genoemd. De Engelse benaming is pushdown automaten.
Deze naam correspondeert met het beeld, dat de stapel niet aan de onderzijde, maar aan de bovenzijde wordt vastgehouden. Bij toevoeging van symbolen moet de stapel naar beneden worden gedrukt, bij verwijdering van symbolen moet de stapel uit zichzelf omhoog komen. Definitie stapelautomaat Een 7-tupel A= <s,r,r,6,s
0
,z 0 ,F>
is een stapelautomaat, als geldt:
Sis een eindige verzameling (elementen vanS heten toestanden), I is een eindige niet-lege verzameling (elementen van I heten invoersymbolen),
- 67 -
r is een eindige verzameling (elementen van
r heten stapelsymbolen),
6 1s een afbeelding S x (I U {A}) x r .... P ( S x r * ) , w
s
0
z0
ES (begintoestand), Er (beginsymbool),
F c S (elementen van F heten toegelaten toestanden). De interpretatie van 6 is, dat als (s',w) E
6(s,~,n) en~
E I,de automaat,
als hij in toestand s verkeert en n op de top van de stapel heeft staan, bij lezing van het invoersymbool
~
in één stap over kan gaan in toestand
s' onder gelijktijdige vervanging van n bovenaan de stapel door w. Een analoge interpretatie,maar dan zonder lezing van een invoersymbool, geven
we als in het bovenstaande
~
door A wordt vervangen.
Om nu de verwerking van een invoerwoord door de automaat te beschrijven voeren we in een bij de automaat behorende momentane.beschrijvillg, dat is
een tripel (s,p,q) waarin s E
s,
p E I * , q E r * • De interpretatie hiervan
is, dat s de geldende toestand is, p het nog niet gelezen deel van het invoerwoord, q de geldende inhoud van de stapel. We definiëren nu een binaire relatie
~
tussen momentane beschrijvingen. We willen dat zo
doen, dat m ·~ m' geïnterpreteerd kan worden als: m kan in één bereke-
ningsstap bij A overgaan in m'. We definiëren dat (s,~p,Tq)
~
(s' ,p,q'q)
geldt
voors ES,~ EI U {A},p E I*, TE r,q Er * , als (s',q') E ó(s,~,T). We definiëren m
* Tm'
* lp;-
als de reflexief-transitieve afsluiting
van~
:
geldt per definitie als er een n E lN en een rij m0 , ••• ,mn van
momentane beschrijvingen bestaan zo, dat m0 voor jE {O, ••• ,n-1}.
= m,
mn
= m'
en mj
T
mj+ 1
- 68 -
We willen de automaat als acceptor gebruiken. Dit kan echter op verschillende manieren; we beschrijven de twee meest gebruikelijke keuzen. De eerste is om
evenals bij de eindige automaat gebruik te maken van de verzameling
F van toegelaten toestanden. Op grond van het non-determinisme beschrijven we het zo, dat we een woord w accepteren, als er een rij overgangen bestaat,
die begint in de begintoestand en met
z0
op de stapel, waarbij het hele
woord w gelezen wordt en geëindigd in een toestand in. F. In plaats van aldus op grond van toegelaten toestanden te accepteren, doet men dit ook wel op grond van een lege stapel: met een soortgelijke start als zoëven moet het mogelijk zijn om na lezing van het gehele woord te eindigen met een lege stapel. Formeel leidt dit tot de volgende twee definities voor een stapelautomaat A:
Bij L (A) speelt de verzameling F in het geheel geen rol. Als afkorting 2 van een stapelautomaat wordt soms ndpa gebruikt (non-deterministic pushdown autornaton). Het verband tussen L (A) en L (A) komt tot uitdrukking 1
2
1n
de volgende stel-
ling: Stelling 10. 1 • L (A 1 2
)
Bewijs:
= L1 (A)
Bij iedere ndpa A bestaan er ndpa 1 s A1 en A" zo, dat en L (A") 1
= L2 (A).
We geven alleen de definities van A1 en A" en laten het bewijs dat
- 69 -
<s,I ,r ,ö ,s ,z ,F>. Kies een n1euwe toestand si en definieer 0 0
Stel A S' :::::
s u
r'
r u {Z ,Z 1 } . Verder 0
:=
nieuwe stapelsymbolen Zl en Zl en definieer 0
{SI } ; kies twee
SI
•= s Z' ·0' 0.-
De afbeelding 0 I
Fl = 1/J
z~
o·
0 '
wordt als volgt gedefinieerd. Stel f; E I U {A}, s E
6 1 (t,r;,z }:=
0
l' ( :c''} 'c
so en f;
als t
l
als s f/_ F of f;
r(s 'i;,'r) ö(s,f;,T)
u ((si,!()}
1
ó'(s' ,t:,'J:I):=
rs ~A)}
als
f;
als
f;
rs ~A)} 1
Ö
1
(t,f;,Z
1
)
:=
tES 1 ,TEf:
A,
1 s 0 of f; 1 A,
als t
6 1 (s,f;,'r):=
s,
A,
als s E F en f;
A
1
1
'
A,
als t E F U (SI } en f;
!/. F U
als t
A,
{SI} of f;
A,
1
A.
Daarmee is de definitie van A' voltooid. Kies nu een n1euwe toestand s"
en definieer S":= SU {s"}; kies twee nieuwe stapelsymbolen Z"
0
en Z" en
r" := r U {Z" . . .. , Z"} • Ver d er s " := s , Z" :;;; z• •, F"·.= {s"}. De afbeeld e f 1n1eer 0 0 0 0 0 ding ö" wordt als volgt gedefinieerd. Stel f; E I U {A}, s E S", T E r:
ö"(s,f;,Z~) :=
r
so ·:oz")}
als s = so en f;
1
als s
ö"(s,f;,T):=
rs,:,T)
als s
so of f;
11,
1 A,
1 s",
als s = s " ,
((s",Z")}
ó"(::;,r;,,z")::;;-
Daarmee
lS
{
1/J
s
A,
als s = s" of f;
11.
ab s
1
de definitie van A" voltooid.
s" en
I
- 70 -
De nu volgende stelling geeft het verband met contekstvrije ralen.
Stelling 10.2 ( Chomsky). Een taal L is contekstvrij dan en slechts dan als er een ndpa A bestaat zo, dat L = L (A). 2
Bewi.i s:
Stel L contekstvrij. Kies een contekstvrije grammatica G
= zo, dat L = L(G). We definiëren een ndpa A als volgt.
z0 :=
S: = { 0} , I:= IT, r: = IN U IT, s o··= 0, wordt als volgt gedefinieerd. Stel
ó(O,~,n):=
6(0,~,A)
{(O~A)} {
~
~.
Z, F:=
De afbeelding
6
E IT U {A}, n E IT, A E IN:
als
n,
~
VJ
als E,
cF
n,
·- { {(O,r)J (A,r) E R} als
i;
A,
~
f A.
.-
~
als
Daarmee is de definitie van A voltooid. Het bewijs dat L (A) 2
L(G) laten
we aan de lezer over.
Omgekeerd gaan we nu uit van een ndpa A = <s,I,r ,6 ,s
0
,z 0 ,F>. We defini-
eren een contekstvrije grammatica als volgt: IN:= S x S x
r, IT:= I,
Z:= (s ,s ,z ), 0 0 0 R:= !((s,t m,T),qt ,t ,•r ) •.• (t m- ,t m,Tm- 1 lll 1 0 1 0 mE JN,t
0
E
s, ... ,tm E S,s E S,T 0 E r, ... ,Tm_ 1 E r,T E
f,E, EI U {A},
(t ,T ••• Tm_ ) E 6(s,~,T)} 1 0 0 Let wel, dat dit voor m = 0 een regel
((s,t
0 ,T),~)
oplevert onder de voor-
waarde (t ,A) E 6(s,i;,T). Daarmee is de definitie van G voltooid. Het be0 wijs dat L(G) = L (A) laten we aan de lezer over. 2
I
- 11 -
Op grond van Stelling 10.1 is er ook een met Stelling 10.2 corresponderende stelling, waarin 1
2
door 1
1
is vervangen.
Bij het nabootsen van een automaat door een fysische machine is het indeterminisme een hinderlijke omstandigheid. We vragen ons af of wij ons tot deterministische
automaten hadden kunnen beperken. We moeten die dan eerst
definiëren. De bedoeling is, dat de automaat in iedere situatie niet meer dan één keuze heeft; daarbij inbegrepen de keuze tussen wel en niet lezen. We laten echter wel blokkades toe, dat wil zeggen situaties waarin er in het geheel geen keuze is. Definitie deterministische stapelautomaat Een ndpa <s,r,r,ó,s ,z ,F> heet een deterministische stapelautomaat als 0 0 geldt:
VsES VsEI VTEf[#(ö(s,s,T))
+
#(6(s,A,T)) ( 1] .
Dit betekent dat deze aantallen 0,0 of 1,0 of 0,1 zijn. We gebruiken de afkorting dpa voor een deterministische stapelautomaat. Voor deze automaten maakt het wel verschil of er op grond van toegelaten toestanden, dan wel op grond van lege stapel wordt geaccepteerd. Enerzijds is het wel zo, dat er bij iedere dpa A een dpa A" bestaat zo, dat L (A") 1
= L2 (A),
maar
anderzijds bestaat er een dpa A zo, dat voor alle dpa's A' geldt L (A') 2
#
# L 1 (A). Acceptatie op toegelaten toestanden levert het meest aanvaardbare resultaat. Definitie deterministische taal Een taal L heet deterministisch als er een dpa A bestaat zo, dat L
1 (A). 1
- 72 -
Uiteraard is een deterministische taal contekstvrij. Dat niet iedere contekstvrije taal deterministisch is volgt uit de volgende twee eigenschappen van deterministische talen, die we niet zullen bewijzen.
Stelling
10.3.
Het complement van een deterministische taal
lS
determi-
nistisch. Stelling 10.4.
Als L een deterministische taal is dan bestaat er een niet-
ambigue contekstvrije grammatica G zo, dat L = L(G). Een contekstvrije taal, waarvan het complement niet contekstvrij is, is op grond van Stelling
10.3 niet deterministisch
inherent ambigue contekstvrije taal terministisch en zulke talen
1s
en zulke talen bestaan. Een
op grond van Stelling 10.4 niet de-
be:~taan.
Het omgekeerde van Stelling 10.4 is onjuist. De taal van de palindromen vari
even lengte (zie §1) kan worden gegenereerd met een niet-ambigue contekstvrije grammatica, maar is niet deterministisch. Dit tonen
Opgave.
~e
niet aan.
Construeer een ndpa die de taal der palindromen van even lengte
accepteert. We beschouwen nu de
~:;tappen
van een au"Lotnaat, waarbij geen invoersymbool
wordt gelezen (A-stappen) en vragen ons af of deze gemist kunnen worden. Dit zou een vereenvoudiging betekenen, omdat dan bij verwerking van een invoerwoord het aantal stappen gelijk
1s
aan de lengte van dat woord. For-
meel definiëren we een stapelautomaat zonder A-stappen als een stapelautomaat <s.r,r ,o,s
0
,z 0 ,F>,
waarvoor geldt:, Y"ES
v1,Er
[ó(s,A,T) = 1<1] •
- 73 -
Het is duidelijk, dat voor een stapelautomaat A zonder A-stappen geldt A ~ L2 (A) • Dit blijkt de enige beperking te zijn.
Stelling 10.5.
Als A een ndpa is, dan bestaat er een ndpa A' zonder A-
stappen zo, dat L (A') = L (A). Als bovendien geldt A~ L (A), dan be2 1 1 staat er een ndpa A" zonder Deze stelling bewijzen
A-stappen zo, dat L (A") 2
= L2 (A).
we niet. Er blijkt uit, dat we ons voor het accep-
teren van contekstvrije talen tot stapelautomaten
zonder
hadden kunnen beperken. Dat neemt niet weg, dat het voor een
A-stappen gegeven
contekstvrije taal soms gemakkelijker is om een stapelautomaat met A-stappen te construeren, die de taal accepteert, dan een zonder A-stappen. Bovendien levert de combinatie van determinisme en het weglaten van A-stap-
pen wel een essentiële beperking op. Er bestaan namelijk deterministische talen, die niet door een dpa zonder A-stappen kunnen worden geaccepteerd. Voor zulke talen bestaat er dan wel een dpa met A-stappen of een ndpa zonder A-stappen. Voor de
definitie van deterministische talen blijkt het
daarom gewenst om stapelautomaten met A-stappen mee in de beschouwing te betrekken.
- 74 -
HOOFDSTUK 3. SEMANTIEK § 11 • INLEIDING Het opstellen van een formalisme geschiedt meestal met een zekere bedoeling. Zeer algemeen geformuleerd houdt semantiek zich bezig met het verband tussen formele systemen en datgene wat ermee bedoeld is (de "betekenis"). Als men bijvoorbeeld een contekstvrije grammatica opstelt ten behoeve van natuurlijke talen of programmeertalen, dan kiest men bij voorkeur hulpsymbolen, die iets betekenen en waarvoor men ook namen kiest, waaruit die be-
tekenis blijkt (voorbeelden: (noun phrase), (verb phrase) bij natuurlijke talen; , , <procedure> bij programmeertalen). Het opstellen van een afleidingaboom voor een tot de taal behorende "tekst" zal dan een
bijdrage leveren tot het vinden van de "betekenis" van die
tekst. Op de weg naar de betekenis is dat echter pas een eerste stap, die trouwens gewoonlijk nog niet tot de semantiek gerekend wordt. Toch houdt bij voorbeeld ambiguïteit al in dat er meer dan één interpretatie van de
tekst mogelijk is. Wil men verder gaan, dan zal men zijn doelstellingen nader moeten preciseren.
Het voorbeeld van een programmeertaal is illustratief. Een programmeertekst zal vaak geschreven worden met het oogmerk deze vervolgens door een rekenautomaat te laten lezen en uitvoeren. Men zou dan onder semantiek kunnen verstaan de betrekking tussen de gedaante van de tekst en de serie handelingen, die in de automaat worden verricht, of eventueel alleen de betrekking tussen eindtoestand en begintoestand van de automaat. Het feit dat een zelfde tekst door automaten van verschillend type en merk kan worden uitgevoerd, zouden we kunnen ondervangen door de introductie van een
- 75 -
"abstracte 11 automaat, waarvan verondersteld wordt dat zijn gedrag representatief
is voor het gedrag van de "fysische" automaten. Een schrijver
van een programmatekst zal echter in het algemeen verderstrekkende oogmerken hebben dan alleen het bezighouden van
een rekenautomaat. Hoewel deze oog-
merken zeer divers kunnen zijn, beschrijven we ze hier als "het oplossen
van een probleem". Het oplossen van de vraag of men die doelstelling heeft verwezenlijkt is pas de ware semantiek; de beperking tot het "computergedrag" wordt soms wel pragmatiek of operationele semantiek genoemd. Het ontwerpen van mathematische modellen voor de semantiek in wijdere zin noemt men mathematische semantiek.
Dat een programma, dat pretendeert de grootste gemene deler van twee positieve natuurlijke getallen uit te rekenen, dat ook werkelijk doet, is alleen vast te stellen, als men weet wat de grootste gemene deler van twee
positieve natuurlijke getallen is. Als men zich hier van af maakt door te stellèn
dat de grootste gemene deler gedefinieerd is door hetgeen het
programma oplevert, gebruikt men de term "grootste gemene deler" in een
andere betekenis, dan gebruikelijk is; dit geldt ook als het programma correct ls.
"
Het 1s niet de bedoeling om hier een systematische behandeling te geven van de semantiek van programmeertalen. We volstaan met het belichten van
enkele mathematische achtergronden. Een uitvoering van een programma leidt tot vergroting van informatie. Als het programma bijvoorbeeld de waarde van een funtie f levert de invoer van een argumentwaarde
a
uitrekent, dan
als.uitvoer f(a). Dit ver-
groten van de informatie komt in het bijzonder tot uiting als de functie
'1
•'' :,~
- 76 -
herhaaldelijk wordt uitgerekend zoals dat het geval is bij de uitvoering van een recursieve procedure. Veronderstel dat gevraagd is om nl uit te rekenen en dat vermenigvuldiging tot de normale rekenfaciliteiten behoort, dan kan het doel bereikt worden met een recursieve procedure fac waarbij fac(n) gedefinieerd is door de programmatekst: if n ; 0 then
else n
* fac(n-1)
•
Ter verklaring vatten we de tekst van de procedure eerst op als een operator P, die werkt op een variabele functie fen waarbij (Pf)(n) gedefinieerd wordt door if n ; 0 then
else n
* f(n-1)
We veronderstellen dat de variabele n de verzameling
~
der gehele getallen
doorloopt. Voor iedere functie f is Pf ook een functie, dus P is een operator die functies 1n functies omzet. Kiest men bijvoorbeeld voor f de n(n-1) als n # 0. Nu 1s
identieke functie dan is (Pf)(O); 1 en (Pf)(n)
fac blijkbaar een functie, die voldoet aan Pfac ; fac, maar fac(n) is alleen gedefinieerd voor n
~
0, en de gebruikelijke wijze van uitvoering
van bovenstaande programmatekst voor fac met een negatief getal als invoer leidt tot een niet-stoppende berekening. Dat neemt niet weg, dat Pf ; f wel degelijk oplossingen heeft, die voor allenE Zo voldoet voor iedere constante c de functie g n!
c
~
gedefinieerd zijn.
gedefinieerd door
als n ~ 0 ,
g (n):;
c
(-1 )n+1c
(-n- 1 )! als n < 0 ,
aan Pg
c
; g • Bij de gebruikelijke uitvoering van de recursieve procedure c
- 77 -
is het zo, dat naarmate het aantal malen dat de procedure mag worden aangeroepen groter is, het aantal waarden van n waarvoor fac(n) wordt verkregen, ook groter is, We kunnen dit beschrijven met behulp van partiële functies, dat zijn functies f die· op een deelverzameling van 2Z gedefinieerd zijn. De groei van die deelverzameling weerspiegelt de groei van onze kennis omtrent de te berekenen functie. Als we aannemen, dat we met totale onwetendheid beginnen, dan stellen we
dat f
0
de nergens gedefinieerde functie is. Met behulp van de operator P
maken we dan de rij functies f ,f , ••• , 0 1 door fn+l f (x) n
die inductief gedefinieerd wordt
.= Pfn. Bij fac is het duidelijk dat de uitkomst wordt, dat
= x!
voor 0 ~ x
Bij uitvoering is f
n
de
en f (x) ongedefinieerd voor alle andere x E ZZ. n
functie die verkregen wordt als men de procedure
ten hoogsten maal aanroept. Elke volgende functie is een voortzetting van de vorige. De door de recursieve procedure bepaalde functie f is de omvattende functie f(x)
= x!
als x
~
0, f(x) ongedefinieerd als x
< 0,
We stre-
ven nu een iets algemenere formulering na.
§12.
PARTIËLE FUNCTIES Stel A en B verzamelingen en T de verzameling van alle partiële functies van A naar B, dat wil zeggen bij iedere f € T behoort een domeinD f c A en voor alle x E Df
geldt f(x) E B. Op T definiëren we een relatie
~
door voor
f E T en g E T te stellen
In woorden zegt men~ "g is voortzetting van f 11 of
11
g geeft meer informatie
dan f". De relatie~ is wiskundig eenvoudig, als we de verzamelingstheoretische opvatting kiezen, waarbij functies verzamelingen van paren zijn:
•
.i
- 78 -
f
= {{x,f(x))ix
Daaruit
E Df}, Bij die opvatting is f ~ g hetzelfde als f cg.
volgt direct dat
~
aan de eisen van een partiële ordening vol-
doet: f ~ f
als
f
~
als
f
~gen
g en g g
~
h, dan f
~
~
f, dan f = g •
We beschouwen nu de operatoren P: T
h,
-+
T, We zullen aan de operatoren enkele
voorwaarden opleggen, die geïnspireerd zijn door de uitvoering van programmateksten. We eisen eerst, dat als g meer informatie bevat dan f, ook Pg-meer informatie bevat dan Pf. Dit leidt tot de volgende voorwaarde: 1.
Als f
~
g, dan Pf
~
Pg
(monotonie).
De tweede voorwaarde komt voort uit de gedachte, dat als de berekening van (Pf)(x) een uitkomst oplevert, er bij de uitvoering hiervan de berekening van f(y) voor slechts eindig veel waarden van y wordt gevergd, Welke waarden van y dat zijn mag daarbij behalve van f ook van de waarde van x afhangen. Vervangen we nu echter de f door een g, die in alle y, waarvoor de f(y) bij de berekening van (Pf)(x) gebruikt worden, dezelfde waarde heeft als f, dan verloopt de berekening geheel op dezelfde wijze en is (Pg)(x)
= (Pf)(x).
Dit leidt tot de volgende voorwaarde: 2.
Als f E T en x E DPf' dan bestaat er een eindige deelverzameling Y van Df zo, dat voor alle gE T, waarvoor geldt Y c Dg en VY'EY[g{y) = f(y)], ook geldt x E DPg en (Pg)(x)
=
(Pf)(x) •
- 79 -
We kunnen een andere formulering van 2. krijgen door in plaats van de
verzameling Y de restrictie
van f tot Y te gebruiken. We noemen een h E T
eindig als Dh eindig is (de verzameling h is dan ook eindig), We definiëren T0 als de verzameling van de eindige elementen van T.
2'.
Als f ET en x E DPf' dan bestaat er een hE T
0
zo, dat h ~fen voor
= (Pf )(x).
alle g E T, waarvoor geldt h ~ g, ook geldt x E DPg en ( Pg) (x)
Het is duidelijk dat 2, en 2'. equivalent zijn. Als we aannemen datPook monotoon is, kan 2. in een eenvoudiger gedaante gebracht worden. 2". Als f E T en x E DPf' dan bestaat er een hE T zo, dat h ~ fen x E DPh' 0
Het is duidelijk dat 2' . . . 2".
Dat uit 1, en 2", volgt dat 2'. geldt ziet
men als volgt. Stel f E T en x E DPf dan geeft 2". dat er een h E T
0
met h Ph~
~fen
x E DPh' Als nu voor gE T geldt h
~
g, dan volgt uit 1, dat
= (Ph)(x) = (Pf)(x),
Pg, dus x E DPg en (Pg)(x)
is
waarmee 2'. is aan-
getoond. We veronderstellen nu dat de operator P: T definiëren een rij ~
r 0 ,r 1 , .••
1. en 2. voldoet. We
~Taan
van elementen van T met volledige inductie:
(nergens gedefinieerde functie) en f
n+ 1
= Pf
n
(we schrijven dan ook
n
P f ) • Er geldt nu VnElN [ f ~ f ] · de rij is monotoon niet-dalend. n n+1 ' 0 Dit bewijzen we met volledige fn ~ fn+ 1 , dan fn+ 1
= Pfn
inductie, f
~ Pfn+
1
= fn+ 2
0
=
~ ~
f
1
(triviaal). Stel
op grond van 1. Met de verzame-
lingstheoretische opvatting van functies definiëren we nu f:= U {f In E lN}, n
We bewijzen dat dit een partiële functie is. Het is uiteraard een verzameling paren. Stel nu (x,y) E fen (x,z) E f. Dan is ereennE lN zo, dat (x,y) E f
n
en een m E lN zo, dat (x,z) E f • We mogen aannemen dat n ~ m. m
- 80 -
Dan geldt f n ~ f m en dus (x,y) E f m en (x,z) € f m• Omdat f m E T, geldt dan y
= z.
= f.
Dus f E T. De volgende bewering is dat Pf
stellen we n E JN , dan f
n
~
f, dus :f
n+ 1
=P:fn ~ Pf,
Om dit te bewijzen
maar ook r 0
~ Pf
en dus f
~
P:f.
Stel nu x E DPf en stel ?-at h de op grond van.2 1 • daarbij behorendepartiële functie ïs,dus hE T0 , h ~fen x € DPh' Stel nu y E Db, dan y E Df, .du" er 1s een n E lN zo, dat y E Df
en fn (y)
= h(y);
voor alle m ;;. n geldt
n
dan ook fm(y) = h(y). Omdat Db eindig is, zijn er maar eindig veel van zulke y; door van de bijbehorende n de grootste te nemen vinden we dat er een n E lN bestaat zo, dat h x E Dpf
f • Op grond van 2 1 • geldt dan n
c Df. Daarmee is bewezen dat DPf c Df. Tezamen met f ~ Pf
Df
n
~
n+1
volgt daaruit Pf
= f.
Stel nu een gE T waarvoor geldt Pg = g. Dan geldt ook YnElN [fn
.~
g]. Dit
bewijzen we met volledige inductie. r
~
g, dan
f n+1
= Pfn
~
Pg
0
~
g is triviaal. Stel fn
g. Daaruit volgt dan weer f
~
g.
We noemen een g E T, waarvoor geldt Pg = g een dekpunt (Engels: fixed point) van P. De hierboven gevonden f is een dekpunt van P, maar bovendien geldt voor ieder dekpunt g van P, dat f
~
g. Daarom heet f kleinste dekpunt
(Engels: least fixed point) van P. Dit geeft de volgende stelling.
Stelling 12.1.
Stel A en B verzamelingen, T de verzameling der partiële
functies van A naarBen P: T
~
T, die aan voorwaarden 1. en 2. voldoet.
Dan heeft P een kleinste dekpunt en wel U { PnYl[ n E lN }. De bij een recursieve procedure verkregen functie is de partiële functie, die het kleinste dekpunt is van de bij de procedure behorende operator.
- 81 -
§13. PARTIEEL GEORDENDE VERZAMELINGEN
We willen overgaan tot een wat algemenere formulering, waarbij we niet meer aan partiële functies gebonden zijn. Het idee van vergroting van informatie willen we echter behouden, hetgeen uitgedrukt wordt in een partiële ordening. We beschouwen een partieel geordende verzameling
l
<S,l>, dat is een verzameling S en een relatie
op S zo, dat voor alle
f E S, g E S, h E S geldt
f
l
f,
als
f
l
g en g
l
h, dan f
als
f l gen g
l
f, dan f = g •
l
h,
Het blijkt, dat we om bruikbare resultaten te verkrijgen nog verdere restricties aan de partiële geordende verzameling zullen moeten opleggen. Welke restricties dat zijn, zullen we aan de analogie met partiële functies ontlenen. Eerst bespreken we echter enkele begrippen, die betrekking hebben op partieel geordende verzamelingen. In een partieel geordende verzameling heet d een grootste ondergrens van fen g als dl f, dl gen als uit u l fen u
l
g volgtul d.
Het is duidelijk, dat een aan deze voorwaarden voldoende d door f en g vastgelegd is zodat we van de grootste ondergrens van f en g mogen spreken, zo deze bestaat. We noteren d = f functies hebben
twee elementen
n g.
In de verzameling der partiële
f en g inderdaad een grootste ondergrens,
namelijk de verza.melingstheoretische doorsnede f
n g, die inderdaad een
partiële functie is, die aan de vereisten voldoet.
~-----
-~
- 82 -
Op analoge wijze definiëren we de kleinste bovengrens v van f en g door: f
l
v, g
l
ven uit f
l
u eng
l
u volgt v
l
u. We noterenv=f.Wg. Bij par-
tiële functies behoeft een kleinste bovengrens niet te bestaan. Stel dat er een a € Df
n Dg
is, waarvoor geldt f'(a} -F g(a). Voor een kleinste boven-
grens zou moeten gelden f(a) = (f U g)(a) en g(a) = (f U g)(a), hetgeen onmogelijk is. Er bestaat dan zelfs geen gemeenschappelijke bovengrens h, laat staan een kleinste. De begrippen
n
en
U zijn
in plaats van voor twee elementen ook voor een
willekeurige deelverzameling D van S te formuleren. We doen het eerst voorn. Stel D c:: S, dan is n D het element VuES[VfED[u
l
f] .. u
van S dat voldoet aan VfED[ n D l f] en
l nn].
Voor een D c:: S hoeft rfu niet te bestaan, maar als hij bestaat is hij ondubbelzinnig vastgelegd. Nemen we D = 1/J, dan voldoet n'/J aan Vu€S[u
l n'/JJ .
Dit is het grootste element vanS, dat we, als het bestaat, met T (Engels: top) aanduiden. De verzameling der partiële functies heeft geen grootste element, behalve in triviale uitzonderingsgevallen; om die uit te sluiten veronderstellen we voortaan dat #A ;;. 1 en #B ;;. 2. Voor iedere niet-lege D bestaat in dit geval echter wel
nD
n D,
namelijk de verzamelingatheoretische doorsnede:
= nD.
De definitie van UD gaat analoog. Ook is nu U'/J het kleinste element van S, dat we, als het bestaat, met L (Engels: bottom) aanduiden. Voor partiële functies hoeft U D niet te bestaan, maar hij bestaat wel als
--
-
~
- 83 -
D een bovengrens heeft, dus als D een bovengrens heeft dan heeft D een kleinste bovengrens. Dit volgt gemakkelijk uit de volgende voor willekeurige partieel geordende verzamelingen geldende betrekking: UD = n{u E SIVfED [f
1. u]}
Dit moet zo gelezen worden, dat als n in het rechterlid bestaat, dan U in het linkerlid ook bestaat en de leden aan elkaar gelijk zijn. Deze· betrekking is gemakkelijk aan te tonen. We kunnen dit toepassen op de verzameling T van partiële functies en een deelverzameling DvanT die een bovengrens heeft. Dan is de verzameling in het rechterlid niet leeg, maar daaruit volgt in T dat
n van
die verzameling bestaat.
De verzameling T voldoet echter aan een sterkere voorwaarde·voor bovengrenzen, namelijk: als D c T en ieder tweetal elementen van D heeft een bovengrens in T, dan heeft D een bovengrens in T.
Stelling 13.1.
StelT de verzameling van alle partiële functies van A naar
B, D c T, "rED VgED 3vET [f
"rED
~
v en g ~ v]. Dan bestaat er een u E T zo, dat
[f ~ u].
Bewijs:
Kies u
= UD.
Het is voldoende om te bewijzen dat u een partiële
functie is. Stel (x,y) Eu en (x,z) Eu dan is er een f E D waarvoor y = f(x) eneengE D waarvoor z v E T zo, dat f
= g(x).
~ven g ~
Volgens veronderstelling is er nu ook een
v, maar dan is y = f(x)
= v(x)
g(x) = z.
Een iets zwaardere eis voor D krijgen we, als we v E D eisen. Dit leidt tot het begrip gerichte verzameling (Engels: directed set).
I
,~,-,-
~>-:
- 84 -
Definitie gerichte verzameling Een partieel geordende verzameling
<S ,J?
heet gericht
als
We passen dit vaak toe op een deelverzameling D van een gegeven partieel geordende verzameling S; in dat geval wordt de partiële ordening van D ontleend aan die van S; de v in de definitie moet dan ook in D liggen. De lege verzameling voldoet aan de eisen en is dus een gerichte verzameling; in de literatuur wordt hier vaak een uitzondering gemaakt en de lege verzameling niet meegeteld als gerichte verzameling; wij zullen haar echter wel meetellen. Voorbeelden van gerichte deelverzamelingen van S zijn totaal geordende deelverzamelingen (een partieel geordende verzameling Sheet totaal geordend als VfES VgES [f
l
g of g
l
f]). Een speciaal geval van een totaal geordende
verzameling is een niet-dalende rij : { f In E N } waarvoor geldt n
VnEE [fn
l
fn+ J. Een verzameling die een grootste element heeft, is uiter1
aard ook gericht. De verzameling T van partiële functies voldoet nu aan de volgende twee voorwaarden (geformuleerd voor een partieel geordende verzameling S). I. II.
UD bestaat voor alle gerichte D c S.
nn
bestaat voor alle niet-lege D c S.
Als in een partieel geordende verzameling inclusief D
nD bestaat voor alle D c S,
= 0, dan heetS een volledig tralie (Engels: complete lattice).
In dat geval bestaat ook 1-1 D voor alle D c S en S heeft een grootste element T =
n s = 1..
n 0 en
een kleinste element
1.
=
1-10. Er geldt ook US = T en
- 85 -
De verzameling der partiële functies is geen volledig tralie, maar kan tot een volledig tralie uitgebreid worden door een element
T toe
te voegen en
te verklaren, dat f ~ T voor alle f € T. Voor de D cT, waarvoor UD inT niet bestaat, geldt dan U D = T in de grotere verzameling. We zullen van deze uitbreiding geen gebruik maken. We gaan nu verder met een partieel geordende verzameling die aan voorwaarde I. voldoet; het blijkt niet nodig te zijn om voorwaarde II. te eisen en we zullen dat daarom ook niet doen. Een dergelijke partiële verzameling heet een cpo (Engels: complete partial order).
Definitie cpo Een partieel geordende verzameling
<s,l > met
de eigenschap, dat UD bestaat
voor alle gerichte D c S, heet een cpo.
Omdat U 111 ook bestaat in een cpo, heeft een cpo een kleinste element
.L.
Een
verzameling T 'Van partiële functies is een cpo; een volledig tralie is ook een cpo. We beschouwen nu een operator P: S
~
S, waarbij S een cpo is en vragen ons
af welke beperkingen we aan P zullen opleggen. Van de voorwaarden 1. en 2. die we bij partiële functies hebben opgelegd is 1. (monotonie) direct naar S over te dragen. Voor 2. is dat echter niet duidelijk. We leggen nu een geheel anders ogende voorwaarde aan P op en zullen later
(Stelling 13.4)
bewijzen dat deze in het geval van partiële functies equivalent is met voorwaarden 1. en 2. Een operator die aan deze voorwaarden voldoet heet continu.
- 86 -
Definitie continue operator Stel <s,l> een cpo en P: S-+ S. Dan heet P continu als geldt: voor alle D c S, D niet-leeg en gericht, bestaat U {Pfl f E D} en U{Pflf E D} = P(UD).
Stelling 13.2.
Een continue operator P op een cpo heeft een kleinste dek-
punt en wel U{Pn.l In E 1'1}. Bewi,js:
Stel <S,l> een cpo en P continu. We bewijzen eerst, dat P monotoon
is. Stel f E S,g E S, f l g. Dan is { f ,g} een niet-lege gerichte verzameling. Omdat P continu is bestaat U{Phlh E {f ,g}} = Pf U Pg en dit is= P( U {f ,g)) = = Pg. Daaruit volgt Pf lPg. Definieer nu de rij r ,r , ••• 0 1
door r
=
0
l.
en fn+ 1 = Pfn. Dan geldt VnEll [fn l fn+ 1 ], omdat P monotoon is. Dus {f In E ll} is een niet-lege, gerichte verzameling. Omdat S een cpo is, n
bestaat p = U[rnln E ll} en omdat P continu is, geldt Pp = U{Pfnln E 1'1} = = U[fn+ 1n E E} = p, duspis dekpunt van P. Stel nu q ES, Pq = q, dan 1
geldt VnEl! [fn l als f
[ q, dan f .
n+ 1
n-
dus p l
q]. Dit bewijzen we met volledige inductie: f = Pf
0
=
l.
l
q;
[ Pq = q. Dus is g een bovengrens van {f' In E ll},
n-
n
I
q.
We bespreken nu enkele varianten op Stelliug 13.2. Een klassieke stelling (Knaster-Tarski) zegt, dat in een volledig tralie een monotone operator een kleinste dekpunt heeft. Voor de door ons beoogde toepassingen heeft dit het bezwaar, dat we vaak niet met volledige tralies te maken hebben. Bij partiële functies hebben we bij uitbreiding tot een volledig tralie geen garantie dat het dekpunt niet het toegevoegde element T is. Er bestaan uitbreidingen van Stelling 13.2, die ontstaan door bij gelijkblijvende
o~k
- 87 -
conclusie de veronderstellingen te verzwakken. Men kan de e1s dat S een cpo is vervangen door de eis, dat U D bestaat voor alle totaal geordende D c S. Als men dit doet,wordt het dubieus hoe een continue operator moet worden gedefinieerd. We maken ons daarover echter niet druk, omdat de genoemde verzwakking geen echte verzwakking blijkt te zijn. Er geldt namelijk de volgende stelling.
Stelling 13. 3.
Als in een partieel geordende verzameling <S,l> geldt, dat
U D bestaat voor alle totaal geordende
D c S, dan bestaat U D ook voor alle
gerichte D c S. Het (moeilijke) bewijs van deze stelling behandelen we niet. We kunnen ook de eis voor P drastisch verzwakken. Het blijkt zo te zijn, dat in een cpo iedere monotone operator P een kleinste dekpunt heeft. Ook dit bewijzen we niet; het bewijs is moeilijker dan dat van Stelling 13.2, maar bovendien ook minder constructief, wat onder meer inhoudt, dat er niet zo'n mooie uit-
drukking voor het kleinste dekpunt uit- komt, hetgeen de praktische toepasbaarheid van het resultaat nadelig beïnvloedt. We tonen nu nog aan, dat voor partiële functies continuïteit van een operator overeenkomt met de voorwaarden 1. en 2.
Stelling 13.4. Stel A en B verzamelingen, T de verzameling van alle partiële functies van A naar B en P: T
~
P voldoet aan 1. en 2.
T. Dan geldt: ~Pis
continu.
- 88 -
Bewi.j s: We hebben eerder bewezen ,dat T een cpo is en dat als U D bestaat voorD c: T, dan UD = UD. We veronderstellen nu, dat P voldoet aan 1. en 2. Stel D c: T, D niet-leeg en gericht. Uit 1. volgt, dat ook {Pfjf E D} gericht is en dus dat U{Pfjf E D} bestaat. Maar UD bestaat ook en Un
= UD.
Stelnuf E D, dan f,.; U.D, dus Pf,.; P( UD). Dus U{Pfjf E D}..; P(UD). Stel nu (x,y) E P(UD). Op grond van 2'. is er een hE T zo, dat h..; UD 0 en (x,y) E Ph. Stel nu (z,w) E h, dan is er, wegens h c:'.UD, een k E D waarvoor (z,w) E k. Omdat h eindig is enD niet-leeg en gericht volgt hieruit, dat er een k E D bestaat zo, dat h c: k (let wel dat als h = waarde D
1 ~gebruikt
~.
de voor-
wordt). Maar op grond van 1. geldt ook Ph c: Pk en
(x,y) E Pk c: U{Pfjf E D}. Daarmee is aangetoond,, dat P(UD) .;o;.U{Pfjf E D}, Be~de ongeÜjkheden-iill.men- geven dat-P(DnT;, tJTI>rlf E D}.
nc;;;
pis continu.
Nu gaan we omgekeerd van de veronderstelling uit, dat P continu is, Het bewijs dat 1. geldt, ontlenen we aan het bewijs van Stelling 13.2, Ten behoeve van 2, merken we eerst op dat als f E T,dan{h E T jh..; f} niet-leeg en 0 gericht, en U{h E T jh..; f} = U{h E T jh..; f} = f. Uit de continuïteit 0 0 van P volgt dan, dat Pf = U{Phjh E T en h..; f} = U {Phjh E T0 en h..; f}. 0 Stel nu x E DPf' dan is er een hE T zo, dat h ";fen (x,(Pf)(x))E Ph en 0 dus x E DPh' Daarmee is 2". en dus 2. aangetoond.
I
We merken nog op dat uit bovenstaand bewijs volgt dat voor een continue operator Pop een verzameling T van partiële functies en een f ET geldt: Pf = U{Phjh E T en h,.; f} , 0 hetgeen op zichzelf ook een interessante betrekking is. Er volgt uit, dat door de Ph voor h E T alle Pf voor f E T vastgelegd zijn. Dit brengt ons 0
- 89 -
op de vraag of een operator P
0
die slechts op T gedefinieerd is voortge0
zet kan worden tot een continue operator P op T. Uit het bovenstaande volgt dat als het kan, het op slechts één manier kan. Het is duidelijk, dat het noodzakelijk is, dat P
0
monotoon is. Dit blijkt echter ook voldoende te
zijn.
Stelling 13.5. P : T 0 0
~
T
Als T de verzameling der partiële functies
een monotone operator, dan is P: T
Pf:= U{P hlh E T en h 0 0
~
B is en
T gedefinieerd door
f} voor f E T,
een continue operator T ~ T en VfET [Pf 0
Bewi.is:
~
A~
= P0f]
.
In de eerste plaats is Pf, zoals in de stelling gedefinieerd, een
partiële functie. Dit is zo, omdat uit de monotonie van P0 volgt, dat
{P hlh E r en h 0 0 h ~ f; dan P h 0
~
f} een gerichte verzameling is. Stel nuf E T0 , hE T0 ,
~P f en dus Pf = U{P hlh E T
0
0
en h ~ f} = P0 f. Daarmee is
0
VfET [Pf = P 0 f] aangetoond. 0
We bewijzen nu 1. en 2. voor P. g, dan {P hih E To en h 0
~
f} c {P hih E T en h 0 0
dus U{P hlh E T en h ~ f} ~U {P hih E To en h 0 0 0
~
g}, dus Pf
Stel f E T, gE T, f
~
~
~
Pg. Daarmee
er een h E To zo, dat h
~
f
en (x,y) E P 0h = Ph. Dus als x E DPf' dan is er een h E To zo' dat h
~
f
is 1. aangetoond. Stel nu (x,y) E Pf, dan
lS
g},
en x E DPh" Daarmee is 2".en dus 2. aangetoond. DusPis continu.
I
