No title

1

Hoofdstuk 1- Tellen

1 Tellen Korte inhoud. In dit hoofdstuk bekijken we oneindige verzamelingen, en gelijkmachtigheid van zulke verzamelingen. De begrippen ‘aftelbaar’ en ‘overaftelbaar’ worden ingevoerd. We zullen ook het diagonaalargument van Cantor bespreken. Tenslotte voeren we ‘oneindige getallen’ in; de kardinaalgetallen.

1.0. De theorie van het oneindige. In dit hoofdstuk gaat het vooral over oneindige verzamelingen, en hun grootte. Op het eerste gezicht lijkt het alsof er maar één soort oneindig is, en daarmee uit. Maar eind van de 19-de eeuw ontdekte Georg Cantor dat er verschillende ‘graden’ van oneindig zijn, de een nog groter dan de ander. Hij ontdekte daarmee een heel nieuw en fascinerend gebied dat de beroemde Duitse wiskundige David Hilbert betitelde als ‘het paradijs van Cantor’. Twee interessante web-sites over Cantor zijn te vinden op: http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Cantor.html http://www.c3.lanl.gov/mega-math/workbk/infinity/infinity.html

1.1. De paradox van Galilei. Hoe moeilijk het oneindige te begrijpen is, beschreef Galileo Galilei al in 1638 in een boek1 waarin hij zijn nieuwe theorieën uitlegt. Hij beschrijft een gesprek tussen de fictieve personages Simplicio, Salviati, en Sagredo, die proberen het oneindige te begrijpen, maar daarbij tegen problemen oplopen. (Zie Figuur 1.2.) Bekijk de verzameling A = {1,2,3,4,...} en de verzameling kwadraten B = {1,4,9,16,...}. Het is enerzijds duidelijk dat B ‘minder’ elementen heeft dan A, want je krijgt B uit A door elementen weg te gooien. Maar... anderzijds hebben A en B precies ‘evenveel’ elementen, want zoals in Figuur 1.2 wordt gedemonstreerd, kun je de elementen van A en B door paring precies met elkaar laten corresponderen. Dit lijkt met elkaar in tegenspraak. Toch is de tegenspraak maar schijnbaar (en daarmee een ‘paradox’, een schijnbare tegenspraak). Galilei en zijn verhaalpersonages kwamen er verder niet uit. Galilei trok de conclusie dat begrippen als ‘evenveel elementen’, of ‘minder elementen’ niet van toepassing waren op oneindige verzamelingen. Zelfs opperde hij de mogelijkheid dat alle oneindige verzamelingen evenveel elementen hadden in de zin van Figuur 1.2, namelijk door de elementen met elkaar te ‘paren’.

1

Discorsi e Dimostrazioni matematiche, intorno a due nuoue scienze. In Leida, appresso gli Elsevirii, M.D.C.XXXVIII. Formele Structuren - 2001

2

Hoofdstuk 1- Tellen

1

4

9

16

25

........

1

2

3

4

5

........

Figuur 1.2 1.1. OPGAVE. (Zie Figuur 1.3.) Laat zien dat de mogelijkheid die Galilei opperde, ook juist is voor (a) de oneindige verzamelingen gevormd door de punten op twee concentrische cirkels; (b) de punten op de twee lijnstukken in de driehoek.

Figuur 1.3 1.2. OPGAVE. Het Hilbert hotel. Een oneindig groot hotel heeft kamers genummerd 1,2,3,4,... . Het hotel is vol, alle kamers zijn bezet. Dan arriveert er een vermoeide gast. De hotel manager zegt: ‘Geen probleem, ook al zitten we vol, voor u vinden we nog wel een kamer. Hij neemt de microfoon van de intercom die direct met alle kamers is verbonden, en geeft een bepaalde order. De gasten volgen de order op, en nu is er plotseling een kamer voor iedereen; voor de al aanwezige gasten, maar ook voor de nieuwe gast. (a) Wat was de order die de manager uitsprak? (b) Een tijd later komt er een touringcar voorrijden, met daarin oneindig veel toeristen: toerist 1, toerist 2, toerist 3, ... Ook nu verzint de hotel manager een oplossing zodat ook deze nieuw aangekomen gasten een kamer kunnen krijgen. Hoe is de oplossing van de manager nu? (Dit verhaal werd door de eerder genoemde Hilbert gebruikt ter illustratie van de vreemde eigenschappen van oneindigheid.) 1.3. OPGAVE. De paradox van Tristam Shandy. Tristam Shandy was bezig zijn autobiografie te schrijven, maar hij deed dat heel uitvoerig. Zo uitvoerig dat hij een jaar nodig had om één dag van zijn leven te beschrijven. Al schrijvend raakt hij steeds verder achter. Na honderd jaar heeft hij nog niet eens zijn eerste halve levensjaar beschreven. Laat zien (of zie in) dat hij, als hij het eeuwige leven heeft, toch op den duur elke dag van zijn leven beschrijft.

1.2. Injecties en bijecties. Voor we Cantor’s oplossing geven, herhalen we eerst nog even enkele begrippen die al behandeld zijn in het college LTR (Logische Taal en Redeneermethoden).

Formele Structuren - 2001

1

4

injectie

geen injectie

2

surjectie 3

bijectie Figuur 1.6

1.2.1. DEFINITIE. Zij f een functie van verzameling A naar verzameling B (notatie f: A ! B). (i) Dan heet f een injectie van A naar B als "x,y#A (x $ y % f(x) $ f(y)). (We zeggen ook wel: injectie van A in B, en ook: f is injectief als duidelijk is om welke A en B het gaat.) (ii) f is een surjectie van A naar B als "y#B &x#A f(x) = y. Ook: surjectie van A op B, en: f is surjectief. (iii) f is een bijectie van A naar B als f zowel injectief als surjectief is. 1.2.2. NOTATIE. (i) Als er een injectie f van A in B bestaat, schrijven we A !in B. (ii) Als er een bijectie van A naar B bestaat, schrijven we A '! B. Deze ‘symmetrische notatie’ wordt gerechtvaardigd door opgave 1.5. Een injectie f: A ! B

4

Hoofdstuk 1- Tellen 1.5. OPGAVE. Laat zien dat als er een bijectie is van A naar B, er ook een bijectie is van B naar A. 1.6. OPGAVE. Gegeven is A ( B. Laat zien dat dan A !in B. Is het omgekeerde ook zo? 1.7. OPGAVE. (i) Bekijk de functie f: N x N ! N gedefinieerd door f(x, y) = 2x . 3y. Is f injectief, surjectief, bijectief? Welk paar x, y wordt door het natuurlijke getal 72 gecodeerd?

(ii) Bekijk de functie g gedefinieerd door g(x, y) = (x + y)(x + y + 1)/2 + y Vul de waarden g(x,y) in, in Figuur 1.7, in de blanco hokjes. Wat voor vermoeden geeft dit?

4 3 2 1 0 0

1

2

3

4

Figuur 1.7

We voeren nu een belangrijke notatie in: 1.2.3. NOTATIE. AB = {f | f: B ! A}. Vaak wordt AB ook geschreven als B ! A. 1.2.4. NOTATIE. De verzameling {0, 1} geven we vaak aan als ‘2’. Algemener hebben we: n = {0, 1, ..., n-1}. 1.2.5. DEFINITIE. De machtsverzameling van verzameling A, notatie )(A), is de verzameling van alle deelverzamelingen van A: )(A) = {X | X ( A}. 1.8. OPGAVE. (a) Bepaal )(A) voor het geval (i) A = *" (ii) A = {a}; (iii) A = {a,b,c}. Formele Structuren - 2001

5

Hoofdstuk 1- Tellen (b) Hoeveel deelverzamelingen heeft een verzameling met n elementen? 1.9. OPGAVE.

)(A) '!2 A.

Nog iets over de verzameling 2 N: de elementen hiervan zijn functies van naar {0, 1}. Dit zijn juist de oneindige rijen van 0-en en 1-en. Net zo bestaat de verzameling NN uit oneindige rijen natuurlijke getallen. 1.10. OPGAVE. Laat zien dat voor een verzameling A en voor n zoals boven gedefiniëerd, An juist de verzameling van “n-tupels” van elementen uit A is.

1.3. Het inzicht van Cantor. Het duurde tot 1873 voor het beslissende inzicht gevonden werd, door Georg Cantor. Hij vond de oplossing van de problemen met oneindigheid, bestaande uit de volgende definities. 1.3.1. DEFINITIE. Een verzameling A heeft een grootte, het aantal elementen van A, die we het kardinaalgetal van A noemen, notatie: #A. (Voor de leesbaarheid schrijven we soms ook #(A).) Verder worden deze groottes of kardinaalgetallen als volgt met elkaar vergeleken: 1.3.2. DEFINITIE. #

#A = #B +!A '!B

#

#A , #B +!A !in B

#

#A < #B +!#A , #B & #A $ #B.

Na deze definities is het paradijs van Cantor ontsloten. We kunnen al meteen inzien dat we het volgende intuïtief verwachte feit hebben: A ( B %!#A , #B 1.11. OPGAVE. Bewijs dit, door een vorige opgave te gebruiken (1.6).


6

Hoofdstuk 1- Tellen

Verder voeren we de volgende notatie in voor het aantal natuurlijke getallen: #N = -0. Dit is het eerste oneindige getal, aleph-nul. Er zijn dus -0 natuurlijke getallen. Als een verzameling -0 veel elementen heeft, heet hij aftelbaar. Er is dan dus een bijectie van N naar die verzameling. Als een verzameling oneindig is, en niet aftelbaar, heet hij onaftelbaar, of ook, overaftelbaar. Maar, wat betekent ‘oneindig’ eigenlijk? We kunnen dat nu precies vastleggen (definiëren): Een verzameling A is oneindig als #A . -0. Je kunt ook zeggen: als N !in A. Een oneindige verzameling bevat dus altijd een ‘kopie’ van de natuurlijke getallen–en is daarom per definitie oneindig. (Zie Figuur 1.8.) A

N

in

Figuur 1.8

En de paradox van Galilei wordt nu opgelost door het inzicht dat een oneindige verzameling best gelijkmachtig (') kan zijn met een echte deelverzameling, met andere woorden, een oneindige verzameling kan een echte deelverzameling hebben met evenveel elementen. 1.12. OPGAVE. Hoeveel even natuurlijke getallen zijn er? Hoeveel oneven? Hoeveel kwadraten? Hoeveel elementen heeft N x N ? *1.13. OPGAVE. Je zou oneindigheid ook anders kunnen definiëren. Bewijs de equivalentie van (i) en (ii): (i) Een verzameling is gelijkmachtig is met een echte deelverzameling; (ii) Een verzameling is oneindig volgens de gegeven definitie.

We kunnen nu ook precies bewijzen dat de eindige getallen, dat zijn dus de natuurlijke getallen 0, 1, 2, 3, ..., allemaal kleiner zijn dan het oneindige getal -0. Neem bijvoorbeeld de verzameling A ={a,b,c}. Dan is dus #A = 3. Nu is A !in N, dus #A , #N. Dus 3 , -0. Verder is ook 3 $ -0, want 3 = -0 zou betekenen dat A '! N, en dat is niet zo. Dus 3 < -0. Net zo voor andere natuurlijke getallen.


7

Hoofdstuk 1- Tellen

1.4. De stelling van Cantor en Bernstein.

#

A !in B & B !in A %!!A '!B

#

#A , #B & #B , #A %!!#A = #B

We kunnen nu oneindige getallen met elkaar vergelijken qua grootte, maar we missen nog iets heel essentieels. Bij de eindige getallen, (de natuurlijke dus), hebben we voor alle n en m het volgende feit: n , m & m , n %!n = m. Dit hebben we ook voor de oneindige getallen nodig, om alles goed te laten werken. En inderdaad is dit juist, zoals de Stelling van Cantor en Bernstein zegt. In bovenstaand kader zijn twee formuleringen gegeven, waarvan je snel kunt inzien dat ze hetzelfde zeggen. De stelling geeft een erg handige methode om van twee verzamelingen hun gelijkmachtheid te bewijzen: probeer een injectie van de een in de ander te vinden, en omgekeerd, en klaar. Je kunt de stelling ook zo weergeven: als twee verzamelingen wederzijds in elkaar gecodeerd kunnen worden, hebben ze evenveel elementen. We geven nu het bewijs. Dat bestaat eruit dat we de gegeven injecties ‘onder de microscoop leggen’ en er een bijectie uit proberen te sleutelen. Het bewijs is toch wel wat bewerkelijk, en daarom met een * gemerkt. *BEWIJS. Gegeven is A !in B & B !in A. Dus we hebben injecties f: A! B en g: B ! A. Deze f en g bepalen een aantal 'zigzag figuren', door herhaaldelijk ‘de trein heen’ (f) en ‘de trein terug’ (g) te nemen tussen A en B. (Zie Figuur 1.9.)


8

Hoofdstuk 1- Tellen

A

B f g

Figuur 1.9 Neem een punt a0 in A, bepaal het f-beeld b0 in B, bepaal daarvan het g-beeld in A, enz. Op deze manier ontstaat een zigzag als in Figuur 1.9. Ook naar de andere kant sluiten we de zigzag af, dat wil zeggen, we bepalen het g-origineel van a0 in B (als dit bestaat!), daarvan het f-origineel in A (als dit bestaat), enz. (In feite construeren we de maximaal samenhangende componenten in de graaf (A / B, R) waarbij R de binaire relatie is die aangeeft dat twee punten verbonden zijn door een f- of g-pijl.) Nu kun je gemakkelijk nagaan (gebruikend dat f en g injectief zijn) wat voor types zigzagpatronen ontstaan. Dit zijn de vijf types in Figuur 1.10. Merk op dat als we A en B disjunct veronderstellen (wat zonder verlies van algemeenheid kan), de zigzags een partitie van A / B vormen.

(b)

(c)

.....

(a)

.....

(e)

.....

.....

(d)

Figuur 1.10


9

Hoofdstuk 1- Tellen

De gezochte bijectie h van A naar B kunnen we nu ‘locaal’, dat wil zeggen per zigzag, aangeven. Op zigzags van type a, b, c, d nemen we h gelijk aan f. Op zigzags van type e wordt één punt niet door f bestreken, maar in dit geval kunnen we voor h de inverse van g nemen. Tenslotte plakken we alle stuksgewijs gedefinieerde delen van h aan elkaar tot de gezochte bijectie.

1.4.1 VOORBEELD. Bewijs dat NN '!2 N. We moeten dus om Cantor-Bernstein toe te kunnen passen laten zien dat er (i) een injectie is van 2 N in NN; (ii) een injectie is van NN in 2 N. (i) is simpel: elk oneindig 01-rijtje is ook een oneindige rij natuurlijke getallen. (ii) We moeten dus een rij natuurlijke getallen coderen als een 01-rij. Dit is niet moeilijk, bijvoorbeeld: de rij 4, 8, 7, 3, 0, 2, 1, ... coderen we als 11110111111110111111101110011010... En Cantor en Bernstein doen de rest. 1.14. OPGAVE. Bewijs uit de Stelling van Cantor-Bernstein dat #A , #B %! ¬(#B < #A). 1.15. OPGAVE. (i) Neem A = [0,1] = {x#! R | 0 , x , 1} en B = (0, 1) = {x#! R | 0 < x < 1}. (A heet een ‘segment’ en B een interval’.) Bewijs dat A '!B. (ii) Bewijs met Cantor-Bernstein dat de vereniging van twee disjuncte segmenten in R (bijvoorbeeld [0, 1] U [2, 5] evenveel punten hebben als één segment, bijvoorbeeld [10, 11]. 1.16. OPGAVE. Zij L de verzameling van de MIU-woorden, uit het hoofdstuk Deductie. Laat zien dat #L = -0. 1.17. OPGAVE. (i) Bewijs dat de vereniging van twee disjuncte aftelbare verzamelingen weer aftelbaar is. (ii) Hetzelfde als ze niet disjunct zijn.


10

Hoofdstuk 1- Tellen

1.5. De verzamelingen N, Z, Q, R. Het begin van wiskunde en informatica ligt bij de verzameling van natuurlijke getallen N = {0,1,2,3,...}. Deze wordt omvat door de verzameling van gehele getallen Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}, die op zijn beurt weer omvat wordt door de verzameling van rationale getallen Q = {n/m | n, m # Z, m $ 0}, op zijn beurt weer omvat door de verzameling reële getallen R:

N ( Z ( Q ( R.

#

N: natuurlijke getallen 0, 1, 2, 3, ...

#

Z : gehele getallen ...-3, -2, -1, 0, 1, 2, 3, ...

#

Q: rationale getallen 1/3, 5/4, 17/8, -0.2, ...

#

R: reële getallen 0, 3 -1, e, 2 (1/2), log 2,...

N Z Q R Een heel belangrijke deelverzameling P ( N is die van de priemgetallen, P = {1, 2, 3, 5, 7, 11, ...}. Ze zijn alleen deelbaar door 1 en door zichzelf. Een bekend feit, door de oude Grieken ontdekt, is dat er oneindig veel priemgetallen zijn. Er is veel bekend over deze getallen, maar ook veel nog niet. Zo is het niet bekend of er oneindig veel priemtweelingen zijn. Een priemtweeling is een paar {p, p+2} ( P . Priemgetallen zijn tegenwoordig heel belangrijk in de informatica: ze dienen voor encryptie van berichten.


Hoofdstuk 1- Tellen

11

1.18. OPGAVE. (i) Bepaal de eerste 10 priemtweelingen. (ii) Er zijn twee priemtweelingen die elkaar overlappen, namelijk {3, 5} en {5, 7}. Dat geeft een priemdrieling {3, 5, 7}. Waarom komen zulke priemdrielingen {p, p+2, p+4} verder niet voor?

Nog een bekend voorbeeld van een “open probleem” voor de naturlijke getallen is het Collatz probleem, ook wel Syracuse probleem of “3n+1” probleem genoemd. Dit bestaat uit het construeren van rijen natuurlijke getallen, als volgt. Gegeven is een begingetal. Bij een getal n in de rij wordt de opvolger zo geconstrueerd: als n even is wordt het door 2 gedeeld; als n oneven is wordt het volgende getal 3n + 1. Het vermoeden is nu dat ongeacht het begingetal, de rij op den duur altijd uitkomt op 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, ... Voorbeeld: 3, 10, 5, 16, 8, 4, 2, 1, 4, ... Dit vermoeden is bevestigd met computerberekeningen voor alle begingetallen tot 3.2 x 1016! 1.19. OPGAVE. Bereken de rij met begingetal 7.

We komen nu bij de rationale getallen, of breuken. Een bijzonderheid van de rationale getallen is dat ze ‘dicht liggen’ op de getallenrechte; tussen elke twee rationale getallen ligt er weer één, en zelfs oneindig veel. 1.20. OPGAVE. Gegeven zijn de rationale getallen x en y met x $ y. Geef een rationaal getal tussen deze twee. Hoe zie je dat er zelfs oneindig veel rationale getallen tussen x en y liggen?

Een kenmerk van rationale getallen is dat hun decimale ontwikkeling periodiek is, dat wil zeggen: vanaf zeker punt in de decimale ontwikkeling treedt een herhaling op van een groep cijfers. 1.21. OPGAVE. Ga dit na voor de breuk 1/7.

Uit de rationale getallen ontstaan weer de reële getallen; hoe ze precies ontstaan laten we hier achterwege. Je kunt ze ook voorstellen door middel van hun oneindige decimale ontwikkeling; bijvoorbeeld: 0 = 3.1415926535... Het getal 0 is niet rationaal; dus is de oneindige decimale ontwikkeling, waarvan boven het eerste stukje staat, niet periodiek. Dat dit zo is, is erg moeilijk in te zien. Wel is gemakkelijk in te zien dat het getal 12 niet rationaal (irrationaal) is:


12

Hoofdstuk 1- Tellen

1.22. OPGAVE. We bewijzen dat 12 irrationaal is. Stel

12 = t/n. Dan 2 = t2 /n2 , dus t2 = 2n2 . Kijk nu naar het

aantal factoren 2 in de linkerkant en rechterkant van deze vergelijking. Conclusie? *1.23. OPGAVE. Een ‘typisch wiskundige’ vraag is: is (12)(12) weer een irrationaal getal? Nog zo’n vraag van dezelfde soort is: zijn er twee irrationale getallen x en y zodat xy rationaal is? Op het eerste gezicht lijkt dat vreemd; irrationale getallen zijn ‘moeilijk’, en dan nog een machtsverheffing tussen twee zulke getallen... Toch zijn ze er wel, en de redenering is heel opmerkelijk: er zijn twee gevallen, het eerste is dat (12)(12) rationaal is; het tweede dat (12)(12) irrationaal is. In het eerste geval zijn we klaar, dan kunnen we voor x en y beide 12 nemen. In het tweede geval zijn we ook klaar! Want dan kunnen we nemen: x = (12)(12) en y = 12. Dan is namelijk xy = 2. (Reken dit na.) Dit is een voorbeeld van een ‘niet-constructieve’ redenering. (Overigens is met een zeer ingewikkeld bewijs bewezen dat (12)(12) irrationaal is.)

1.24. OPGAVE. Bewijs dat ook #Z = -0. Hint: gebruik Opgave 1.17. 1.25. OPGAVE. Bewijs dat #Q = -0. Hint: gebruik Opgave 1.7.

Het feit dat #Q = -0 is nogal verrassend, omdat de rationale getallen zo ‘dicht bezaaid’ op de getallenrechte liggen (zie Figuur 1.11). Namelijk, tussen elke twee rationale getallen zit weer een rationaal getal, en zelfs oneindig veel, en tussen elke twee daarvan weer oneindig veel, enzovoorts! We hebben nu de volgende vraag: hoeveel elementen bevat R? Misschien ook -0? Ook Cantor vond dit erg moeilijk te beantwoorden. In 1873 vond hij het verrassende antwoord dat er meer dan -0 veel getallen in R zijn. Als opstap om dit te begrijpen kijken we eerst naar rijtjes van 0-en en 1-en. 1.6. De 0-1-rijen. We bekijken nu de verzameling van oneindige rijtjes bestaande uit 0 en 1. Deze verzameling wordt aangegeven met de notatie 2 N . *1.26. OPGAVE. (i) Een 01-rij heet periodiek als hij bestaat uit een ‘aanloopstuk’ gevolgd door een oneindige herhaling van een 01-woord. Geef een voorbeeld van een periodieke 01-rij, en ook van een niet-periodieke 01-rij. (ii) Bewijs dat er -0 veel periodieke 01-rijen zijn.


13

Hoofdstuk 1- Tellen

(iii) Definieer functies zip, die twee 01-rijen in elkaar zipt, alternerend de een en de ander; en een inverse functie unzip die een rijtje unzipt tot twee rijen. (iv) Bewijs dat er evenveel a-periodieke rijtjes zijn als alle rijen. [Hint: codeer een algemeen rijtje in een aperiodieke door hem te zippen met een vaste a-periodieke; en pas Cantor-Bernstein toe.]

In de vorige opgave hebben we gezien dat er -0 veel periodieke 01-rijen zijn. Maar is de hele verzameling 2 N van 01-rijtjes misschien ook aftelbaar? Cantor had een prachtig bewijs dat dit niet zo is. Het argument staat sindsdien bekend als Cantor’s diagonaalargument, en gaat als volgt. Stel dat de 01-rijen aftelbaar zijn. (We zullen hieruit een tegenspraak afleiden.) Dan is er dus een bijectie van N naar 2 N . Deze bijectie zou er bijvoorbeeld zo uit kunnen zien: 0 ' 1 0 1 0 1 1 0 ...

(r0)

1 ' 1 0 1 1 0 1 1 ...

(r1)

2 ' 0 1 0 1 0 1 0 ...

(r2)

3 ' 1 1 1 1 1 1 1 ...

(r3)

4 ' 0 0 0 1 0 0 0 ...

(r4)

5 ' 1 1 0 0 1 1 0 .. .

(r5)

6 ' 0 0 1 1 0 0 1 .. .

(r6)

.. ....... In deze opsomming komt dus elk 01-rijtje ergens voor! Zo zou bijvoorbeeld de periodieke rij 000111000111... op plaats 100087 kunnen staan (en is dus r100087); de aperiodieke rij 10100100010000100000... op plaats 999 (en is dus r999), enzovoorts. Bekijk nu de rij van dikgedrukte getallen op de ‘diagonaal’: 1001011... en neem hiervan het ‘negatief’: 0110100..., de ‘anti-diagonaal’. Noem deze rij d. Met deze rij d is iets bijzonders aan de hand. Hij is niet hetzelfde als r0, want d en r0 verschillen op de eerste plaats (mogelijk op nog meer plaatsen, maar dat doet er niet toe). Ook is d $ r1, waarom? En d $ r2, waarom? En algemeen: d $ rn, waarom? Dus d komt niet in de opsomming voor! Tegenspraak met het boven gestelde. Dus is het boven gestelde niet waar, dat wil zeggen: er is geen bijectie tussen N en 2N . Dus hebben we #N $ #2N . Dus hebben we #N < #2N , want #N , #2N is eenvoudig in te zien. (Hoe?) We hebben nu dus een nieuw oneindig getal gevonden dat echt


14

Hoofdstuk 1- Tellen

groter is dan -0, namelijk #2N. 1.7. De reele getallen R. We hebben nu gezien dat het aantal 01-rijtjes groter is dan -0. Anders gezegd: de verzameling van 01-rijtjes is overaftelbaar. We laten nu zien dat het aantal reële getallen precies gelijk is aan het aantal 01-rijtjes, dus ook overaftelbaar. Dit volgt uit het feit dat

R ' 2 N. Hoe kunnen we een bijectie tussen R en 2 N maken? De truc is een reëel getal binair te ontwikkelen; bijvoorbeeld 0.5 is in het binaire stelsel 0.10000... We coderen nu een reëel getal via zijn binaire expansie als 01-rijtje, en en omgekeerd een 01-rijtje als een reëel getal. De stelling van Cantor en Bernstein doet dan de rest van het werk. Dus we weten nu dat #R > -0. Het getal #R wordt ook wel het continuüm-getal genoemd, en geschreven als c. Hoewel wij hieraan niet toekomen, vermelden we dat met kardinaalgetallen ook ‘gerekend’ kan worden, met de operaties + (optelling), “x” (vermenigvuldiging), en machtsverheffen. Dan blijkt dat #R in feite is: 2-0 . Dit is ‘intuïtief’ al wel min of meer te begrijpen als je bedenkt dat #R = #2 N, maar echt begrijpen kan natuurlijk pas als we ‘machtsverheffen’ van kardinaalgetallen zouden hebben ingevoerd. *1.27. OPGAVE. Bewijs dat de volgende verzamelingen evenveel elementen hebben: (i)

het eenheidslijnstuk E = [0,1] = {x#! R | 0 , x , 1};

(ii)

het eenheidsvierkant V in het vlak: V = {(x,y) #! R 2 | 0 , x,y , 1};

(iii)

de eenheidskubus K in de ruimte: K = {(x,y,z) #! R 3 | 0 , x,y,z , 1}.

1.8. De alephs. We hebben nu kennis gemaakt met het kleinste oneindige getal -0, en ook gezien dat er grotere getallen dan -0 zijn. Het eerste getal groter dan -0 noemde Cantor -1. En het dan eerstvolgende grotere getal is -2. Zo krijgen we de rij van alephs


15

Hoofdstuk 1- Tellen

-0, -1, -2, -3, ..., -1000, ... Maar dit is nog niet alles! Na al deze alephs met als rangnummer in de rij een natuurlijk getal n, komt er één die groter is dan alle vorige, namelijk de aleph met rangnummer -0 zelf. Dit is dus --0. En nog veel verder komt de aleph met rangnummer --0, en lang daarna de aleph met dat als rangnummer, enzovoorts, in een nooit eindigende rij, met gigantische grote alephs zoals waarbij de stack van aleph-subscripten zelf oneindig is. De mysteries van deze oneindige getallen hebben ook schrijvers geïnspireerd, zoals uit het volgende citaat blijkt. Ik zag de Aleph, vanuit alle gezichtspunten, ik zag in de Aleph de aarde, en in de aarde weer de Aleph en in de Aleph de aarde, ik zag mijn gezicht en mijn ingewanden, ik zag jouw gezicht, ik voelde een duizeling en huilde, omdat mijn ogen dat geheime, slechts bij gissing bestaande voorwerp hadden gezien, waarvan de naam wederrechtelijk door de mensen gebruikt wordt, maar dat geen mens heeft aanschouwd: het onvoorstelbare heelal. J.L. Borges, De Aleph.

De rij van alephs is een soort maatstok waarlangs we verzamelingen kunnen leggen, om hun grootte te ‘meten’. Nu is er nog de volgende belangrijke vraag: waar op deze oneindigegetallen-maatstok van alephs ligt het continuümgetal c, of 2-0 ? Deze vraag heeft Cantor lang bezig gehouden; hij dacht dat dit getal op de plaats van -1 ligt, dus dat 2-0 = -1. Cantor’s vermoeden werd later de ‘continuüm-hypothese’genoemd. Pas in 1963 vond de Amerikaanse wiskundige Paul Cohen het verrassende antwoord op dit continuümprobleem. Het blijkt dat de gangbare axioma’s van de verzamelingenleer geen uitsluitsel geven over de plaats van 2-0 in de rij van alephs! Zo is het ‘consistent’ aan te nemen dat 2-0 = -1, maar ook dat 2-0 = -2, of 2-0 = -3, of 2-0 = -$%%1. Maar een uitleg van wat dit ‘consistent’ zijn precies betekent, voert


16

Hoofdstuk 1- Tellen

op dit moment te ver. *1.9. Het abstracte diagonaalargument. In 1.4 hebben we met Cantor’s diagonaalargument gezien dat #N < #(2 N). Dit is in feite een bijzonder geval van nog een sterke stelling van Cantor, die een ‘abstracte versie’ van het diagonaalargument gebruikt. 1.9.1. STELLING (Cantor). Voor elke verzameling A geldt: #A < #)(A). BEWIJS. Stel A '!)(A). Dan bestaat er een bijectie f: A ! )(A). Nu had Cantor het volgende briljante idee: Neem de verzameling B ( A gedefinieerd door B = {x # A | x 2 f(x)}. B # )(A), dus B moet optreden als beeld onder f, zeg B = f(b). Geldt b # B? Volgens de definitie van B geldt b # B + b 2 f(b) en dus, omdat f(b) = B: b # B + b 2 B, een contradictie. De veronderstelling dat A ' )(A) is hiermee weerlegd: #A $ #)(A). Dus #N < #)(N) < #)()(N)) < ...; er zijn dus steeds ‘grotere oneindigheden’. Ook bestaat er geen grootste ‘oneindigheid’, i.e. geen A met #B , #A voor alle B. (Want #)(A) , #A geldt niet.) *1.28. OPGAVE. In deze opgave geven we een bewijs dat er een niet-reguliere taal is, op een totaal andere manier dan in hoofdstuk 2 is gedaan. Gegeven is het alphabet 3 = {0,1}. (i) Bepaal #(3*). (ii) Bewijs dat er -0 veel reguliere expressies zijn. (iii) De verzameling van talen over 3, is

)(3*). Wat is #)(3*)?

(iv) Concludeer dat er meer talen dan reguliere expressies zijn, en dat er daarom een taal is die niet door een reguliere expressie wordt aangeduid.


17

Hoofdstuk 1- Tellen

*1.10. Rekenen met kardinalen. Rekenen met kardinaalgetallen is verrassend gemakkelijk: som en product van twee kardinaalgetallen 4 en 5 is eenvoudig het grootste van die twee: 4 + 5 = 4 x 5 = max (4, 5) Zo hebben we bijvoorbeeld: -0 + -0 = 2 x-0 = -0 n x -0 = -0 -0 x -0 = (-0)2 = -0 Een mooie vergelijking is: -0-0 = 2-0. Verder is de volgende ongelijkheid van belang: 4 < 24 ; dit is een gevolg van de stelling van Cantor, Stelling 1.9.1. We besluiten met de definities van +, x, en machtsverheffen. #

Som: Gegeven zijn kardinaalgetallen 4 en 5. Neem nu disjuncte verzamelingen A en B

zodat #A = 4 en #B = 5. Dan is 4 + 5!= #(A U B). #

Product: Gegeven zijn kardinaalgetallen 4 en 5. Neem nu verzamelingen A en B zodat

#A = 4 en #B = 5. Dan is 4 x 5!= #(A x B). Hierbij is A x B het cartesisch product van A en B, dat wil zeggen: A x B = {(a, b) | a # A, b # B}. #

Exponentiatie. Gegeven zijn kardinaalgetallen 4 en 5. Neem nu verzamelingen A en B

zodat #A = 4 en #B = 5. Dan is 4 5 = #(AB). Hierbij is AB de verzameling functies van B naar A, dus AB = {f | f: A ! B} (zie notatie 1.2.3.). 1.29. OPGAVE. Bewijs dat R 1.30. OPGAVE. Bereken: (3

' N x 2N . Bewijs hiermee de vergelijking -0-0 = 2-0.

x 2-0 + 2-0) 2 x (-0)2 +-0 = ?


Hoofdstuk 1- Tellen

18


41

Hoofdstuk 3 - Eindige automaten

3 Eindige automaten Korte inhoud. In dit hoofdstuk bekijken we de belangrijkste bouwstenen die we nodig hebben in de (theoretische) informatica: woorden (strings), grafen, bomen, functies, streams. Ook bekijken we enkele fundamentele feiten over deze datatypen. Veel van de begrippen in dit hoofdstuk zullen we in de volgende hoofdstukken weer tegen komen.

3.0. Introductie. In dit Hoofdstuk bekijken we enkele van de meest belangrijke ‘data typen’ die voorkomen in de informatica, en met name de theoretische informatica. Het is een allerminst volledig overzicht over belangrijke data typen! Verder bekijken we de hier behandelde data typen zonder de bijbehorende operaties erop, die in de ‘praktische’ informatica wel aan de orde zijn. Bijvoorbeeld op het data type Bag, of zoals hier genoemd, multiset, zijn de operaties ‘insert’, ‘delete’ van belang; maar wij kijken hier alleen naar enkele interessante theoretische aspecten. (Een meer volledige behandeling, inclusief de bijbehorende operaties, zit in onze colleges die over algebraïsche specificaties gaan.) We beginnen met een korte terugblik op de belangrijkste soorten getallen in ons arsenaal. Dit wordt gevolgd door een kort uitstapje naar reguliere expressies en reguliere talen; ook eindige deterministische automaten, gebruikt als acceptors, komen aan bod. We besluiten met een korte excursie naar het data type ‘bomen’, mogelijk oneindig, al of niet gelabeld. 3.1. Strings en talen. Het

volgende fundamentele data type is dat van de strings. Een string is een eindig rijtje symbolen uit een alfabet. (Strings worden soms ook woorden genoemd, vanwege de overeenkomst

met het dagelijks spraakgebruik.) Vaak wordt een alfabet aangegeven met !. In het vorige hoofdstuk hebben we uitvoerig gewerkt met strings over het alfabet ! = {M, I, U}. De verzameling van alle strings ‘over’ !, wordt genoteerd als !*. We voeren een vaste notatie in voor de lege string, bestaande uit 0 symbolen: ". Verder hebben we de operatie concatenatie die twee strings achter elkaar zet. Bijvoorbeel, MI geconcateneerd met III is MIIII. In het algemeen Formele Structuren - 2001

42


is wv de concatenatie van strings w en v. Verder staat wn voor www...w (n maal). Dus w0 = ". Natuurlijk geldt voor elke string w # !*: w" = "w = w. Een taal L over het alfabet ! is een deelverzameling L $ !*. Dus de kleinste taal over ! is %, de lege taal; en de grootste is !* zelf. Verwar % niet met "! En ook niet met {"}! Behalve strings kunnen we ook talen met elkaar concateneren. We definiëren voor talen L1 en L2 hun concatenatie L1L2 als volgt: L1L2 = {wv | w # L1, v # L2} . Verder definiëren we Ln als LLL. . .L (n maal), met in het bijzonder L0 = . . . .(Vul aan wat je hier verwacht.) En tenslotte definiëren we de *-afsluiting L*van een taal L: L* = L0 U L1 U L2 U L3. . . 3.1.1. OPGAVE. (i) Gegeven is de taal = {0n1m | n, m

# N} over het alfabet {0, 1}. Wat is L2?

(ii) Wat is {0, 1}*? (iii) En {00, 11}*?

3.1.1. Reguliere expressies. We hebben nu een paar operaties gezien om uit gegeven talen een nieuwe taal te maken: concatenatie, vereniging U, en de *-afsluiting. Met die operaties kunnen we een notatiesysteem voor talen maken: de reguliere expressies. Het is gebruikelijk om in plaats van U een + te schrijven; en de taal bestaande uit een enkele letter, {a}, schrijven we kortweg als a. Bijvoorbeeld a + b + c staat voor de taal {a, b, c}. Nu de officiële ‘inductieve’ definitie: 3.1.1.1. DEFINITIE. Gegeven is een alfabet !. (i)

%, " en a # ! zijn reguliere expressies.

(ii)

Als r1 en r2 reguliere expressies zijn, dan ook (r1 + r2), (r1.r2), r1*.


43


Vaak wordt de “.” in (r1.r2) weggelaten; en ook buitenste haakjes laten we meestal weg. Verder is de afspraak dat concatenatie sterker bindt dan +, en * weer sterker dan + en concatenatie. Dus ab + c is (ab) + c, en niet a(b + c); en ab* is a.(b*) en niet (ab)*. 3.1.1.2. OPGAVE. (i)

Welke taal stelt de reguliere expressie a*(a + b) voor?

(ii)

En (a + b)*(a + bb)?

(iii)

Geef een reguliere expressie voor de taal over het alfabet {0, 1} van alle strings waarin 00 als substring voorkomt.

*3.1.1.3. OPGAVE.Vind een reguliere expressie voor de taal bestaande uit 01-woorden waarin geen subwoord 00 voorkomt.

Vaak zijn er verschillende reguliere expressies die dezelfde taal aanduiden. Bijvoorbeeld: (0 + 1)* + 1* en (0 + 1) * hebben allebei als bijbehorende taal de verzameling van alle strings over {0, 1}. 3.1.1.4. DEFINITIE. Een taal heet regulier als hij wordt aangeduid door een reguliere expressie. 3.1.2. Deterministische eindige automaten. We bekijken nu een totaal andere manier om talen te beschrijven. Daartoe definiëren we de zogenaamde deterministische eindige automaat (afgekort dea), die gebruikt zal worden om talen te ‘accepteren’. De officiële definitie is een hele mond vol: Een dea M is gedefiniëerd als een vijftal M = (Q, !, &, q0, F) waarbij Q een eindige verzameling toestanden is; ! een eindige verzameling symbolen, het input alfabet; &: Q x ! ' Q is een totale functie, de transitie functie; q0 is de begintoestand; F $ Q is de verzameling van eindtoestanden.


44


In plaats van zo’n vijftal zullen we een dea altijd voorstellen op een meer overzichtelijke manier, namelijk met een transitie graaf. Een voorbeeld is in Figuur 3.2 gegeven. De begintoestand wordt door een uit het niets komende pijl aangegeven; de toestanden als cirkels met daarin de naam van de toestand; de eindtoestanden met dubbele cirkels. De pijlen met labels uit ! erbij geven precies de transitiefunctie weer. Uit elke toestand (ook uit de eindtoestanden!) vertrekt voor elke a # ! precies één a-pijl. Soms (zie Figuur 3.3) schrijven we meer labels bij dezelfde pijl; bijvoorbeeld de a,b-pijl van q1 naar q2. Dit is een “afkorting” voor een tweetal pijlen, namelijk een a-pijl en een b-pijl beide van q1 naar q2. De werking van een dea M als ‘acceptor’ van strings uit !* is als volgt. Gegeven is een string w. We ‘lezen deze string nu in’, door in de begintoestand van M te beginnen, en bij elke volgende letter de overeenkomstige transitie in M te maken. Omdat vanuit elke toestand voor elke letter precies één pijl vertrekt, komen we bij het inlezen van w in een uniek bepaalde toestand van M uit. (Vandaar dat M deterministisch heet.) Als deze toestand een eindtoestand is, zeggen we dat de string w geaccepteerd is door de dea M; en anders is de string geweigerd. (De eindtoestanden zijn dus accepterende toestanden.) Bekijk als voorbeeld de dea in Figuur 3.2. Hier wordt de string 101 geaccepteerd, en ook 111, maar 00 wordt geweigerd. Nu de voor de hand liggende maar toch belangrijke definitie: een taal L wordt door dea M geaccepteerd, als elke string w # L door L geaccepteerd wordt, en alle andere niet. 0

q0

0

0 1

q1

1 1

q2

Figuur 3.2 3.1.2.1. OPGAVE. Welke taal wordt door de automaat in Figuur 3.3 geaccepteerd?

a

q0

a,b

b

q1

a, b

q2

Figuur 3.3 Formele Structuren - 2001

45


3.1.2.2. OPGAVE. Maak een automaat die alle strings over {a, b} accepteert die met ab beginnen.

We hebben nu twee manieren leren kennen om talen te ‘bepalen’: door middel van reguliere expressies, en door middel van een dea als acceptor. Op het eerste gezicht hebben die twee manieren weinig met elkaar te maken. Maar, één van de meest fundamentele stellingen op dit gebied van de ‘formele talen’ zegt dat beide manieren gelijkwaardig zijn! Namelijk: 3.1.2.3. STELLING. De reguliere talen zijn precies de talen die door een eindige automaat geaccepteerd worden. We zullen dit niet hier bewijzen. Een volledig bewijs staat bijvoorbeeld in het boek ‘An introduction to formal languages and automata’ (Peter Linz, 1990), dat gebruikt wordt in het college ‘Formele talen’. Een belangrijke vraag is nu of elke taal door een eindige automaat geaccepteerd wordt. met andere woorden, of elke taal regulier is. Dit is niet zo, en we zullen nu gaan bewijzen dat er ook niet-reguliere talen zijn. Een voorbeeld van een niet-reguliere taal is gemakkelijk te vinden: L = {0n1n | n ( 0}. Voor het bewijs dat L niet-regulier is, hebben we het volgende “telprincipe” nodig.

05

06 07

17

015 010 hier 0717 maar ook 01517 geaccepteerd. Figuur 3.4


46


3.1.2.4. STELLING. (Pigeon-hole principle) (i)

Gegeven is een ladenkast met n laden, en m > n dingen. Hierbij zijn n , m # N . Als de

dingen in de laden worden opgeborgen, is er een lade die minstens 2 dingen bevat. (ii) Gegeven is een ladenkast met eindig veel laden, en oneindig veel dingen. Als de dingen in de laden worden opgeborgen, is er een lade die oneindig veel dingen bevat. Het bewijs van dit principe, dat we afkorten met PHP, laten we achterwege omdat dit feit zo evident is. We gaan nu verder met het bewijs dat L = {0n1n | n ( 0} niet-regulier is. Stel dat deze taal wel regulier is. Dan is er dus een een dea die M accepteert. Bekijk nu alle strings 0n, voor n ( 0. Deze strings voeren we in de dea M in. Elke string leidt naar een bepaalde toestand van M. (Zie Figuur 3.4.) Volgens PHP moet er dan een toestand zijn waar twee strings van de 0n strings naar toe leiden. In het voorbeeld van Figuur 3.4 zijn dit 07 en 015, die in de grijze toestand terechtkomen. Als we nu verder gaan vanuit deze toestand met 17, dan komen we in een eindtoestand, want de string 0717 wordt door M geaccepteerd. Maar dan wordt ook de string 01517 geaccepteerd! En dat is tegenspraak met de aanname dat M precies de strings 0n1n accepteert. Dus deze taal is niet regulier. (In hoofdstuk 3, Tellen, zullen we een heel ander bewijs zien van het feit dat er nietreguliere talen zijn, gebaseerd op het feit dat er “veel meer talen dan reguliere expressies zijn”.) 3.2. Bomen. We komen nu toe aan een ander fundamenteel data type, de bomen. We zijn in het vorig hoofdstuk, Deductie, al bomen tegen gekomen; zie Figuur 3.5.


47


MI MIU MIUIU MIUIUIUIU

MII MIIU

MIIII

MIIUIIU

MIIIIU

afleidingsboom van

MIIIIIIII MUI .......

MIU

L

Figuur 3.5

We geven nu de kenmerken van een boom. •

Anders dan echte bomen groeien onze bomen van boven naar beneden.

•

Het bovenste punt of knoop is de wortel.

•

Vanuit een knoop gaan er pijlen naar een aantal opvolgers van die knoop; er is geen volgorde voor die opvolgers (dus ze kunnen omgedraaid worden). Officiëel: de bomen in deze sectie zijn commutatief. Een knoop kan ook oneindig veel opvolgers hebben.

•

Vaak laten we de richting van de pijlen weg, omdat deze toch altijd van boven naar beneden gaat.

•

Elke knoop is via een uniek pad verbonden met de wortel.

•

Bij de knopen zetten we vaak ‘labels’, zoals in het voorbeeld van de MI-boom. Een boom kan ook ongelabeld zijn.

•

Als een knoop geen opvolgers heeft, is het een eindknoop.

•

Een tak van een boom is een rij, eindig of oneindig, beginnend bij de wortel, waarbij telkens met een opvolger wordt verder gegaan. Bijvoorbeeld MI, MIU, MIUIU, MIUIUIUIU, ... is een oneindige tak van de MI-boom. Een tak loopt maximaal door, dat wil zeggen, hij stopt in een eindknoop of is oneindig.

•

Een boom heet eindig splitsend, als elke knoop maar eindig veel opvolgers heeft.

•

Een boom is eindig als hij maar eindig veel knopen heeft, anders oneindig.

•

Een sub-boom van boom T is een boom met als wortel een knoop r van T, en bestaande


48


uit alles onder r. Een directe sub-boom van T is een sub-boom met als wortel een opvolger van de wortel van T. 3 5

3

7

8

9

0 1

8 7

5

0 9 5

5

1

Figuur 3.6

Figuur 3.6 bevat tweemaal dezelfde boom; het is een eindige boom met natuurlijke getallen als labels. 3.2.1. OPGAVE. Hoeveel sub-bomen en directe sub-bomen heeft de boom in Figuur 3.6?

3.2.1. Bijzondere bomen. We bekijken nu een merkwaardig feit over bomen dat we in andere versies nog terug zullen zien. Het is de Russell paradox, in een presentatie van N.G. de Bruijn. In deze sectie bekijken we ongelabelde bomen. 3.2.1.1. DEFINITIE. Een boom is bijzonder als hij hetzelfde is als een directe subboom. Een boom is gewoon als hij niet bijzonder is. 3.2.1.2. OPGAVE. Geef de bijzondere bomen aan in Figuur 3.7, en teken nog een andere bijzondere boom.

Figuur 3.7

Van een bos bomen (eindig of oneindig) kunnen we een nieuwe boom maken door een nieuwe wortel te nemen en het bos bomen als directe subbomen daaronder te hangen. Dit doen we nu met het bos van gewone bomen. We vormen de superboom S die als directe subbomen heeft: alle gewone bomen. (Zie Figuur 3.8.) Probeer nu de volgende vragen te beantwoorden! Formele Structuren - 2001

49


superboom met als directe subbomen alle gewone bomen Figuur 3.8 3.2.1.3. OPGAVE. Is de superboom S gewoon? Is S bijzonder?

3.2.2. König’s Lemma. Er is een eenvoudige eigenschap van bomen die bekend staat als König’s Lemma (KL), die we nu gaan bewijzen. KL is simpel, maar een mooi stukje ‘gereedschap’ bij veel argumenten. 3.2.2.1. STELLING. Een eindig splitsende, oneindige boom heeft een oneindige tak. BEWIJS. Zie Figuur 3.9. We kijken erst naar de wortel; ‘hieronder’ liggen oneindig veel knopen. We kleuren de wortel daarom zwart. Kijk nu naar de directe subbomen van de wortel; wegens PHP moet er minstens één van hen weer oneindig veel punten hebben. We kiezen er zo één, en kleuren zijn wortel zwart. Van deze subboom bekijken we weer de directe subbomen, en kleuren weer de wortel zwart van één van de directe oneindige subbomen. Enzovoorts. Zo vinden we een tak met zwarte punten, en omdat het keuzeproces zoals beschreven oneindig doorgaat, is dat een oneindige tak.


50


oneindige tak

Figuur 3.9 3.2.2.2. OPGAVE. Laat zien dat de voorwaarde ‘eindig splitsend’ echt nodig is voor het hebben van een oneindige tak. (De andere voorwaarde is uiteraard ook nodig.)

We geven nu een toepassing van KL, en introduceren daarbij een volgend belangrijk data type, de multisets. 3.2.3. Multisets. In deze sectie bekijken we multisets van natuurlijke getallen. Een voorbeeld van zo’n multiset is: {7, 7, 0, 5, 6, 4, 4, 7, 88, 88}. Het is een verzameling van natuurlijke getallen, met dit verschil met gewone verzamelingen dat een element meer keren voor kan komen. Op multisets kunnen we de volgende acties uitvoeren, Formele Structuren - 2001

51


aangegeven met een pijl (!): als M1 een multiset is, kunnen we een nieuwe multiset M2 maken door precies één element van M1 te verwijderen, en te vervangen door willekeurig veel kleinere elementen, mogelijk 0. We schrijven dan M1 ! M2 . Bijvoorbeeld: {7, 7, 0, 5, 6, 4, 4, 7, 88, 8 8}! {7, 7, 0, 5, 6, 4, 4, 7, 88, 10,10,10,10,9,9,9,6,6,6}! {7, 7, 0, 5, 5,5,5,5, 4, 4, 7, 88, 10,10,10,10,9,9,9,6,6,6}! {7, 7, 5, 5,5,5,5, 4, 4, 7, 88, 10,10,10,10,9,9,9,6,6,6} !. . . . (Het element dat in een stap vervangen wordt door kleinere, is telkens dik gedrukt.) Dus multisets kunnen sterk groeien in deze stappen. Toch is het zo dat er geen oneindige rij van zulke stappen mogelijk is! Vroeg of laat moet de reeks eindigen, en wel in de lege multiset die we met % aangeven. Dit heet multiset terminatie. 3.2.3.1. STELLING. Er is geen oneindige rij M1 ! M2 ! M3 ! ... ! Mn . . . BEWIJS. Stel er is wel zo’n rij. (Zie Figuren 3.10 en 3.11.)We beginnen met een wortel te tekenen, en daaronder de boom die ontstaat door de elementen in de multisets M1, M2, ... als knopen te tekenen. Een knoop die in een stap wordt vervangen door 0 of meer kleinere getallen, heet actief. In elke stap Mn ! Mn+1 is dus precies één actieve knoop; de rest is passief. Van een actieve knoop gaan we met dik gedrukte lijntjes naar zijn 0 of meer kleinere opvolgers. van een passieve knoop trekken we een gewoon dun lijntje naar zijn opvolger, die hetzelfde is. Zo ontstaat de boom in Figuur 3.10; het is een oneindige boom. Nu gaan we de knopen die altijd passief zijn, wegsnoeien. (Een snoeiplek is aangegeven met een zwart blokje.) Dit geeft de gesnoeide boom in Figuur 3.11. Nog steeds is de gesnoeide boom oneindig. Want, in elke stap is er minstens één knoop, namelijk de actieve; en er zijn oneindig veel stappen. De boom is ook eindig splitsend. Toepassen van KL geeft dus dat er een oneindige tak is. deze tak moet oneindig veel dikke lijntjes bevatten, anders was het een passieve tak en was hij weggesnoeid. Maar langs elk dik lijntje daalt het natuurlijk getal dat daar staat. Dat kan niet oneindig vaak gebeuren. Tegenspraak. Er is dus niet zo’n rij en de stelling is bewezen. Formele Structuren - 2001

52


voor snoeien M1

4

5

2

➞ M2

3

5

3

2

3

➞

5

M3

➞ M4

5

1

1

2

2

2

2

2

2

➞ .....

Figuur 3.10

na snoeien M1

4

➞ M2

3

3

➞ 3

M3

2

2

2

➞

2

M4

1

1

➞ .....

Figuur 3.11 3.2.3.1. OPGAVE. Hoe lang kan de multiset {0,0,0,0,0,0,0} blijven bestaan, voor terminatie optreedt? En hoe lang {1}? 3.2.3.2. OPGAVE. Amoeben zijn als volgt gedefiniëerd:


53

Hoofdstuk 3 - Eindige automaten (i)

O is een amoebe (de oer-amoebe);

(ii)

als x1,...,xn amoeben zijn, dan is ook

x 1 x2 ....... xn

een amoebe. De xi (i = 1,...,n) zijn de ‘zonen’ van de grote amoebe. (iii)

Een kolonie van amoeben is een multiset van amoeben, zoals in Figuur 3.12.

amoeben kolonie Figuur 3.12 Amoeben ontplooien de volgende activiteit: amoebe ) kan elk van zijn zonen xi door een willekeurig aantal copieën xi,...,xi (ki maal, ki ( 0) van die zoon vervangen; ) zelf sterft bij die actie (dat wil zeggen, zijn buitenste schil verdwijnt). Amoebe ) mag verschillende van zijn zonen simultaan vermenigvuldigen. Als ) de oer-amoebe is (dus geen zonen heeft), kan hij spontaan sterven. Een voorbeeld van een rij stappen in het leven van een amoebenkolonie is gegeven in Figuur 3.13. Bewijs dat een amoebenkolonie slechts eindig lang kan blijven leven.

➞

➞

➞ ...

levensloop van kolonie amoeben Figuur 3.13



54



55



56



57



58



59


75

Hoofdstuk 5 - Rekenen met processen

5 Rekenen met processen Korte inhoud. Dit hoofdstuk bevat een inleiding in de algebra van processen. Vanuit atomaire processen (acties, stappen, gebeurtenissen) worden meer ingewikkelde processen gemaakt met de operaties som, product en ‘merge’. Met recursie kunnen oneindige processen gemaakt worden. Verder bekijken we processen die met elkaar kunnen communiceren door het uitvoeren van een gezamelijke actie.

5.0. Wat is een proces? Een proces is iets dat voortgaat, verloopt, met stappen in de tijd. Processen komen overal in het dagelijks leven voor: in de rechtsspraak, in de industrie, en in de informatica. Net zoals je kunt rekenen met getallen in de algebra, of met logische uitspraken in de logica, kun je ook rekenen met processen. Zo’n rekenmethode voor processen, procesalgebra genaamd, is ongeveer 20 jaar geleden ontwikkeld, door onder andere de Engelse onderzoekers Hoare en Milner. Beiden hebben voor hun werk de Turing Award gekregen, de ‘Nobelprijs voor informatica’. 5.1. Atomaire processen. Net zoals woorden (strings) gevormd worden door letters uit een alfabet, worden processen opgebouwd uit atomaire processen, die niet verder te ontleden zijn. We geven die atomaire processen, ook wel ‘acties’ of ‘stappen’ of ‘events’ (gebeurtenissen) genoemd, vaak aan met letters a,b,c,... Wat die acties precies zijn, hangt af van de toepassing. 5.1.1. VOORBEELD. Gegeven is een bord met 5 maal 5 vakjes. We willen de beweging van de zwarte stip (● ) over het bord beschrijven. De acties zijn: up, down, left, right, afgekort als, u, d, l, r. 5 . 2 . Samengestelde processen Het na elkaar doen van acties geven we aan als vermenigvuldiging. Zo is r.r.r de beweging die bestaat uit 3 stappen naar rechts; en r.r.r.u.u.u is een beweging van de punt naar het grijze veld n. Vaak laten we de ‘punt’ weg, zodat het laatste ‘bewegingsproces’ is: rrruuu. Een andere

manier om op n te komen is rururu. We gebruiken ook exponenten, net als in gewone algebra, en kunnen dan voor de laatste twee processen schrijven: r3u3, respectievelijk (ru)3.

Formele structuren - 2001

76


Figuur 5.1.1 5.1.1. OPGAVE. Hoeveel manieren zijn er om met de acties u,d,l,r de stip naar n te brengen? En als alleen de acties u en r gebruikt mogen worden?

Boven hebben we al gezien hoe uit atomaire processen (acties) processen kunnen worden samengesteld door de operatie “.”, vermenigvuldiging, ook wel ‘sequentiële compositie’ genoemd, omdat het een sequentie van acties maakt. Er zijn nog andere operaties om processen op te bouwen. De eerste andere operatie is met de “+”, som, ook wel ‘alternatieve compositie’ genoemd. Bijvoorbeeld in de situatie van Figuur 5.1 staat r3u3 + (ru)3 voor het proces dat òf r3u3 doet, òf (ru)3. Er wordt dan dus een keuze gemaakt tussen beide alternatieven. 5.2.1. VOORBEELD. We bepalen het proces dat de beweging(en) beschrijft van de stip naar n op het 2-bij-3 bord als in Figuur 5.2.1(a), met alleen u en r acties. In de vakjes zijn de ‘tussenprocessen’ al ingevuld. Het gevraagde proces is dus r(ru + ur) + urr. Merk op dat zo’n proces dus niet alleen weergeeft wat er feitelijk gebeurt, maar meer dan dat, namelijk alles wat er (in die situatie) kan gebeuren, de potenties. Als we alleen in de feitelijke executies (procesverlopen) geïnteresseerd zijn, moeten we bij elke + een keuze maken; we krijgen dan een “trace” of executie. Dit proces heeft dus 3 traces; rru, rur en urr. 5.2.1. OPGAVE. Zie het 3-bij-3 bord in Figuur 5.2.1(b).


77


rr

r

r(ru+ur) + urr

ru + ur

u

(a)

(b) Figuur 5.2.1

(i)

Bepaal het proces dat de bewegingen van ● naar het grijze veld beschrijft, met alleen u en r acties.

(ii)

Geef de afzonderlijke traces.

Met de + en de . hebben we de basis-operaties om samengestelde processen te maken uit de elementaire acties. Processen die alleen opgebouwd zijn uit atomen met + en ., heten basis procestermen. Er gelden voor + en . enkele wetten net als in gewone algebra. Deze staan in Tabel 5.1. Sommige van deze wetten zijn letterlijk hetzelfde als in gewone algebra, - maar de wet x + x = x is nieuw, en betekent dat de keuze tussen proces x doen of proces x doen hetzelfde is als proces x doen. Merk ook op dat de “.” hier niet commutatief is, zoals in gewone algebra; het proces ur is verschillend van ru, de volgorde van de acties doet er toe. Wel is u + r = r + u.

basis proces algebra x+y=y+x x + (y + z) = (x + y) + z x+x=x (x + y) .z = x.z + y.z x.(y.z) = (x.y).z Tabel 5.1.1: BPA 5.2.3. OPGAVE. Laat zien dat (a + b)3 = a(a(a + b) + b(a + b)) + b(a(a + b) + b(a + b)).

NOTATIE. ● om het gebruik van haakjes te beperken schrijven we bijvoorbeeld a.b.c in plaats van (a.b).c; Formele structuren - 2001

78


de . bindt sterker dan de +, dus (a.b) + c schrijven we als a.b + c; ● buitenste haakjes worden weggelaten; ● de . wordt vaak weggelaten, net als in ‘gewone’ algebra, dus in plaats van a.b + c schrijven we ab + c. ●

5.2.1. OPMERKING. We hebben niet algemeen a(b + c) = ab + ac. De reden is dat de ‘timing’ van de keuzemomenten verschillend is: in a(b + c) wordt na de a-actie pas voor b of c gekozen; in ab + ac wordt voor de a-actie, al meteen bij het begin, gekozen. Dit verschil in timing van keuzes is belangrijk wanneer er communicatie acties in het spel is, zoals op het eind van dit hoofdstuk. Dat de vergelijking a(b + c) = ab + ac dan onwenselijk is, wordt hier niet precies gemaakt. 5 . 3 . Procesgrafen. Het is vaak handig om een proces als graaf te tekenen. De procesgraaf van r(ru+ur) + urr is:

r

r

u

u

u

r

r

r

Figuur 5.3.1

●

De bovenste knoop heet de wortel; de knopen waar geen pijl uit vertrekt, zijn de eindknopen. De traces zijn de takken van wortel tot eindknoop, in het voorbeeld: rru, rur, urr.

●

De gelabelde pijlen o !a o in de graaf heten transities.

●

We noemen een procesgraaf een procesboom als er geen 2 pijlen naar dezelfde knoop gaan. Deze graaf in Figuur 5.3.1 is dus ook een procesboom.

●

De graaf van een enkele actie a is de transitie o !a o, dus de graaf met twee punten

●

en een a-pijl. De ‘+’ geeft een splitsing in de graaf. Preciezer: de graaf van x + y ontstaat door de grafen van x en y te tekenen en daarvan de wortels op elkaar te plakken (te identificeren).

●


79


Voor het tekenen van x.y gaan we als volgt te werk: plak alle eindknopen van x op elkaar en maak dit de wortel van y.

●

5.3.1. OPGAVE. (i) Teken de procesgraaf van (a + b)3. (ii) Teken de procesboom van a(a(a + b) + b(a + b)) + b(a(a + b) + b(a + b). (iii) Hoe is de boom in (ii) uit de graaf in (i) te krijgen?

5 . 4 . Parallelle processen. Na de basis operaties + en . introduceren we nu de operator die twee processen ‘parallel schakelt’, de merge ||. Voor processen x en y is x || y het proces dat de stappen van x en y ‘door elkaar heen weeft’. Hiermee kunnen we processen heel ‘compact’ beschrijven. 5.4.1. VOORBEELD. We gaan na wat het proces ab || ba kan doen:

ab || ba a

b

b || ba b

ab || a b

a

ba

b || a

b

b a

a

a a

a ab

b || a a

b

b

a b

a

a

a

b

b b

b

Figuur 5.4.1


80


Hierbij hebben we als ‘geheugensteuntje’ het na een stap overblijvende proces in de knopen geschreven. De knopen zijn als het ware de ‘toestanden’ van het proces. Bovenstaande procesboom behoort ook bij het proces a(bba +b(ba + ab)) + b(a(ba + ab) + aab). We kunnen nu als vervolg op de eerdere vergelijkingen voor + en ., vergelijkingen geven voor || zodat inderdaad ab || ba uitgerekend kan worden tot a(bba +b(ba + ab)) + b(a(ba + ab) + aab). Daarvoor is nodig dat we een hulp-operator invoeren, de left-merge . De vergelijkingen voor || en zijn:

x || y = x y + y x +x|y a x = a.x ax y = a(x || y) (x + y) z = x z + y z

Tabel 5.4.1

(Het omcirkelde gedeelte x|y moet in deze tabel weggedacht worden; het speelt pas verderop een rol.) 5.4.2. VOORBEELD. Als voorbeeld ‘reduceren’ we de term bab || ab tot een basis procesterm. Steeds is het gedeelte dat wordt ‘herschreven’, dikgedrukt. bab || ab

= bab ab + ab bab = b(ab || ab) + ab bab = b(ab ab + ab ab) + ab bab = b(ab ab) + ab bab = b(a(b || ab)) + ab bab = b(a(b ab + ab b)) + ab bab = b(a(bab + ab b)) + ab bab = b(a(bab + a(b || b))) + ab bab = b(a(bab + a(b b+b b))) + ab = b(a(bab + a(b b+b b))) + ab = b(a(bab + a(b b))) + ab bab

bab bab


81


= b(a(bab + abb)) + ab bab = b(a(bab + abb)) + a(b || bab) = b(a(bab + abb)) + a(b bab + bab b) = b(a(bab + abb)) + a(bbab + bab b) = b(a(bab + abb)) + a(bbab + b(ab || b)) = b(a(bab + abb)) + a(bbab + b(ab b + b ab)) = b(a(bab + abb)) + a(bbab + b(ab b + bab)) = b(a(bab + abb)) + a(bbab + b(a(b || b) + bab)) = b(a(bab + abb)) + a(bbab + b(abb + bab)) 5.4.3. OPMERKING. Wat stelt eigenlijk voor? Zoals de notatie al suggereert, is x y is eigenlijk de ‘linkerhelft’ van het proces x || y, namelijk die helft waarbij de eerste stap uit x komt. En y x is omgekeerd de ‘rechterhelft’ van x || y, namelijk die helft waarbij de eerste stap uit y komt. Dus inderdaad is x || y = linkerhelft + rechterhelft = x y + y x. 5.4.3.1. OPGAVE. Geef in de graaf in Figuur 5.4.1 de sub-grafen aan die corresponderen met ab

ba en ba

ab.

5.4.4. OPMERKING. De operatie || is associatief voor basistermen; dat wil zeggen, als r, s, en t basis termen zijn, dan geldt (r || s) || t = r || (s || t). We zullen dit hier niet bewijzen. We moeten nog definiëren hoe de graaf van x || y getekend wordt. Dit gebeurt zoals al aangegeven in Voorbeeld 5.4.1. In de volgende sectie geven we een precieze definitie. ●

5.4.1. OPGAVE. (Zie Figuur 5.4.1. Bewijs dat ab || ba = a(bba + b(ab + ba) + b(aab + a(ba + ab)). De lange uitdrukking a(bba + b(ab + ba) + b(aab + a(ba + ab)) wordt dus veel compacter weergegeven door de korte uitdrukking ab || ba. 5.4.2. OPGAVE. Reken de volgende termen uit tot basis term. a || b ab || c (a + b) || c 5.4.3. OPGAVE. Bereken: (i) a || a = aa; (ii) a || a || a = aaa. (iii) Welk vermoeden krijg je hierdoor?


82

Hoofdstuk 5 - Rekenen met processen 5.4.4. OPGAVE. Idem met (i) a2 || b2 (ii) (a + b) || (a + b) (iii) a3 || a3 (iv) abc || (d + e). 5.4.5. OPGAVE. Wat stelt het proces r || r || r || u || u || u voor in de stituatie van Figuur 5.1.1? En r.r.r || u.u.u? 5.4.6.

OPGAVE. Geef het proces dat de stip naar n brengt (op alle mogelijke manieren), op het vakjes-veld in

Figuur 5.4.3(a), met alleen r en u acties. Maak handig gebruik van ||. (Merk op dat het voor het veld als in (b) niet zo simpel gaat.)

(a)

(b) Figuur 5.4.3

B

c b

A

a acties a, b, c Figuur 5.4.4

5.4.7. OPGAVE. Een mier loopt over de ribben van de kubus in Figuur 5.4.4 van punt A naar B. De acties bij deze wandeling zijn: a (een hele zijde naar rechts), b (een hele zijde naar achter), c (een hele zijde omhoog). (i)

Kies een wandeling van A naar B en schrijf deze als proces met behulp van de acties a, b, c.

(ii)

Hoeveel wandelingen zijn er mogelijk? Formele structuren - 2001

83

Hoofdstuk 5 - Rekenen met processen (iii)

Geef het proces dat al deze wandelingen als mogelijke traces heeft, met behulp van de merge operator.

5.4.8. OPGAVE. De mier wandelt van A naar B in twee op elkaar gestapelde kubussen, in Figuur 5.4.5. Geef het proces dat alle mogelijke wandelingen (met dezelfde acties als in de vorige opgave) als traces heeft. 5.4.9. OPGAVE. In Figuur 5.4.6 staat een flatgebouw van 81 kubussen. Schrijf het proces op dat alle mogelijke wandelingen van een mier van A naar B als traces heeft, met weer dezelfde acties als in opgaven 5.4.7 en 5.4.8. Als we dit proces uitrekenen tot basis term, krijgen we de zeer lange term op de volgende bladzijde (deze term staat in het boek Baeten -Weijland, Procesalgebra, zie de lijst met literatuur.) (Een ‘combinatorische’ opmerking terzijde: dit proces heeft 1680 traces. Dit is als volgt in te zien: Elk trace is een woord van 9 letters lang, namelijk een woord met 3 a’s erin, 3 b’s, en 3 c’s; bijvoorbeeld aabcacbcb. Om de a’s te plaatsen, moeten we 3 plaatsen uit 9 kiezen; dit kan op “9-over-3” = 9!/3!.6! = 84 manieren. Om daarna de b’s te plaatsen op de overgebleven 6 plaatsen, zijn er “6-over-3” = 6!/3!.3! = 20 manieren. De c’s kunnen maar op 1 manier op de laatste 3 plaatsen gezet worden. In totaal dus 84 x 20 = 1680 traces.)

B

c b

A

a acties a, b, c

Figuur 5.4.5


84


B

A c b a acties a, b, c

Figuur 5.4.6

a(a(a(b(b(bccc + c(bcc + c(bc + cb))) + c(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb))) + c(b(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + c(b(b(bc + cb) + cbb) + cbbb))) + b(a(b(bccc + c(bcc + c(bc + cb))) + c(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb))) + b(a(bccc + c(bcc + c(bc + cb))) + b(accc + c(acc + c(ac + ca))) + c(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba)))) + c(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))))) + c(a(b(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + c(b(b(bc + cb) + cbb) + cbbb)) +b(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + c(a(b(b(bc + cb) + cbb) + cbbb) + b(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + c(abbb + b(abb + b(ab + ba)))))) + b(a(a(b(bccc + c(bcc + c(bc + cb))) + c(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb))) + b(a(bccc + c(bcc + c(bc + cb))) + b(accc + c(acc + c(ac + ca))) + c(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba)))) + c(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + b(a(a(bccc + c(bcc + c(bc + cb))) + b(accc + c(acc + c(ac + ca))) + c(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba)))) + b(a(accc + c(acc + c(ac + ca))) + c(a(acc + c(ac + ca)) + c(a(ac + ca) + caa))) + c(a(a(bcc + c(bc + cb)) + b(acc + c(acca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)))) + c(a(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + b(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + c(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))))) + c(a(a(b(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + c(b(b(bc + cb) + cbb) + cbbb)) + b(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + c(a(b(b(bc + cb) + cbb) + cbbb) + b(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + c(abbb + b(abb + b(ab + ba))))) + b(a(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + b(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + c(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)))) + c(a(a(b(b(bc + cb) + cbb) + cbbb) + b(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + c(abbb + b(abb + b(ab + ba)))) + b(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + c + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + c(a(abbb + b(abb + b(ab + ba))) + b(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)))))) + b(a(a(a(b(bccc + c(bcc + c(bc + cb))) + c(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb))) + b(a(bccc + c(bcc + c(bc + cb))) + b(accc + c(acc + c(ac + ca))) + c(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba)))) + c(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))))) + b(a(a(bccc + c(bcc + c(bc + cb))) + b(accc + c(acc + c(ac + ca))) + c(a(bcc + c(bc + cb)) + b(acc +c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba)))) + b(a(accc + c(acc + c(ac + ca))) + c(a(acc + c(ac + ca)) + c(a(ac + ca) + caa))) + c(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)))) + c(a(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + b(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + c(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))))) + b(a(a(a(bccc + c(bcc + c(bc + cb))) + b(accc + c(acc + c(ac + ca))) + c(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba)))) + b(a(accc + c(acc + c(ac + ca))) + c(a(acc + c(ac + ca)) + c(a(ac + ca) + caa))) + c(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)))) + b(a(a(accc + c(acc + c(ac + ca))) + c(a(acc + c(ac + ca)) + c(a(ac + ca) + caa))) + c(a(a(acc + c(ac + ca)) +



85

c(a(ac + ca) + caa)) + c(a(a(ac + ca) + caa) + caaa))) + c(a(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + b(a(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(ac + ca) + caa) + caaa)) + c(a(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + b(a(a(ac + ca) + caa) + caaa) + c(a(a(ab + ba) + baa) + baaa)))) + c(a(a(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + b(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + c(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)))) + b(a(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + b(a(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(ac + ca) + caa) + caaa)) + c(a(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + b(a(a(ac + ca) + caa) + caaa) + c(a(a(ab + ba) + baa) + baaa))) + c(a(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + b(a(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + b(a(a(ac + ca) + caa) + caaa) + c(a(a(ab + ba) + baa) + baaa)) + c(a(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)) + b(a(a(ab + ba) + baa) + baaa))))) + c(a(a(a(b(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + c(b(b(bc + cb) + cbb) + cbbb)) + b(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + c(a(b(b(bc + cb) + cbb) + cbbb) + b(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + c(abbb + b(abb + b(ab + ba))))) + b(a(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba)))) + b(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + c(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) b(a(ab + ba) + baa)))) + c(a(a(b(b(bc + cb) + cbb) + cbbb) + b(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + c(abbb + b(abb + b(ab + ba)))) + b(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + c(a(abbb + b(abb + b(ab + ba))) + b(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))))) + b(a(a(a(b(bcc + c(bc + cb)) + c(b(bc + cb) + cbb)) + b(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + c(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab+ ba)))) + b(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + c(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)))) + b(a(a(a(bcc + c(bc + cb)) + b(acc + c(ac + ca)) + c(a(bc + cb) + b(ac + ca) + c(ab + ba))) + b(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa))) + b(a(a(acc + c(ac + ca)) + c(a(ac + ca) + caa)) + c(a(a(ac + ca) + caa) + caaa)) + c(a(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + b(a(a(ac + ca) + caa) + caaa) + c(a(a(ab + ba) + baa) + baaa))) + c(a(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + b(a(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + b(a(a(ac + ca) + caa) + caaa) + c(a(a(ab + ba) + baa) + baaa)) + c(a(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)) + b(a(a(ab + ba) + baa) + baaa)))) + c(a(a(a(b(b(bc + cb) + cbb) + cbbb) + b(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(ab + b(ab + ba))) + c(abbb + b(abb + b(ab + ba)))) + b(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + c(a(abbb + b(abb + b(ab + ba))) + b(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)))) + b(a(a(a(b(bc + cb) + cbb) + b(a(bc + cb) + b(ac + ca) + c(ab + ba)) + c(abb + b(ab + ba))) + b(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + c(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + b(a(a(a(bc + cb) + b(ac + ca) + c(ab + ba)) + b(a(ac + ca) + caa) + c(a(ab + ba) + baa)) + b(a(a(ac + ca) + caa) + caaa) + c(a(a(ab + ba) + baa) + baaa)) + c(a(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)) + b(a(a(ab + ba) + baa) + baaa))) + c(a(a(abbb + b(abb + b(ab + ba))) + b(a(abb + b(ab + ba)) + b(a(ab + ba) + baa))) + b(a(a(abb + b(ab + ba)) + b(a(ab + ba) + baa)) + b(a(a(ab + ba) + baa) + baaa))))).


86


5.5. Procesgrafen en transitieregels. We geven nu een precieze definitie van de procesgraaf van een term door middel van een afleidingssysteem (zoals in Hoofdstuk 1, Deductie) van transitieregels. Hierbij komt het symbool o voor, dat staat voor terminatie (het is als het ware een eindknoop van een procesgraaf. Het is een hulpsymbool, en niet zelf een proces. actie.

a !a o

plus.

x !a x’ " x + y !a x’ y !a y’ " x + y !a y’ x !a o " x + y !a o y !a o " x + y !a o

maal.

x !a o " x.y !a y x !a x’ " x.y !a x’.y

merge.

x !a o " x || y !a y y !a o " x || y !a x x !a x’ " x || y !a x’ || y y !a y’ " x || y !a x || y’

left-merge

x !a o " x x !a x’ " x

y !a y y !a x’

y


87


communicatie

x !c x’ & y !c* y’" x || y !c x’ || y’ x !c o & y !c* o " x || y !c o x !c o & y !c* y’" x || y !c y’ x !c x’ & y !c* o" x || y !c x’

5.6. Recursieve processen. Tot nu toe zijn we alleen eindige, terminerende processen tegengekomen. Procesalgebra wordt echter pas interessant en nuttig als we ook over recursief gedefineerde processen kunnen spreken. We vervolgen nu de sectie over BPA uit hoofdstuk 5. 5.6.1. VOORBEELD. Het eenvoudigste voorbeeld van een koffie-automaat (die we K zullen noemen), werkt als volgt: je kunt er een kwartje inwerpen (de actie i(25), waarna de automaat een kopje koffie geeft (de actie gc) en weer in zijn begintoestand terugkeert. We kunnen beginnen met op te schrijven: K = i(25).gc, maar dit zou betekenen dat de machine na het schenken van de koffie klaar is. Een beter idee is: K = i(25).gc.K.

(*)

In deze vergelijking komt het proces dat we willen specificeren (K) ook rechts van het =-teken voor. We noemen (*) daarom een recursieve vergelijking. De procesgraaf van proces K ziet er als volgt uit; het is een cyclische graaf: i(25) K gc Formele structuren - 2001

88


5.6.2. VOORBEELD. Het allereenvoudigste recursief gedefinieerde proces is: X = aX. Dit proces kan een a-stap doen en is dan weer zichzelf: X !a X. Dus X kan een oneindige reeks van a-stappen doen: X !a X !a X !a X !a . . . De procesgraaf van X is een enkele a-cycle:

X a

5.6.3. VOORBEELD. X = aX + b. Hoe tekenen we van dit proces de graaf? We beginnen met het tekenen van de wortel, die we met X aangeven:

X Vanuit de wortel van deze graaf kunnen we twee stappen zetten: een a-stap die ons weer in X brengt, of een b-stap waarmee het proces termineert:

a

X b


89


En dit is de graaf van het proces X. We hebben de vergelijking X = aX + b ‘opgelost’. 5.5.9. VOORBEELD. Bovenstaand recept werkt ook voor processen die met meer dan één recursievergelijking gedefinieerd zijn, zoals bijvoorbeeld: X = (a + b)Y + cdX Y = cccX Altijd is in het geval van meer recursievergelijkingen het eerste proces waarom het gaat; de overige vergelijkingen zijn voor de hulp-processen. Hier is dus de Y een ‘hulpproces’. Eerst veranderen we iets aan de eerste vergelijking, door middel van het BPA axioma (x + y) z = xz + yz: X = aY + bY + cdX Y = cccX. Nu beginnen we met het oplossen van het stelsel vergelijkingen door de wortels X en Y te tekenen:

X

Y

Vervolgens bekijken we wat er gebeurt als we één atomaire stap zetten: a X

Y b

c

dX

c

ccX

Als namen van nieuwe knopen kiezen we dus ‘subtermen’ van de rechterzijden van de recursievergelijkingen. Zetten we dit proces voort, dan vinden we als oplossingen voor X en Y:


90


a X c

d

a Y

c

X

b

Y cb

c

c

cX

d

c dX

c

cX c

ccX

ccX

dX

en nu is de linkerhelft, met de pijl naar X, de gezochte oplossing als procesgraaf van het stelsel vergelijkingen. De linker, omdat bij een recursiestelsel van meer dan één vergelijking de eerste variabele de ‘leidende’ variabele is, dat wil zeggen het proces waar het om gaat. NOTATIE: Zoals duidelijk is uit de voorbeelden boven, geven we de ‘recursievariabelen’ aan met hoofdletters. 5.6.5. VOORBEELD: Counter. We analyseren de volgende recursievergelijkingen, met recursievariabelen C en D, en acties u en d (voor up en down): C = uDC D = d + uDD De eerste vergelijking geeft het bedoelde proces aan, de tweede is een hulpvergelijking. De eerste vergelijking zegt dat er vanuit de wortel C een u-stap is naar een proces DC. We weten dus al dat een stukje van de bijbehorende procesgraaf er als volgt uitziet:

C

u

DC

We willen nu zien wat het proces DC kan doen. Hiertoe vullen we in wat we volgens de tweede vergelijking voor D hebben: DC = (d + uDD)C = dC + uDDC. We zien nu dat dit laatste proces dC + uDDC een d-stap naar C kan doen, of een u-stap naar DDC. We kunnen nu weer een stukje van de procesgraaf van C tekenen: Formele structuren - 2001

91


d

C

DC

u

u

DDC

Het patroon wordt nu duidelijk: DDC = (d + uDD)DC = dDC + uDDDC, dus DDC kan een d-stap naar DC doen of een u-stap naar DDDC. Zo doorgaande vinden we dus de oneindige procesgraaf

C0

d u

C1

d u

C2

d u

C3

d u

5.6.1. OPGAVE. Bepaal de oplossing (als procesgraaf) van X = aXX + b. Wat stelt het proces X voor? 5.6.2. OPGAVE. Los op als procesgraaf: X = aXXX + b. 5.6.3. OPGAVE. Bepaal de oplossing voor X van het stelsel {X = aX + bcY + d, Y = aaY + cdX} 5.5.9. OPGAVE. Gegeven is een oneindig schaakbord waarop net als in het vorige hoofdstuk 5, een punt ● kan bewegen met acties u, d, l, r. Wat stellen de volgende recursief gedefinieerde processen voor? (i) X = uX. (ii) X = lrX. (iii) X = rruullddX. (iv) X = (uuu||rrr).X *5.6.5. OPGAVE: Laat zien dat de recursievergelijking C = u(d || C) hetzelfde proces geeft als de Counter C in Voorbeeld 5.6.5. De || is hier nog als in Hoofdstuk 5, zonder communicatie.

5.7. Processen met deadlock. In het vervolg hebben we een nieuwe speciale actie nodig die we ‘deadlock’ noemen en noteren als #. Voor # gelden de volgende twee axioma’s:


92


deadlock x +# = x #.x = # Tabel 5.7.1: Deadlock

De intuïtie ‘achter’ # is dat het ‘de onmogelijke actie’ is. Vandaar dat in een keuze x + # voor de x gekozen moet worden. En vandaar ook # x = #, want na # is er niets. Misschien is het moeilijk een concreet begrip van # te vormen, maar dat doet er niet toe; de ‘rechtvaardiging’ van # is dat deze constante ‘werkt’, en een axiomatisering van communicerende processen mogelijk maakt waarmee goed gerekend kan worden. 1 5.7.1. VOORBEELD. Met de axioma’s voor # kan in veel gevallen de # uit een term worden ‘weggerekend’: (i) a + #(a# + e) b +#a + = a (ii) Uit a + c(b# + #e) kan de # niet weggerekend worden: a + c(b# + #e) = a + cb#, en deze term kan niet verder vereenvoudigd worden. 5.7.2. DEFINITIE. (i) Een term die vereenvoudigd kan worden tot een term zonder #, heet deadlock-vrij. (ii) Een term die niet vereenvoudigd kan worden tot een term zonder #, heet bevat deadlock, of: heeft een deadlock-mogelijkheid. (iii) Als alle traces van een proces op # eindigen, zeggen we dat het proces altijd deadlockt. 5.7.3. DEFINITIE. De definitie van basis termen wordt nu iets uitgebreid: een basis term is een term die is opgebouwd uit atomen en # met ‘+’ en ‘.’. 5.7.1. OPGAVE. Welke van de volgende processen is deadlock-vrij? (i) ##+ # (ii) a# + # 1

Dit kan vergeleken worden met de 0 in rekenkunde, of met het complexe getal i. (Merk op dat de vergelijkingen voor # hetzelfde zijn als voor 0! Toch is voor # niet de notatie 0 gekozen, om historische redenen; toen # geïntroduceerd werd in procesalgebra had 0 al een andere betekenis. Bovendien speelt 0 in een andere versie van procesalgebra, Milner’s CCS, een andere rol.) Formele structuren - 2001

93


(iii) a(b + #) + #a. 5.8. Communicerende processen. We vervolgen nu met een uitbreiding van BPA met merge ||. De merge krijgt nu ook communicatie als ‘feature’. In het voorafgaande waren alle acties ‘gelijkberechtigd’, en onafhankelijk van elkaar. Maar procesalgebra krijgt zijn echte kracht pas, als we processen bekijken die met elkaar kunnen communiceren en samenwerken.We hebben dan te maken met interactie, of ook wel genoemd: reactieve processen. Het standaardvoorbeeld is dat van de koffiemachine M en een gebruiker G. 5.8.1. VOORBEELD. De koffiemachine M is gegeven als het volgende proces: M = accept_coin.(accept_coffee.give_coffee + accept_tea.give_tea). De betekenis van deze acties spreekt voor zich. Sommige acties zijn ‘passief’, bijvoorbeeld accept_coffee betekent dat de knop voor koffie wordt ingedrukt (en niet weigert). Een gebruiker G die koffie wil, is gegeven als G = insert_coin.push_coffee. Het is de bedoeling dat de acties insert_coin en accept_coin tegelijkertijd plaats vinden; het resultaat is dan de actie coin_falls.We schrijven dit met ‘|’ als volgt: insert_coin | accept_coin = coin_falls. De acties insert_coin en accept_coin heten communicatie-acties. Andere communicaties van acties in dit voorbeeld zijn: push_coffee | accept_coffee = coffee_accepted push_tea | accept_tea = tea_accepted. Communicatie-acties zijn als het ware ‘halve acties’; pas als de twee helften elkaar vinden in een communicatie, ontstaat een gewone, ‘hele’ actie. Ook in het dagelijks leven zijn hiervan veel voorbeelden, bijvoorbeeld de actie van het elkaar een hand geven. Ieder van de twee handgevers voert een halve actie uit, samen vormen die de hele actie van het handschudden. De Formele structuren - 2001

94


vorm van actie-communicatie die we nu bespreken, staat dan ook bekend als ‘hand-shaking’. In de informatica hebben we zulke halve acties bijvoorbeeld in de volgende situatie, bij de uitwisseling van data bij een poort. De acties send5(d) en receive5(d) (respectievelijk het uitzenden en ontvangen van datum d aan poort nummer 5), kunnen alleen tegelijkertijd worden uitgevoerd - en vormen dan samen de actie communicate5(d). De bedoeling is nu dat de samenwerking van M en G als resultaat oplevert: coin_falls.coffee_accepted.give_coffee.

M G K

T

$(G || M) Figuur 5.8.1

We voeren eerst een notatie in die het gemakkelijk maakt te onthouden wat de hele en de halve acties zijn. We hebben nu ‘hele’ acties die we met a, b, c,... zullen aangeven; en ‘halve’ acties c, c’, c*,... (communicatie-acties). Bij een halve actie c hoort zijn wederhelft (communicatiepartner) c*. Omgekeerd is c* de partner van c. Het resultaat van het gelijktijdig uitvoeren van c en zijn partner c* is c. Dit is weer een hele actie! We schrijven dit als: c | c* = c. We zullen steeds de notatie ‘*’ en onderlijning gebruiken voor zulke communicaties, bijvoorbeeld ook als er meer communicatieparen zijn zó: c1 | c1* = c1, enz. Dus:

c-actie | c-actie* = c-actie


95


Het volgende nieuwe element is dat de merge || iets anders wordt. Het proces x || y krijgt er nu een derde mogelijkheid bij. De merge x || y heeft nu niet alleen een linkerhelft x y en en rechterhelft y x , maar ook een derde mogelijkheid waarbij de eerste stap moet bestaan uit een gezamenlijke actie van x en y, dat wil zeggen, een communicatie tussen een eerste stap c van x en een eerste stap c* van y. In termen van transities hebben we nu de extra mogelijkheid:

c.x || c*.y !c x || y

5.8.2. VOORBEELD. We bepalen de procesgraaf van c.c* || c*.c.

c.c* || c*.c c

c c* || c

c* || c*.c c*

c c

c

c* || c

c*

c

c* c c c c

c.c* || c

c* c c

c*

c*.c

c*

c c*

c* c c c

c*

c.c*

c* || c

c*

c*

c

c

c c* c*

c* c*

Figuur 5.8.1

In deze procesgraaf zijn er takken waarin de halve acties c, c* gecommuniceerd hebben met resultaat c, maar er zijn ook takken waarin ze op zichzelf voorkomen zonder dat ze gecommuniceerd hebben. Maar het is de bedoeling bij het specificeren van processen met communicatie-acties, dat die communicaties niet alleen kunnen voorkomen, maar zelfs moeten voorkomen. Dit bereiken we door een schoonveegoperatie: alle halve acties die er na uitwerken zijn, worden verwijderd. De operatie die dit doet heet de restrictie-operator, genoteerd met $. Formele structuren - 2001

96


De werking van $ is als volgt. Eerst worden alle communicatie-acties c,c’, c*, c’*,... vervangen door #. Vervolgens worden de vergelijkingen x + # = # en #.x = # zo vaak als mogelijk toegepast, maar dan op de graaf. Preciezer: de graaf wordt opgeschoond op de volgende manier. 5.8.3. DEFINITIE. Gegeven is een procesgraaf (met #-stappen). Een knoop u heet onbereikbaar wegens deadlock als elk pad van de wortel naar u een #-pijl bevat. Twee verschillende pijlen w !a v en w’ !a’ v’ van g noemen we zusterpijlen als w = w’. (Dus de beginknopen van deze pijlen zijn hetzelfde.) Onder het #-opschonen van een procesgraaf verstaan we het volgende procede: 1. verwijder alle pijlen u !a v uit de graaf waarvoor geldt dat u onbereikbaar is wegens deadlock. 2. verwijder net zo lang #-pijlen totdat geen enkele pijl meer een #-zusterpijl heeft. Het resultaat van deze operatie noemen we het #-schone overblijfsel van g, notatie $(g). 5.8.4. VOORBEELD.Van de onderstaande graaf g levert dit het volgende resultaat $(g) op:

g

a

#

$(g)

b c e

a

b c

d Figuur 5.7.3

In Figuur 5.8.2 is de $ toegepast op de graaf in Figuur 5.8.1. De gearceerde delen worden verwijderd, en wat overblijft is de procesgraaf van $(c.c* || c*.c). Dit blijkt te zijn c.c. Dit is inderdaad het intuïtief verwachte resultaat.


97


$

c.c* || c*.c

c

c c* || c

c* || c*.c c*

c c

c

c* || c

c*

c

c* c c c c

c.c* || c

c* c c

c*

c*.c

c*

c c*

c

c* c c c

c*

c.c*

c* || c

c*

c*

c

c

c* c*

c* c*

Figuur 5.8.2

5.8.1. OPGAVE. Werk het proces $(K || G) uit.

We besluiten met enkele voorbeelden die duidelijk maken hoe deadlock door communicatie kan ontstaan als ‘processen op elkaar staan te wachten’. 5.8.5. VOORBEELD. Gegeven zijn processen A en B. De communicatieparen zijn (ten overvloede) aangegeven met dikke gearceerde lijnen. Intuitief verwachten we (maar we rekenen het niet na): $(A ||B) = (a1.a2 || b1.b2). c1. (a3.a4 || b3.b4). c2. (a5.a6 || b5.b6). A=

a1. a 2. c1. a3. a 4. c2. a5. a 6

B=

b1. b2. c1*. b3. b4. c 2*. b5. b6 Formele structuren - 2001

98


Wanneer we B wijzigen in B’ door de communicatie-acties om te draaien, krijgen we deadlock: $(A ||B’) = (a1.a2 || b1.b2). #.

A=

a1. a 2. c1. a3. a 4. c2. a5. a 6

B' =

b1. b2. c2*. b3. b4. c 1*. b5. b6

5.8.6. VOORBEELD. Nu twee oneindige processen, bestaande uit 3 componenten X, Y, Z, elk door één vergelijking recursief gedefinieerd: X = a. c1. a c2. a. X Y = b. c*1.

b c3. b. Y

Z = d. c*3. d c* 2. d. Z Hier krijgen we een deadlock-vrij oneindig proces. 5.8.2. OPGAVE. Geef een oneindig trace van dit proces.

X = a. c1. a c2. a. X Y = b. c3.

b c*1. b. Y

Z = d. c*2. d c* 3. d. Z Maar dit proces dealockt altijd! 5.8.3. OPGAVE. Geef een deadlockend trace van dit proces.


99


* 5 . 9 . ACP, Algebra van Communicerende Processen. Deze extra sectie is alleen bedoeld om eens door te kijken, voor wie het interessant vind eens te zien hoe al het bovenstaande ook puur algebraisch gedaan kan worden. Het is nu nog maar een kleine stap om wat we boven met procesgrafen gedaan hebben, algebraïsch te maken net zoals in Hoofdstuk 5, de axioma’s voor || en . Het eerste nieuwe element is de introductie van een bijzondere actie, de ‘onmogelijke actie’ #. Deze actie voldoet aan de volgende twee vergelijkingen:

●

deadlock x +# = x #.x = # Tabel5.9.1

Het volgende nieuwe element is dat de acties nu onderverdeeld zijn in ‘gewone acties’, die we met a, b, c,... zullen aangeven; en communicatie-acties c, c’, c*,... Bij een communicatie-actie c hoort zijn communicatie-partner c*. Omgekeerd is c* de partner van c. Het resultaat van het gelijktijdig uitvoeren van c en zijn partner c* is c. Dit is weer een gewone actie! We schrijven dit als: ●

c | c* = c. We zullen steeds de notatie ‘*’ en onderlijning gebruiken voor zulke communicaties, bijvoorbeeld ook als er meer communicatieparen zijn zó: c1 | c1* = c1, enz. Dus:

c-actie | c-actie* = c-actie

(Als we eenmaal vertrouwd zijn met ACP, hoeven we deze notatie-conventie niet langer gebruiken.) Het volgende nieuwe element is dat de merge || iets anders wordt. Het proces x || y krijgt er een derde deel bij . De merge x || y heeft nu niet alleen een linkerhelft x y en en rechterhelft ●


100


y x , maar ook een ‘midden’, x | y. Dit is x || y waarbij de eerste stap moet bestaan uit een gezamenlijke actie van x en y, dat wil zeggen, een communicatie tussen een eerste stap c van x en een eerste stap c* van y. We noemen x | y de “communicatie-merge van x en y”. De axioma’s voor blijven zoals ze waren. Dus we hebben de axioma’s als in Tabel 5.9.1:

merge x || y = x y + y x + x|y a x = a.x ax y = a(x || y) (x + y) z = x z + y z

Tabel 5.9.2

De communicatie-merge x | y wordt als volgt uitgerekend; zie Tabel 5.9.3. Het eerste axioma (cx)|(c*y) = c(x || y) is boven verklaard. De twee volgende, (cx)|c* = c.x en c|(c*y) = c.y, zijn de gevallen waarbij de y of de x er niet is. Het axioma ax|by = #, betreft een mislukte ●

communicatie (cx)|(c*y) = c(x || y) (cx)|c* = c.x c|(c*y) = c.y ax|by = # ax|b = # a|by = # (x + y)|z = x|z + y|z x|(y + z) = x|y + x|z

Tabel 5.9.3

communicatie: a en b zijn gewone acties, dus geen communicatie-partners; dus het resultaat is #, de onmogelijke actie.De axioma’s ax|b = # en a|by = # zijn weer voor de gevallen dat y of x er niet is. De laatste twee, (x + y)|z = x|z + y| en x|(y + z) = x|y + x|z, zeggen hoe sommen worden uitgerekend.


101

Hoofdstuk 5 - Rekenen met processen ●

De restrictie-operator $:

restrictie $(c) = $(c*) = $(#) = # $(a) = a $(x + y) = $ (x) + $(y) $(x . y) = $ (x) . $(y)

Tabel 5.9.4

Het totale axiomasysteem wordt daarmee:

basis proces algebra

communicatie

x+y=y+x x + (y + z) = (x + y) + z x+x=x (x + y) .z = x.z + y.z x.(y.z) = (x.y).z

(cx)|(c*y) = c(x || y) (cx)|c* = c.x c|(c*y) = c.y ax|by = # ax|b = # a|by = # (x + y)|z = x|z + y|z x|(y + z) = x|y + x|z

deadlock x +# = x #.x = #

restrictie

merge x || y = x y + y x + x|y a x = a.x ax y = a(x || y) (x + y) z = x z + y z

$(c) = $(c*) = $(#) = # $(a) = a $(x + y) = $ (x) + $(y) $(x . y) = $ (x) . $(y)

Tabel 5.9.5: ACP

5.9.1. OPMERKING. ACP is een heel sterk ‘specificatiemechanisme: alle Turing Machines kunnen erin geïmplementeerd worden. Alle berekenbare functies kunnen dus ook met ACP verkregen worden! Formele structuren - 2001


102

5.9.1. OPGAVE. Bewijs: $((a + c) || (b + c*)) = (a || b) +c. 5.9.2. OPGAVE. (i) Bereken: $(ac1.c2 || c1*.c2*) (ii) Bereken: $(ac1.c2 || c2*.c1*) 5.9.3. OPGAVE. Bepaal, zonder het expliciet uit te rekenen, de basis term waaraan de volgende term gelijk is:

$((a + c1(d + c2(e + c3))) || c1*.c2*.c3*) *5.9.4. OPGAVE. (i) Bewijs: $[c(c1 + c2) || c*.c1*] = c.c1* (ii) Bewijs: $[c.c1 + c.c2 || c*.c1*] = c.c1* + c.#. (iii) Concludeer dat in de context $[N || c*.c1*] (d.i. een term met een open plaats ) de processen c(c1 + c2) en c.c1 + c.c2 een essentiëel verschillend resultaat opleveren: het eerste geeft c.c1*, dus een deadlock-vrij proces; het tweede geeft c.c1* + c.#, dus een proces met deadlock-mogelijkheid. Als we dus een procestheorie willen hebben, die deadlock-gedrag ‘respecteert’ (dat wil zeggen, niet twee processen gelijk stelt die verschillend deadlock-gedrag hebben), dan mogen we niet de vergelijking c(c1 + c2) = c.c1 + c.c2 hebben. daarom bevat BPA in Tabel 5.1.1 niet de vergelijking z(x + y) = zx + zy!


105

Hoofdstuk 6 - Termen en vergelijkingen

6 Termen en vergelijkingen Korte inhoud. In dit hoofdstuk geven we een korte inleiding in het rekenen met termen, door middel van termherschrijfsystemen. Termen kunnen zowel eindig als oneindig zijn. Termherschrijfsystemen vormen het fundament van ‘functioneel programmeren’.

6.1. Eindige termen. In Hoofdstuk 4 hebben we gezien hoe alles wat met een computer geprogrammeerd kan worden, al op een Turing machine geprogrammeerd kan worden. Met andere woorden, elke berekenbare functie kan met een Turing machine programma verkregen worden. In de praktijk zijn Turing machines niet handig, en kiezen we voor andere methoden. Eén van die methoden wordt gegeven door termen en vergelijkingen. In Hoofdstuk 4 hebben we gezien hoe de optelling op natuurlijke getallen met een Tu machine gedaan kan worden. We bekijken nu hoe dat gaat met termen en vergelijkingen; ook vermenigvuldiging doen we tegelijk erbij. Om te beginnen: de optelling ‘+’ en de vermenigvuldiging ‘x’wordt vastgelegd door de vergelijkingen in Tabel 6.1. Hierbij zijn + en x in ‘infix-notatie’ geschreven, dat wil zeggen, tussen hun argumenten. De standaardnotatie voor termen is anders; de operatoren worden dan vóór hun argumenten geschreven. Tabel 6.2 bevat dezelfde vergelijkingen, maar nu in standaardnotatie; verder staat A (addition) voor + en M (multiplication) voor x. De operatie “+1” is genoteerd met S (successor). De natuurlijke getallen, 0, 1, 2, 3, ... worden nu weergegeven door de termen 0, S(0), S(S(0)), S(S(S(0))), ...

e1 e2 e3 e4

x+0 =x x+ (y + 1) = (x + y) + 1 xx0=0 x x (y + 1) = (x x y) + x Tabel 6.1


106


e’1 e’2 e’3 e’4

A(x,0) = x A(x,S(y)) = S(A(x,y)) M(x,0) = 0 M(x,S(y)) = A(M(x,y),x) Tabel 6.2

Het alphabet of signatuur van de termen die we nu bekijken is dus ! = {A, M, S, 0}. Elk van deze operatoren of functie-symbolen heeft een ariteit, dit is het getal dat aangeeft wat het aantal argumenten is van die operator. Zo hebben A en M ariteit 2, S, heeft ariteit 1, en 0 heeft ariteit 0. We zeggen ook dat A en M binair zijn, S unair is, en 0 een constante. Standaard zijn er altijd variabelen x, y, z,... aanwezig. We kunnen nu de verzamelingen termen ‘over’ deze signatuur ! definiëren: 6.1.1. DEFINITIE. De verzameling van termen ‘over’ !, Ter(!), is als volgt inductief gedefiniëerd: (i) (ii)

x, y, z,... " Ter(!), als F een n-air functiesymbool is en t1, ..., tn " Ter(!) (n # 0), dan F(t1, ..., tn) " Ter(!). De ti (i = 1,...,n) heten de argumenten van de term F(t1,...,tn).

Vaak geven we in plaats van een term zijn termboom. Figuur 6.2 geeft de termboom van de term S(A(M(S(0), 0), 0)).


107


S

A

M

S

0

0

0

Figuur 6.2

6.1.2. DEFINITIE. Een vergelijking is een uitdrukking t = s, met t en s termen, zoals in Tabel 6.2. Meestal worden vergelijkingen zoals in Tabel 6.2. in een bepaalde richting gebruikt, namelijk van links naar rechts. Dat wil zeggen dat we in een grotere term een deelterm die de vorm heeft van de linkerkant van een vergelijking, mogen vervangen door de overeenkomstige rechterkant. Om die richting aan te geven, schrijven we de vergelijkingen met een ‘$’ zoals in Tabel 6.3. Dit is daarmee een ‘termherschrijfsysteem’ geworden, afkorting: TRS (term rewriting system).

r1 r2 r3 r4

A(x,0) $ x A(x,S(y)) $ S(A(x,y)) M(x,0) $ 0 M(x,S(y)) $ A(M(x,y),x) Tabel 6.3

6.1.3. DEFINITIE. ● Als we 0 of meer $-stappen achter elkaar doen, wordt dit met aangegeven. Dus als t $... $ s, schrijven we t s. ● De subterm die in een reductiestap wordt herschreven, heet een redex. (Dit is een afkorting van ‘reducible expression’.) Formele structuren - 2001

108


6.1.4. VOORBEELD. M(S(S(0)), S(S(0))) hebben:

S(S(S(S(0)))), omdat we de volgende reductierij

M(S(S(0)),S(S(0))) $ A(M(S(S(0)),S(0)),S(S(0))) $ S( A(M(S(S(0)),S(0)),S(0)) ) $ S( S( A(M(S(S(0)),S(0)),0) ) ) $ S( S( M(S(S(0)),S(0)) ) ) $ S(S(A(M(S(S(0)),0),S(S(0))))) $ S(S(A(0,S(S(0))))) $ S(S(S(A ( 0 , S ( 0 ) )))) $ S(S(S(S(A ( 0 , 0 ))))) $ S(S(S(S(0)))). Hier is in elke stap het dikgedrukte redex herschreven. Merk op dat dit niet de enige reductie is van M(S(S(0)), S(S(0))) naar S(S(S(S(0)))). 6.1.5. DEFINITIE. ● Een term die niet verder gereduceerd kan worden (die dus geen redex bevat), heet een normaalvorm. In bovenstaand voorbeeld is de term M(S(S(0)), S(S(0))) dus gereduceerd naar de normaalvorm S(S(S(S(0)))). ● We zeggen dat een term een normaalvorm heeft, als hij er naar toe reduceert. 6.1.6. VOORBEELD. In dit voorbeeld laten we alle mogelijke reductiestappen zien uitgaande van de term M(S(0), S(0)), naar zijn normaalvorm S(0). We krijgen dan de reductiegraaf van M(S(0), S(0)).


109


M(S(0), S(0))

A(M(S(0), 0), S(0))

A(0, S(0))

S(A(M(S(0), 0)), 0))

S(A(0, 0))

S(M(S (0), 0))

S(0)

Figuur 6.1: Reductiegraaf van M(S(0), S(0))

6.1. OPGAVE. Vul de TRS voor + en x in Tabel 6.3 aan met twee herschrijfregels voor exponentiatie (het rekenen met exponenten). 6.2. OPGAVE. Bepaal de reductiegraaf van M(S(0, S(S(0))).

6.1.6. VOORBEELD. Reductiegrafen kunnen ook cykels bevatten. Voeg aan de TRS van Tabel 6.3 de volgende regel toe: A(x, y) $ A(y, x); dus deze extra regel drukt de commutativiteit van de optelling uit. Van de TRS in Tabel 6.3 kan bewezen worden dat elke term een normaalvorm heeft; voor de TRS met deze extra regel is dat niet meer zo. Figuur 6.2 bevat de reductiegraaf van de term A(0, S(0)). 6.3. OPGAVE. Geef een term in de uitgebreide TRS van Voorbeeld 6.1.6 die geen normaalvorm heeft.


110


A(0, S(0))

A(S(0), 0)

S(A(0, 0))

S(0)

Figuur 6.2

6.1.6. VOORBEELD. Ackermann’s functie. Ackermann’s functie is een mooi voorbeeld van een zeer sterk stijgende functie. Voor wetenswaardigheden over deze ‘killer’ functie, zie de webpages op: www.ifs.tuwien.ac.at/~kosara/ackermann.html. De definitie van deze functie staat in Tabel 6.4. In het TRS formalisme kunnen we die definitie eleganter weergeven, zoals in Tabel 6.5 gedaan is. De condities uit Tabel 6.4 hebben nu plaats gemaakt voor ‘pattern matching’.

f(m, n) = n + 1 f(m - 1, 1) f(m - 1, f(m, n - 1))

als m = 0 als m > 0 en n = 0 als m,n > 0

Tabel 6.4 Ackermann’s functie

Ack(0,x)

$

S(x)

Ack(S(x), 0)

$

Ack(x, S(0))

Ack(S(x), S(y)) $

Ack(x, Ack(S(x),y))

Tabel 6.5: TRS voor Ackermann’s functie 6.3.

OPGAVE. Bereken Ack(S(S(0)), S(S(0))).

*6.4. OPGAVE. Bereken Ack(S(S(S(0))), S(S(S(0)))). 6.5.

OPGAVE. Geef een TRS die de faculteitsfunctie n! (in woorden: n-faculteit) berekent. Die is zo gedefiniëerd: 0! = 1, (n + 1)! = (n+1). n! Formele structuren - 2001

111


6.1.6. VOORBEELD. In dit voorbeeld laten we zien hoe met een TRS het maximum van twee natuurlijke getallen kan worden berekend. Hierbij is A de optelling zoals in Tabel 6.3.

max(x, y) $ aux(x, y, 0) aux(S(x), S(y), z) $ aux(x, y, S(z)) aux(S(x), 0, z) $ A(S(x), z) aux(0, S(x), z) $ A(S(x), z) aux(0, 0, z) $ z Tabel 6.6 6.6. OPGAVE.

Bereken de normaalvorm van max(S(S(S(S(S(0))))), S(S(S(0)))).

6.7. OPGAVE. Geef een TRS die het minimum van twee natuurlijke getallen berekent.

6.2. Oneindige termen. In het voorgaande hebben we alleen naar eindige termen gekeken. Maar we kunnen ook heel goed met oneindige termen werken. Oneindige termen komen veel voor bij functioneel programmeren, bijvoorbeeld in de vorm van oneindige rijen natuurlijke getallen (‘streams’) , of oneindige bomen. We geven nu aan hoe oneindige termen op natuurlijke wijze ontstaan, uit het ‘framework’ dat we al hebben voor de eindige termen. Bekijk bijvoorbeeld de reductieregel F(x) $ P(x, F(S(x)). Neem als start-term F(0), en pas de regel herhaald toe, zodat de termen in Figuur 6.4 verkregen worden. Duidelijk is te zien dat deze rij termen steeds dichter nadert naar een oneindige limietterm, de meest rechtse in de figuur. De oneindigheid is hier gesuggereerd door de grijze lijntjes. De functie P staat voor Paring. (Notatie: functionele programmeertalen schrijven meestal x:y in plaats van P(x, y), met de infix-operator “: “).We kunnen de limiet-term dus zien als de ‘ paring’ van de natuurlijke getallen. Zo’n geïtereerde paring wordt gebruikt om Formele structuren - 2001

112


oneindige rijen (streams) te maken. De limiet-term in figuur 6.4 is dus eenvoudig de rij van natuurlijke getallen, als oneindige term geschreven. We voeren nu ‘oneindig termherschrijven’ in als uitbreiding van de gewone versie, door deze oneindige limiet-termen toe te laten als resultaat van een oneindige rij reductiestappen. Merk op dat de begrippen redex, reductiestap, normaalvorm precies hetzelfde zijn bij oneindige termen als bij eindige.

F(0)

.....

P 0

P 0

F

P

S

S

0

0

P S

P

S 0 Figuur 6.4

6.2.1. VOORBEELD. We willen de oneindige rij van 0-en krijgen. Laten we dit object aanduiden als ‘zeros’. Dan kunnen we ones als volgt definiëren: zeros = 0: zeros. We kunnen deze recursieve definitie ook als herschrijfregel opvatten: zeros $ 0: zeros Het bedoelde object is dan de ‘oneindige normaalvorm’ van ones: zeros $ 0: zeros $ 0:0: zeros $ 0:0:0: zeros $... $ 0:0:0:0:0:... 6.2.2. VOORBEELD. Om de rij natuurlijke getallen te krijgen (dus 0:S(0):S(S(0)):S(S(S(0))):...) gaan we als volgt te werk. Eerst stellen we de volgende reductieregel op: nats(x) $ x: nats(S(x) Formele structuren - 2001

113


Nu geeft nats(x) de rij natuurlijke getallen vanaf x, dus x:S(x):S(S(x)):... En nats(0) geeft nu de rij natuurlijke getallen. 6.2.3. VOORBEELD. De rij van Fibonacci-getallen is 0, 1, 1, 2, 3, 5.... we willen deze rij als oneindige term krijgen, dus als 0:S(0):S(0):S(S(0)):.... Neem de reductieregel fib(x, y) $ A(x,y) : fib(y, A(x,y)) (A is weer de optelling.) En nu is de oneindige normaalvorm van 0:S(0):fib(0, S(0)) de rij Fibonacci-getallen. 6.3. OPGAVE. Geef het beginstuk van de reductie van 0:S(0):fib(0, S(0)).

*6.2.4. VOORBEELD. De rij priemgetallen. We geven nu een voorbeeld van een mooie TRS die de rij van priemgetallen 2,3,5,7,11,13,... berekent als oneindige normaalvorm. filter(x:y, 0, m) $ 0:filter(y, m, m) filter(x:y, S(n), m) $ x:filter(y, n,m) sieve(0:y) $ sieve(y) sieve(S(n):y) $ S(n):sieve(filter(y, n, n)) nats(n) $ n:nats(S(n)) primes $ sieve(nats(S(S(0))) 6.4. OPGAVE. Reduceer primes tot de eerste priemgetallen zichtbaar worden.

6.2.5. NOTATIE. Beneden zullen we in plaats van de TRS reprentatie van natuurlijke getallen 0, S(0), S(S(0)),... gemakshalve schrijven 0,1,2,3,... Deze symbolen moeten dan gezien worden als afkortingen voor de officiele termen. *6.5. OPGAVE. Definiëer met een TRS een operator ‘search’ die als input streams natuurlijke getallen krijgt, en als output geeft: het nummer van de plaats in de rij waar voor het eerst een 0 optreedt, als die er is. Dus Formele structuren - 2001

114

Hoofdstuk 6 - Termen en vergelijkingen bijvoorbeeld search (7,6,3,8,0,7,7,7,...) = 5.

6.6. OPGAVE. Geef een TRS met een operator square die de elementen van een stream natuurlijke getallen kwadrateert. Dus bijvoorbeeld square (2,3,5,8,...) = 4,9,25,64,... 6.7. OPGAVE. Geef een TRS met een binaire operator plus die van twee streams natuurlijke getallen de elementen coördinaatsgewijs optelt. Dus bijvoorbeeld plus ((1,2,3,6....), (3,3,8,9....) = 4,5,11,15,...

6.3. Confluentie. In Figuur 6.1 hebben we gezien dat er vaak verschillende manieren zijn om een term naar zijn normaalvorm te reduceren. Dat doet de vraag rijzen of die normaalvorm (die het ‘antwoord’ is van de berekening) wel onafhankelijk is van de gevolgde reductie (berekening). Het zou zeer onprettig zijn als bijvoorbeeld de TRS voor A en M verschillende normaalvormen gaf bij een term. Plus en maal zouden dan niet goed gedefinieerd zijn, met rampzalige gevolgen. Wat we moeten hebben is de eigenschap van unieke normaalvormen: als een term t reduceert naar twee normaalvormen t1 en t2, dan moeten t1 en t2 hetzelfde zijn. We korten deze eigenschap af met UN. Gelukkig heeft de TRS voor A en M de eigenschap UN. De eigenschap UN is zelf een gevolg van een ‘diepere’ eigenschap die confluentie heet, en wordt afgekort als CR (naar de ontdekkers, Church en Rosser). De C R eigenschap is uitgebeeld in Figuur 6.5, die het volgende zegt: Als een term t1 op verschillende manieren gereduceerd kan worden naar twee termen t2 en t3, dan is er altijd een mogelijkheid om deze reducties voort te zetten tot ze weer bij elkaar komen (in een term t4.) De reducties die eerst uiteenliepen, vloeien dus weer samen, vandaar de naam confluentie.

t1

als t2

t

dan t

Figuur 6.5 Formele structuren - 2001

115


Dat UN inderdaad uit CR volgt, is gemakkelijk te zien. Stel namelijk dat een term t1 reduceert naar normaalvormen t2 en t3. Die zouden dus om UN te hebben, hetzelfde moeten zijn. Als we CR weten, is dit ook zo. Want dan kunnen we de reducties weer samen laten komen door middel van vervolgreducties van 0 of meer stappen. Maar omdat t2 en t3 normaalvormen zijn (vanwaar dus geen stap meer mogelijk is) moeten dat 0 stappen zijn. Dat kan alleen als t2 en t3 hetzelfde zijn! Dus hebben we UN. De vraag is nu dus: hoe kunnen we zien of een TRS confluent is? Hier is een vrij eenvoudig criterium voor, dat uit twee delen bestaat: (1) (2)

in de linkerkant van een reductieregel mag een variabele niet dubbel voorkomen; de patronen van de reductieregels mogen elkaar niet overlappen.

Als een TRS deze twee eigenschappen heeft, heet hij orthogonaal. Een hoofdstelling van termherschrijven is dat elke orthogonale TRS confluent is, dus ook de eigenschap UN heeft. En ook voor het geval van oneindig termherschrijven zegt een hoofdstelling dat orthogonale TRsen de eigenschap UN hebben. (In dat geval mogen normaalvormen oneindig zijn, zoals bijvoorbeeld de stream Fibonacci-getallen.) Eis (1) van orthogonaliteit is met één oogopslag te verifiëren. Eis (2) behoeft nadere toelichting. Het patroon van een reductieregel wordt als volgt verkregen: teken de termboom van de linkerkant van de regel; ● laat de variabelen weg. ●

Eis (2), geen overlap tussen de patronen, kan eenvoudig geïllustreerd worden met behulp van slides (transparencies) die bij een overhead-projector gebruikt worden, als volgt: Teken de twee patronen waarvan we willen testen of ze elkaar kunnen overlappen, elk op een slide. ● Probeer door de twee slides over elkaar heen te schuiven, een overlap tot stand te brengen. Lukt dat dan hebben we een paar overlappende patronen, anders is er geen overlap tussen deze twee patronen. ●

6.3.1. VOORBEELD. Zie Figuur 6.6.


116


F

H

C

H

0

L

L

1

slide 1

slide 2 F

H

C

overlap 0

L

1

Figuur 6.6

6.3.2. VOORBEELD. Gegeven is de TRS met regels als in Tabel 6.7. Dan is het patroon van de eerste regel als afgebeeld in Figuur 6.8 (het gearceerde deel).

r1 r2 r3

F(G(x, S(0)), y, H(z)) $ x G(x, S(S(0))) $0 P(G(x, S(0))) $ S(0) Tabel 6.7

6.8. OPGAVE. Teken ook de patronen van de andere twee regels in Tabel 6.9. Formele structuren - 2001

117


De TRS in Tabel 6.9 heeft inderdaad eigenschap (1). Maar ook eigenschap (2), want de drie patronen van de reductieregels kunnen elkaar niet overlappen. Figuur 6.9 bevat een term van deze TRS die een aantal keren de drie patronen bevat; inderdaad overlappen die elkaar niet. Het is niet moeilijk te zien dat geen enkele term in deze TRS twee van de drie patronen kan bevatten zodat die elkaar overlappen. Dus deze TRS is orthogonaal, en daarmee ook CR en daarmee ook UN.

F G x

y

H

S

z

0

Figuur 6.8

F

G

G x

F

S S

G

0

F

S 0

H

0

0

0

P

S

P G

G 0

H

S

S

x

0

0

0

S 0

Figuur 6.9


118


6.3.2. VOORBEELD. Als contrast geven we nu enkele voorbeelden van TRS-en waarbij wel overlap optreedt. Zie Figuur 6.10. (a) (b) (c)

L(L(x)) $ H(x) F(0, x, y) $ 0 F(x, 1, y) $ 1 or(x, y) $ x or(x, y) $ y

L

or

F

L 0

1

y

x

y

L x (a)

(b)

(c)

Figuur 6.10

6.9. OPGAVE. Laat zien dat de AMS0 TRS in Tabel 6.3 orthogonaal is. 6.10. OPGAVE. (i) Teken de patronen van de reductieregels van de TRS voor de Ackermann functie, in Tabel 6.5. (ii) Laat zien dat de TRS voor de Ackermann functie orthogonaal is, en dus confluent.



119


No title

Recommend Documents