opgaven formele structuren deterministische eindige automaten

opgaven formele structuren ‘deterministische eindige automaten’ Opgave 1. De taal L over het alfabet {a, b} bestaat uit alle strings die beginnen met aa en eindigen met ab. Geef een reguliere expressie voor L. Uitwerking van opgave 1: Ook de string a a b zit in de taal ! De reguliere expressie waar het om gaat is a · a · (a + b)∗ · a · b + a · a · b. Opgave 2. Geef een deterministische eindige automaat voor de reguliere taal (1 + 01)∗ (0 + λ) (dus over het alfabet {0, 1}). Uitwerking van opgave 2: De taal weergegeven door de reguliere expressie (1 + 01)∗ (0 + λ) bestaat uit alle strings over het alfabet {0, 1} die geen substring 0 0 hebben. Een deterministische eindige automaat die deze taal herkent: 0, 1 

1  

  ? ?    1 - q0 q fout - 1 0   0    Opgave 3. Je hebt 100 sokken in een donkere kast; je hebt ze in vier kleuren: blauw, wit, rood en zwart. Je kunt ze niet zien maar wilt zeker weten dat je er twee van dezelfde kleur hebt. Hoeveel moet je er minstens pakken? Laat zien hoe je hier het PHP gebruikt. Uitwerking van opgave 3: Je moet tenminste 5 sokken pakken. Hier wordt het pigeon-hole principle gebruikt met de kleuren als holes en de sokken als pigeons. Er zijn 4 kleuren, dus als je meer dan 4 (dus tenminste 5) sokken hebt, hebben tenminste 2 sokken dezelfde kleur. Opgave 4. Hoeveel mensen moet je bij elkaar zetten om zeker te weten dat er twee op dezelfde dag van het jaar jarig zijn? Gebruik weer het PHP. Uitwerking van opgave 4: Je moet tenminste 367 mensen bij elkaar zetten. Hier wordt het pigeon-hole principle gebruikt met de dagen van het jaar als holes en de mensen als pigeons. Er zijn 366 dagen van het jaar (rekening houdend met schrikkeljaren), dus als er meer dan 366 (dus tenminste 367) mensen zijn, zijn er tenminste 2 op dezelfde dag jarig. Opgave 5. Geef een reguliere expressie voor de taal over het alfabet {0, 1} van alle strings waarin precies twee keer een 0 voorkomt (N.B. die twee 0’en hoeven niet achter elkaar voor te komen).

1

Geef ook een deterministische eindige automaat die die taal accepteert. Uitwerking van opgave 5: Een mogelijke reguliere expressie is: 1∗ 01∗ 01∗ . In een plaatje: 1  

1  

1  

0, 1 

    ? ? ? ?  0 0 0 - q0 - q1 - q2 - fout   Opgave 6.

Geef een DEA die twee binaire getallen a = an an−1 . . . a1 a0

en b = bn bn−1 . . . b1 b0 (met a ≥ b) aftrekt, d.w.z. op invoer a0 , b0 , a1 , b1 , . . . , an−1 , bn−1 , an , bn uitvoer c0 , c1 , . . . , cn−1 , cn geeft, met a − b = cn cn−1 . . . c1 c0 . Opgave 7.

Geef

• een reguliere expressie die de verzameling beschrijft, en • een DEA die de verzameling herkent voor elk van de volgende verzamelingen in de taal {0, 1}∗ : (a) de verzameling van alle strings die ten minste drie enen bevatten, (b) de verzameling van alle strings die drie opeenvolgende nullen bevatten, (c) de verzameling van alle strings die zowel twee opeenvolgende nullen als twee opeenvolgende enen bevatten. Uitwerking van opgave 7: (a) Een reguliere expressie die de verzameling van alle strings over {0, 1} met ten minste drie enen herkent: 0∗ · 1 · 0∗ · 1 · 0∗ · 1 · (0 + 1)∗ . Een dea die deze verzameling herkent:

2

0  

0  

0  

0, 1 

    ? ? ? ?  - q0 - q1 - q2 - q3 1 1 1   Opgave 8. Beargumenteer dat er voor elk van de volgende verzamelingen geen DEA bestaat die de verzameling herkent: (a) in de taal {0, 1}∗ : de verzameling {1n 01n | n ≥ 1}, (b) in de taal {0, 1}∗ : de verzameling {0n 1m | 0 ≤ n < m}, (c) in de taal {0, 1, 2}∗ : de verzameling {0n 1m 2n+m | n, m ≥ 1}. Uitwerking van opgave 8: (b) Stel er is een dea D die de taal L = {0n 1m | 0 ≤ n < m} herkent. Een dea heeft eindig veel toestanden, dus er zijn vanwege het PHP natuurlijke getallen p en q met p 6= q zodat de automaat na inlezen van 0p in dezelfde toestand, zeg Q, komt als na het inlezen van 0q . Stel dat p < q (dit is geen beperking van de algemeenheid). Omdat de dea de taal L herkent, en 0p 1q een element van L is, komt hij na vervolgens (vanuit Q) inlezen van 1q in een acceptatietoestand. Maar dat betekent dat de dea D ook de string 0q 1q accepteert: eerst brengt inlezen van 0q de dea in toestand Q, en vervolgens inlezen van 1q brengt de automaat in een acceptatietoestand. De string 0q 1q is geen element van de taal L. Dit is dus in tegenspraak met de aanname dat er een dea bestaat die L herkent. We concluderen dat er geen dea is die L herkent. Opgave 9.

Geef

• o `f een reguliere expressie die de verzameling beschrijft en een DEA die de verzameling herkent • ` of een argument waarom zo’n reguliere expressie en zo’n DEA niet bestaan voor elk van de volgende verzamelingen in de taal {0, 1}∗ : (a) de verzameling {0n 1 | n ≥ 0}, (b) de verzameling {0n 1m | n 6= m}, (c) de verzameling van alle niet-lege strings die 101 als substring bevatten, (d) de verzameling van alle strings waarvan het eerste en het laatstse symbool gelijk zijn, (e) de verzameling van alle niet-lege strings met evenveel nullen als enen, (f) de verzameling van alle niet-lege strings die 101 niet als substring bevatten. 3

Opgave 10. Geef een reguliere expressie voor de taal over het alfabet {0, 1} van alle strings waarin precies twee keer een 0 voorkomt (N.B. die twee 0’en hoeven niet achter elkaar voor te komen). Geef ook een deterministische eindige automaat die die taal accepteert. Uitwerking van opgave 10: Een mogelijke reguliere expressie is: 1∗ 01∗ 01∗ . In een plaatje: 1  

0, 1 

1  

1  

    ? ? ? ?  0 - q1 0 - q2 0- q0 fout    Opgave 11.

(uit tentamen 30 mei 2000)

(a) Geef een deterministische eindige automaat voor de taal 01(01)∗ over het alfabet {0, 1}. (b) Wat is het pigeon hole principle? Opgave 12.

(uit hertentamen 17 augustus 2000)

(a) Geef een deterministische eindige automaat voor de taal (01)∗ 1 over het alfabet {0, 1}. (b) Geef een voorbeeld van een taal die niet door een deterministische eindige automaat herkend kan worden. Uitwerking van opgave 12: (a) Een dea die de taal (01)∗ 1 herkent:

0, 1   ?   0, 1   6 6 1 0  1 0  

4

Opgave 13. Geef

(uit tentamen 30 maart 2001)

• o `f een reguliere expressie die de verzameling beschrijft en een DEA die de verzameling herkent • ` of een argument waarom zo’n reguliere expressie en zo’n DEA niet bestaan voor elk van de volgende verzamelingen in de taal {0, 1}∗ : (a) De verzameling van alle strings waarvan het eerste en het laatste symbool verschillend zijn. (b) {1n 02n | n ∈ N}. Uitwerking van opgave 13: (a) Een reguliere expressie: 0(0 + 1)∗ 1 + 1(0 + 1)∗ 0. Een DEA voor deze taal: 0 1   ?  0  ?  - n   1 0  1 0 @    1@  ?  1  ? R @ - n  0  (b) Stel er bestaat een DEA D die de taal bestaande uit alle strings van de vorm 0n 12n herkent. We bekijken om te beginnen de strings van de vorm 0n . Omdat er oneindig veel zulke strings zijn, en de DEA D eindig veel toestanden heeft, zijn er vanwege het PHP een k en een l met k 6= l zodat het inlezen van 0k en 0l je in dezelfde toestand, zeg q, brengt. Omdat D de taal accepteert moet je als je in q begint met het lezen van de string 12k in een acceptatietoestand komen. Maar dan brengt, beginnend in de begintoestand, het lezen van de string 0l 12k je ook in een acceptatietoestand. De string 0l 12k zit niet in de taal. Tegenspraak, dus zo’n DEA D kan niet bestaan. Opgave 14.

(uit hertentamen 17 augustus 2001)

(a) Construeer een eindige automaat voor de taal bestaande uit alle strings over {0, 1} waarvan het verschil tussen het aantal 1-en en het aantal 0-en deelbaar is door 2 (let op: ook 0 is deelbaar door 2). (b) Geef voor elk van de volgende talen aan of die kan worden herkend door een DEA. Alleen het antwoord volstaat. 5

(i) {0n 1m | n 6= m}, (ii) 1(00)(10)∗ , (iii) {1n | n is een macht van 2 }, (iv) De verzameling van alle strings over {0, 1} die 1100 als substring bevatten. Uitwerking van opgave 14: (a)

 0, 1  - n  0, 1  (b) (i)nee, (ii)ja, (iii)nee, (iv)ja. Opgave 15.

(uit tentamen 5 juni 2002)

(a) Geef een deterministische eindige automaat (DEA) voor de taal over {0, 1} bestaande uit alle strings waarin de string 110 niet als substring voorkomt. (b) Geef voor de volgende talen over het alfabet {0, 1} aan of ze regulier zijn. Ja/nee volstaat als antwoord. (i) De verzameling van alle strings die tweemaal zoveel 1-en als 0-en bevatten. (ii) De verzameling van alle strings waarvan het aantal 1-en twee meer is dan het aantal 0-en. (iii) 0∗ (11)∗ . (iv) De verzameling strings waarvan het eerste en het laatste symbool verschillen. (v) De verzameling strings die niet meer dan 1000 symbolen bevatten. (c) L1 en L2 zijn talen over Σ met L1 ⊆ L2 . Bewijs of weerleg (door een tegenvoorbeeld) de volgende bewering: als L2 regulier is, dan is L1 regulier. Uitwerking van opgave 15: (a) Een DEA die deze taal herkent:

6

0  

1  

0, 1 

  ? 0  ? ?     - q0 - q1 - q2 - q3 1 1 0        (b) (i) en (ii): nee. (iii),(iv) en (v): ja. (c) De bewering is niet waar. Neem voor L1 de taal {0n 1n | n ∈ N} en voor L2 de taal 0∗ 1∗ . Dan geldt L1 ⊆ L2 en L2 is regulier. Maar L1 is niet regulier. Opgave 16.

(uit hertentamen 16 augustus 2002)

(a) Geef een DEA voor de taal over {0, 1} bestaande uit alle strings waarin de string 101 als substring voorkomt. (b) Geef • of een reguliere expressie die de taal beschrijft • of een argument dat zo’n reguliere expressie niet bestaat voor de volgende talen over {a, b}. (i) De verzameling van alle strings waarvan het aantal b’s twee meer is dan het aantal a’s. (ii) De verzameling van alle strings waarvan het aantal a’s even is. (c) L1 en L2 zijn talen over een alfabet Σ met L1 ⊆ L2 . Bewijs of weerleg: Als L1 niet regulier is dan is L2 niet regulier. Uitwerking van opgave 16: (a) Een DEA die deze taal herkent:

0  

0, 1 

1  

   ? ? ?  - q2 - q3 - q1 - q0 1 0 1   6 0

7

(b) De verzameling X van alle strings waarvan het aantal a’s twee meer is dan het aantal b’s is geen reguliere taal. Stel dat er een DEA D is die deze verzameling herkent. We bekijken om te beginnen strings van de vorm an . Omdat er oneindig veel van zulke strings zijn en D maar eindig veel toestanden heeft, zijn er vanwege het PHP k en l met k 6= l zodat het inlezen van de string ak de automaat in dezelfde toestand, zeg q, brengt als het inlezen van al . Als er nu, beginnend in q, vervolgens de string bk+2 wordt gelezen, dan komt de automaat in een acceptatietoestand, want ak bk+2 zit in de verzameling X en de DEA herkent X. Maar dan brengt het inlezen van de string al bk+2 de automaat ook een in acceptatietoestand, terwijl al bk+2 niet in X zit. Dit is een tegenspraak met de aanname dat D de verzameling X herkent. Conclusie: er is geen DEA die X herkent. De verzameling van alle strings waarvan het aantal a’s even is wel regulier. Een reguliere expressie voor deze verzameling is (b + ab∗ a)∗ . Opgave 17.

(uit tentamen 26 maart 2003)

(a) Geef een deterministische eindige automaat (DEA) voor de taal over {0, 1} die bestaat uit alle strings die eindigen op 011. (b) Beschrijf de taal gevraagd in 3a ook door middel van een reguliere expressie. (c) Gegeven is een taal L over een alfabet S. We definieren de taal L0 door: L0 = S ∗ \L (dwz. L0 bestaat uit alle strings over S die niet tot L behoren.) Bewijs, of weerleg door een tegenvoorbeeld: Als L regulier is dan is ook L0 regulier. Opgave 18.

(uit hertentamen 15 augustus 2003)

(a) Geef een DEA voor de taal over {0, 1} die bestaat uit alle strings die de string 101 als substring bevatten. (b) Beschrijf de taal uit onderdeel (a) ook door een reguliere expressie. (c) Gegeven zijn twee talen L1 en L2 over een alfabet S. We defini¨eren een nieuwe taal L3 over S door L3 = L1 ∪ L2 . Bewijs, of weerleg door een tegenvoorbeeld: Als L1 en L2 regulier zijn dan is ook L3 regulier.

8

Opgave 19.

(uit tentamen 23 maart 2004)

a. Teken een deterministische eindige automaat (DEA) die de taal herkent bestaande uit alle strings over {0, 1} ter lengte kleiner dan vier. b. Geef een reguliere expressie die de taal uit 3a beschrijft. c. Geef een bewijs dat de volgende taal L niet kan worden beschreven met een reguliere expressie: L = {s ∈ {0, 1}∗ | het aantal 0-en in s is 5 groter dan het aantal 1-en} Uitwerking van opgave 19: a. 0, 1 ?      - n 0, 1- n 0, 1- n 0, 1- n 0, 1     b. λ + (0 + 1) + (0 + 1)(0 + 1) + (0 + 1)(0 + 1)(0 + 1). c. Stel dat er wel een reguliere expressie is die L beschrijft. Dan is er ook een DEA M die L herkent. Die DEA moet ook alle strings van de vorm 1n 0n+5 herkennen. We kijken eerst naar de strings van de vorm 1n . Er zijn oneindig veel van zulke strings. Omdat M maar eindig veel toestanden heeft, zijn er twee verschillende strings 1k and 1l met k 6= l die je in dezelfde toestand, zeg p, brengen. De string 1k 0k+5 zit in de taal, en vanuit p de string 0k+5 lezen moet je dus in een accepterende toestand, zeg q brengen. Maar dat betekent dat het lezen van de string 1l 0k+5 beginnend in de starttoestand je ook in een accepterende toestand brengt, terwijl die string niet in de taal L zit. Uit de aanname dat er een reguliere expressie is die L beschrijft volgt dus een tegenspraak. We concluderen dat die aanname niet waar is: er is dus geen reguliere expressie die L beschrijft. Opgave 20.

(uit hertentamen 29 juni 2004)

a. Teken een deterministische eindige automaat (DEA) die de taal herkent bestaande uit alle strings over {a, b, c} waarin een b niet direct op een a volgt. (Dat betekent dat er geen substring ab voorkomt.) b. Geef een reguliere expressie voor de taal bestaande uit alle strings over {a, b, c} waarin ab w´el als een substring voorkomt. c. Bewijs, of weerleg door een tegenvoorbeeld: als L1 en L2 reguliere talen zijn over hetzelfde alfabet, dan is ook L1 ∪ L2 regulier. 9

Opgave 21.

Geef

• o `f een reguliere expressie die de verzameling beschrijft en een DEA die de verzameling herkent • ` of een bewijs dat zo’n DEA niet bestaat voor elk van de volgende talen in {0, 1}∗ : a. de verzameling van alle strings ter lengte 2 of groter waarvan het tweede en het laatste symbool gelijk zijn; b. {w | w bevat meer 0en dan 1en}. Uitwerking van opgave 21: a. Een reguliere expressie voor de strings ter lengte 2 of meer waarbij het tweede en laatste symbool gelijk zijn: (0 + 1)0(0 + 1)∗ 0 + (0 + 1)1(0 + 1)∗ 1 + (0 + 1)(0 + 1) Een DEA die die taal herkent: 0 1   ?  0  ?  n  1 

0   0, 11 0 @     1@  ?  1  ? R n @  0  (Deze taal is dus regulier.)

b. De taal L = {w | w bevat meer 0en dan 1en} is niet regulier. Stel wel. Dan is er een DEA M die L herkent. Er zijn oneindig veel strings van de vorm 1p en M heeft slechts eindig veel toestanden. Daarom zijn er m en n met m < n zodat het lezen van de string 1m je in dezelfde toestand, zeg q, brengt als het lezen van de string 1n . De string 1m 0m+1 zit in L, want de string bevat meer 0en dan 1en. Omdat M de taal L herkent, moet het lezen van 1m 0m+1 je in een accepterende toestand brengen. Dus als je, beginnend in q, de string 0m+1 leest kom je in een accepterende toestand. Omdat het lezen van 1n je in q brengt, brengt het lezen van 1n 0m+1 je in een accepterende toestand. Maar deze string zit niet in L. Dus dit is een tegenspraak met de aanname dat M de taal L herkent. Conclusie: er bestaat geen DEA die L herkent, ofwel L is niet regulier.

10

Opgave 22. a. Teken een deterministische eindige automaat (DEA) die de taal herkent bestaande uit alle strings over {a, b, c} waarin een b niet direct op een a volgt. (Dat betekent dat er geen substring ab voorkomt.) b. Geef een reguliere expressie voor de taal bestaande uit alle strings over {a, b, c} waarin ab w´el als een substring voorkomt. c. Bewijs, of weerleg door een tegenvoorbeeld: als L1 en L2 reguliere talen zijn over hetzelfde alfabet, dan is ook L1 ∪ L2 regulier. Uitwerking van opgave 22: a. Een DEA voor de taal bestaande uit de strings waarin ab niet als substring voorkomt: a  

b, c  

a, b, c

   ? ? ?   c  - q0 q fout - 1 b a      b. Een reguliere expressie voor de taal bestaande uit alle strings waarin ab als substring voorkomt: (a + b + c)∗ ab(a + b + c)∗ . c. Stel dat L1 en L2 reguliere talen zijn. Dan is er een reguliere expressie, zeg r1 , voor L1 , en een reguliere expressie, zeg r2 , voor L2 . Dus: L1 = T (r1 ) en L2 = T (r2 ). Er geldt: L1 ∪ L2 = T (r1 ) ∪ T (r2 ) = T (r1 + r2 ). Met andere woorden: r1 + r2 is een reguliere expressie voor de taal L1 ∪ L2 , dus L1 ∪ L2 is regulier. Opgave 23. (a) Geef een DEA die de taal {0n 1m | n, m ∈ N} herkent. (b) Geef een reguliere expressie voor de taal bestaande uit alle strings die beginnen met 01 en eindigen op 10. (c) Beredeneer dat de taal bestaande uit alle strings waarin het aantal 0-en twee groter is dan het aantal 1-en niet regulier is. Uitwerking van opgave 23: (a)

11

0  

1  

0, 1 

   ? ? ?   - q0 - q1 - fout 1 0      (b) 01(0 + 1)∗ 10 + 010. (c) Stel dat de taal L bestaande uit alle strings over {0, 1} waarvoor geldt dat het aantal 0-en twee groter is dan het aantal 1-en wel regulier is. Dan is er een DEA M die L herkent. De DEA M accepteert in het bijzonder alle strings van de vorm 1n 0n+2 . We bekijken eerst de strings van de vorm 1n . Er zijn oneindig veel van zulke strings. Omdat M eindig veel toestanden heeft, zijn er p en q met p 6= q zodat het lezen van de string 1p je in dezelfde toestand, zeg t, brengt als het lezen van de string 1q . Omdat de string 1p 0p+2 in de taal L zit en de DEA M de taal L herkent, brengt het lezen van deze string je in een accepterende toestand. Dat betekent dat het lezen van 1q 0p+2 je, via t, in diezelfde accepterende toestand brengt. Maar de string 1q 0p+2 zit niet in de taal L. Dit is een tegenspraak met de aanname dat L regulier is. We concluderen dat L niet regulier is. Opgave 24. (a) Geef een reguliere expressie voor de taal bestaande uit alle strings over {0, 1} waarvan het tweede symbool een 0 is en het ´e´en-na-laatste symbool een 1. (b) Geef een DEA voor de taal die bestaat uit alle niet-lege strings over {0, 1} waarvan het eerste en het laatste symbool hetzelfde zijn. Uitwerking van opgave 24: (a) (0 + 1)0(0 + 1)∗ 1(0 + 1) + 10. (b) 0 1   ?  0  ?  n  1  0  1 0 @    1@  ? ?  1 R n @  0 

12

Opgave 25. Opgave 26. (a) Geef een reguliere expressie voor de taal bestaande uit alle strings over {0, 1} met een oneven aantal symbolen. Uitwerking van opgave 26: (a) (0 + 1)(00 + 01 + 10 + 11)∗ . We beschouwen talen over {0, 1}.

Opgave 27.

(a) Geef een DEA die de taal herkent bestaande uit alle niet-lege strings waarvan het eerste en het laatste symbool verschillen. (b) Geef een DEA voor de taal bestaande uit alle strings waarin 001 niet als substring voorkomt. (c) Geef een reguliere expressie voor de taal die bestaat uit alle strings die beginnen met 10 en eindigen op 01. (d) Geef een reguliere expressie voor de taal die bestaat uit alle strings met een even aantal symbolen. (e) Bewijs dat de taal {0p 1q | p < q} niet regulier is. Uitwerking van opgave 27: (a) Een DEA voor deze taal: 0 1   ?  0  ?  - n  1 

0  1 0 @    1@  ?  1  ? R @ - n  0  (b) Een DEA voor deze taal: 1  

0  

0, 1 

  ? 1  ? ?     q3 q0 q1 q2 0 0 1    

-

13

(c) 10(0 + 1)∗ 01 + 101 (d) (00 + 01 + 10 + 11)∗ (e) Stel er is een dea D die de taal L = {0p 1q | p < q} herkent. Een dea heeft eindig veel toestanden, dus er zijn vanwege het PHP natuurlijke getallen k en l met k 6= l zodat de automaat na inlezen van 0k in dezelfde toestand, zeg Q, komt als na het inlezen van 0l . Stel dat k < l (dit is geen beperking van de algemeenheid). Omdat de dea de taal L herkent, en 0k 1l een element van L is, komt hij na vervolgens (vanuit Q) inlezen van 1l in een acceptatietoestand. Maar dat betekent dat de dea D ook de string 0l 1l accepteert: eerst brengt inlezen van 0l de dea in toestand Q, en vervolgens inlezen van 1l brengt de automaat in een acceptatietoestand. De string 0l 1l is geen element van de taal L. Dit is dus in tegenspraak met de aanname dat er een dea bestaat die L herkent. We concluderen dat er geen dea is die L herkent.

14