Inhoud eindtoets
Eindtoets Introductie 2 Opgaven 3 Terugkoppeling 6
1
Formele talen en automaten
Eindtoets I N T R O D U C T I E
Toegestane hulpmiddelen
Tentamenduur
Samenstelling
Terugkoppeling
Beoordeling
2
Deze eindtoets is bedoeld als voorbereiding op het tentamen van de cursus Formele talen en automaten en is te beschouwen als proeftentamen. Het is belangrijk dat u de eindtoets pas probeert te maken op het moment dat u denkt klaar te zijn met de tentamenvoorbereiding. Hebt u over dat laatste nog twijfels, bekijk dan nog eens de leerdoelen om te ontdekken welke onderdelen u nog onvoldoende beheerst. Bij het tentamen mag u het gedrukte cursusmateriaal, dat wil zeggen het tekstboek en het werkboek, raadplegen. Het cursusmateriaal dient schoon te zijn. Een tentamen duurt drie uur. We adviseren u dan ook de eindtoets binnen een aaneengesloten periode van drie uur te maken. Het aantal opgaven van deze eindtoets, de moeilijkheidsgraad en de verdeling van de opgaven over de leerstof komen overeen met het tentamen. Het tentamen bestaat uit vijf open vragen, soms onderverdeeld in deelvragen. De antwoorden op de opgaven staan in de terugkoppeling. We willen echter benadrukken dat u het meest leert als u eerst de opgaven maakt en pas daarna de antwoorden controleert. Het aantal punten dat u per opgave en per deelvraag kunt behalen, staat bij de opgave vermeld. U kunt in totaal maximaal 100 punten halen. Voor een voldoende voor het tentamen moet u tenminste 55 punten behalen. Het is niet zo dat u óf het volle aantal óf nul punten voor een onderdeel krijgt; als u een deel van de oplossing goed hebt kunt u ook een deel van de punten krijgen. Studeeraanwijzingen De studielast van deze eindtoets bedraagt circa 4 uur, inclusief het nakijken van de opgaven aan de hand van de terugkoppeling.
OUN
25 punten
Eindtoets
13 punten
Opgaven OPGAVE 1 Gegeven is de volgende taal: L = {x {a, b}* : x bevat tenminste één a en een even aantal bʹs} 1a Construeer een rechtslineaire grammatica G die het complement van L genereert, dus L(G) = {a, b}* – L. Beschrijf daarbij kort welke oplossingsmethode u gebruikt.
12 punten
1b Construeer een reguliere expressie voor de taal L. Beschrijf ook hier kort welke oplossingsmethode u gebruikt.
10 punten
20 punten
OPGAVE 2
Gegeven is de volgende taal L over het alfabet {i, +, =}: L = {in + ip = in+p : n, p 1} De taal L bevat dus strings als i + i = ii, iii + ii = iiiii, maar niet de string i + i = iii. Merk op dat spaties niet tot het alfabet horen. Ze zijn hier alleen voor de leesbaarheid toegevoegd. Toon met behulp van het pomplemma voor reguliere talen aan dat L niet regulier is. OPGAVE 3 Gegeven is de taal L van opgave 2.
10 punten 10 punten
20 punten
3a Geef een context‐vrije grammatica G voor L. 3b Geef een (niet‐deterministische) stapelautomaat (npda) M met L(M) = L(G) = L. Leg daarbij uit wat de functie van de verschillende toestanden is. OPGAVE 4 Gegeven is de taal L over het alfabet {a, b} bestaande uit alle strings met een prefix van de vorm anbn, waarbij n 1, en een suffix ambm, waarbij m 1. NB De strings abbabab en aabb behoren beide tot de taal. Bij de eerste string hebben n en m beide de waarde 1 en bij de tweede string vallen prefix en suffix samen (n en m hebben de waarde 2).
OUN
3
Formele talen en automaten
10 punten
10 punten
25 punten
4 punten
4a De taal Lʹ = {anbn : n 1} is context‐vrij. Druk L uit in termen van Lʹ en {a, b}*. 4b Is L context‐vrij? Motiveer uw antwoord. OPGAVE 5 Gegeven is de volgende turingmachine met tapealfabet {a, #} en invoeralfabet {a}:
5a Geef de momentane beschrijving van alle stappen (de berekening) van de turingmachine als hij start met aa op de band.
3 punten
5b Idem voor de invoer aaa.
3 punten
5c Welke invoerstring brengt de turingmachine rechtstreeks van begintoestand q0 via toestand q1 naar eindtoestand q2 gaan?
3 punten
5d Stel dat de invoerstring de vorm an (met n > 1) heeft. Welke waarde moet n hebben wil de turingmachine de cykel q0, q1, q3, q5, q0 één keer doorlopen en hoe ziet de inhoud van de tape na de gang door de cykel?
4 punten
5e Idem voor de cykel q0, q1, q3, q4, q3, q5, q0.
8 punten
4
5f Beschrijf hoe de invoer verwerkt wordt en geef aan welke taal over het alfabet {a} deze turingmachine accepteert.
OUN
Eindtoets
T E R U G K O P P E L I N G Uitwerking van de opgaven 1a Om G te kunnen bepalen, construeren we eerst een automaat Ac die het complement van L accepteert. Dit kan op verschillende manieren, waarvan we er twee volledig uitwerken. Eerste manier De eerste manier is om eerst een deterministische automaat A voor L te bepalen. Door van deze automaat de eindtoestanden en niet‐ eindtoestanden te verwisselen, krijgen we de (deterministische) automaat Ac voor het complement van L. De volgende automaat A1 representeert de taal {x {a, b}* : x bevat ten minste één a}:
De taal {x {a, b}* : x bevat een even aantal bʹs} kan door de volgende eindige automaat A2 worden gerepresenteerd:
Met behulp van de doorsnedeconstructie bepalen we de automaat die L = L(A1) L(A2) representeert:
Omdat A1 en A2 deterministisch zijn, is ook de geconstrueerde automaat A deterministisch. Omdat A totaal en deterministisch is, behoeven we slechts de eindtoestanden en niet‐eindtoestanden te verwisselen om een eindige automaat Ac te krijgen die het complement van de taal L representeert. We geven de toestanden ook andere namen:
OUN
5
Formele talen en automaten
Uitgaande van deze eindige automaat kunnen we eenvoudig de rechtslineaire grammatica construeren die het complement van L genereert. Deze grammatica G = ({S, A, B, C}, {a, b}, P, S) heeft de volgende verzameling productieregels: S aA | b | bB | λ A aA | b | bC B a | aC | b | bS C a | aC | bA Tweede manier We kunnen ook direct een automaat voor {a, b}* – L construeren. We formuleren dit complement van L daartoe als volgt: {a, b}* – L = {x {a, b}* : x bevat geen aʹs of een oneven aantal bʹs} = {x {a, b}* : x bevat geen aʹs} {x {a, b}* : x bevat een oneven aantal bʹs} = L1 L2 We construeren automaten voor L1 en L2:
De niet‐deterministische automaat bestaande uit beide gegeven componenten representeert L1 L2. Door deze automaat deterministisch te maken krijgen we precies de eerder gevonden automaat Ac, waaruit we op dezelfde manier de rechtslineaire grammatica kunnen afleiden. 1b Ook voor deze opgave bestaan verschillende oplossingsmethoden. Eerste manier Uiteraard kunnen we de procedure nfa‐to‐rex uit leereenheid 3 toepassen op de in het onderdeel a gevonden automaat A. We maken eerst een GTG:
6
OUN
Eindtoets
Eerst verwijderen we q1. Hiervoor moeten we voor negen paren van knooppunten de reguliere expressie evalueren met behulp van equation 3.3 van de procedure nfa‐to‐rex: (q0, q0): r00 + r01r11*r10 = Ø + bØ*b = bb (q2, q2): r22 + r21r11*r12 = a + ØØ*a = a (q3, q3): r33 + r31r11*r13 = a + ØØ*Ø = a (q0, q2): r02 + r01r11*r12 = Ø + bØ*a = ba (q0, q3): r03 + r01r11*r13 = a + bØ*Ø = a (q2, q0): r20 + r11r11*r10 = Ø + ØØ*b = Ø (q2, q3): r23 + r21r11*r13 = b + ØØ*Ø = b (q3, q0): r30 + r31r11*r10 = Ø + ØØ*b = Ø (q3, q2): r32 + r31r11*r12 = b + ØØ*a = b Zonder q1 ziet de GTG als volgt uit:
Nu wordt q2 verwijderd. Hiervoor moeten we voor vier paren van knooppunten equation 3.3 van de procedure nfa‐tprex toepassen: (q0, q0): r00 + r02r22*r20 = bb + baa*Ø = bb (q3, q3): r33 + r32r22*r23 = a + ba*b (q0, q3): r03 + r02r22*r23 = a + baa*b (q3, q0): r30 + r32r22*r20 = Ø + ba*Ø = Ø Zonder q2 hebben we de volgende GTG:
OUN
7
Formele talen en automaten
Met behulp van equation 3.2 van de procedure nfa‐to‐rex kunnen we de reguliere expressie evalueren: r = (bb)*(a + baa*b)(a + ba*b)* Uiteraard zijn door een andere nummering van de toestanden ook andere reguliere expressies voor de taal L te verkrijgen! Tweede manier We passen de pragmatische manier van leereenheid 3 toe op de automaat van L:
Stap 1: verwijder q2:
Stap 2: verwijder q3:
Het resultaat is ook r = (bb)*(a + baa*b)(a + ba*b)* .
8
OUN
Eindtoets
Derde manier We kunnen ook rechtstreeks uit de beschrijving van L een reguliere expressie voor L opstellen. We kunnen L namelijk schrijven als: L = Le.{a}.Le Lo.{a}.Lo waarbij Le de taal is die alle strings over {a, b} met een even aantal bʹs bevat en Lo de taal is die alle strings met een oneven aan bʹs bevat. Le is dus de taal behorende bij de volgende eindige automaat:
Het is niet moeilijk in te zien dat Le te schrijven is als Le = ({a} {b}{a}*{b})* Analoog is Lo de taal behorende bij de volgende eindige automaat:
We krijgen zo Lo = {a}*{b}({a} {b}{a}*{b})* We kunnen de taal L als volgt beschrijven: L = ({a} {b}{a}*{b})*{a}({a} {b}{a}*{b})* {a}*{b}({a} {b}{a}*{b})*{a}{a}*{b}({a} {b}{a}*{b})* De bijbehorende reguliere expressie wordt dus: (a + ba*b)*a(a + ba*b)* + a*b(a + ba*b)*aa*b(a + ba*b)* 2 Veronderstel dat L wel regulier is. Volgens de pompstelling bestaat er dan een constante m, waarbij geldt dat iedere string uit L met lengte m of groter, te verdelen is in substrings u, v en w, met v ≠ λ, uv ≤ m en uvnw L voor alle n ù. We kiezen nu een string z = im + im = i2m met z = 4m + 2 $ m. Omdat z L, moet er een verdeling van z in stukken u, v en w bestaan als aangegeven. Omdat uv ≤ m en de eerste m symbolen van z iʹs zijn, moet (zowel u als) v alleen uit iʹs bestaan. Dus geldt v = ik met 1 ≤ k ≤ m. Als we z nu ‘leegpompen‘ dan krijgen we: uv0w = im‐k + im = i2m (1 ≤ k ≤ m) en deze string behoort niet tot L. L is dus niet regulier pompbaar en dus niet regulier.
OUN
9
Formele talen en automaten
3a We zorgen ervoor dat eerst de iʹs voor het plusteken en evenveel iʹs aan de rechterkant komen. Daarna komen de iʹs na het plusteken en laatste iʹs na het is‐teken komen. De taal wordt gegenereerd door de grammatica G = ({S, T }, {i, +, =}, P, S) met de volgende productieregels: S i S i | i + T i T i T i | i = i 3b Er bestaan verschillende oplossingsmethoden. We geven er twee. Eerste manier We kunnen een stapelautomaat construeren met vier toestanden q0, q1, q2 en q3 en met stapelstartsymbool Z. In toestand q0 worden de iʹs vóór het plusteken geteld. Voor elke i komt een stapelsymbool 1 op de stapel. In toestand q1 wordt het aantal iʹs na het plusteken erbij opgeteld. In toestand q2 wordt voor elke i na het is‐teken een stapelsymbool 1 van de stapel gehaald. Toestand q3 is de eindtoestand die alleen bereikt kan worden als er geen stapelsymbool 1 meer op de stapel staat.
Tweede manier Hiervoor gebruiken we de alternatieve constructie om voor de context‐ vrije grammatica uit onderdeel a een stapelautomaat te construeren; zie leereenheid 7, paragraaf2.
10
4a Er zijn twee gevallen te onderscheiden: prefix en suffix vallen wel of niet samen: L = Lʹ.{a, b}*.Lʹ Lʹ 4b De taal Lʹ is context‐vrij. De taal {a, b}* is regulier en dus context‐vrij. Context‐vrije talen zijn gesloten onder concatenatie en vereniging, en dus is L context‐vrij. 5a De berekening voor aa is: q0aa ⊢ #q1a ⊢ #aq3 ⊢ #q5a ⊢ q5#a ⊢ q5□#a ⊢ q0#a ⊢ #q0a ⊢ ##q1 ⊢ ##□q2
OUN
Eindtoets
Als de turingmachine in eindtoestand q2 stopt staat ## op de tape.
5b De momentane beschrijvingen voor aaa zijn: q0aaa ⊢ #q1aa ⊢ #aq3a ⊢ # a#q4 Als de turingmachine in toestand q4 stopt staat #a# op de tape. 5c De invoerstring is dan gelijk aan a. 5d Wil de turingmachine de cykel q0, q1, q3, q5, q0 één keer doorlopen dan moet de invoerstring twee aʹs bevatten (zie ook 5a). Na de cykel bevat de band #a. 5e Voor de cykel q0, q1, q3, q4, q3, q5, q0 moet n gelijk zijn aan 4. De invoerstring is dan aaaa. Na de cykel bevat de band #a#a. 5f De turingmachine markeert in een cykel van q0 naar q0 steeds de helft van de voorkomens van het symbool a. Dit proces wordt herhaald vanaf het begin van de string totdat het aantal a’s na het doorlopen van de string oneven is. Bevat de tape dan nog één niet‐gemarkeerde a, dan gaat de turingmachine naar eindtoestand q2. Kortom: we delen het aantal a’s steeds door 2, totdat we maar één a overhouden. Als je het andersom bekijkt accepteert de turingmachine dus precies de strings met 1 a, 2*1 = 2 a’s, 2*2*1 = 4 a’s, 2*2*2*1 = 8 a’s, 2*2*2*2*1 = 16 a’s. De turingmachine accepteert dus de taal {an : n = 2m, m 0}
OUN
11
