Werkcollege Formele Talen en Automaten 1, voorjaar 2003

Het werkcollege Formele Talen en Automaten 1 werd dit voorjaar gegeven door Rudy van Vliet. Je kunt hem vinden op kamer 150 van het gebouw van Informatica (en Wiskunde en de I-groep). Hij is bereikbaar onder telefoonnummer 071-5277050 of per email rvvliet@liacs.nl.

Tentamen nagekeken

Op dinsdag 27 mei 2003, van 14:00-17:00 heeft het tentamen voor dit vak plaatsgevonden (u weet wel, waar u al uw bonuspunten voor heeft verdiend). Dit tentamen is nagekeken. Zonder dat we al te veel hoefden te sjoemelen hebben 34 van de 47 studenten het gehaald. U vindt de behaalde cijfers hier. Bent u vergeten wat uw collegekaartnummer is? Dan vindt u de cijfers ook aan de deur van Rudy's werkkamer, kamer 150, inclusief studentnamen. De docente heeft de cijfers gecontroleerd, dus u kunt ervan uitgaan dat ze zo ook op uw tentamenkaart terechtkomen. Deze tentamenkaart kan overigens wel even op zich laten wachten, omdat niet iedereen die bij de productie van de tentamenkaart betrokken is (ja, ja, het is een hele procedure) er altijd is in deze vakantietijd.
Voor de statistiek: de bonus die men bij de huiswerkopgaven kon verdienen heeft er voor gezorgd dat 13 studenten een hoger cijfer hebben gehaald dan ze anders hadden gehaald. Een van hen heeft daardoor zelfs het tentamen gehaald!
Je kunt je eigen uitwerkingen van het tentamen op Rudy's kamer ophalen (graag zelfs). Ook hij neemt echter wel eens een dag vrij. Als je van plan bent om speciaal voor het ophalen van je tentamen naar het instituut te komen, vraag Rudy dan eerst of hij er wel zal zijn.

Hertentamen

Op dinsdag 5 augustus 2003, 14:00--17:00, heeft het hertentamen plaatsgevonden. Eventuele verdiende bonuspunten voor huiswerkopgaven waren toen niet meer geldig.
Ook dit tentamen is nagekeken. Dit keer hebben 9 van de 20 studenten het gehaald. U vindt de behaalde cijfers hier. Bent u vergeten wat uw collegekaartnummer is? Dan vindt u de cijfers ook aan de deur van Rudy's werkkamer, kamer 150, inclusief studentnamen.
Dit hertentamen was het laatste reguliere tentamen Formele Talen en Automaten 1. Het vak wordt onder de Bachelor-Master-structuur niet meer aangeboden. Wel kun je het in het komend najaar nog in de avonduren volgen. Dat is echt de laatste gelegenheid.

Behandelde opgaven

Op het werkcollege hebben we de volgende opgaven behandeld:

21 januari 2003: 3.1, 3.2, 3.4.
28 januari 2003: 3.6, 3.7 (K1, K2, K3), 3.8, 3.14a.
4 februari 2003: 3.15a, 3.17, 3.18 (3.15), 3.21a.
11 februari 2003: 3.28, 3.29 (3.1), 3.30, 3.31.
18 februari 2003: 3.34a.
25 februari 2003: 3.41, 4.1 (a, b, e, f), 4.5.
11 maart 2003: 4.6, 4.2, 4.3, 4.4.
18 maart 2003: nabespreking huiswerkopgave 1, 4.7, 4.8.
25 maart 2003: 4.11b (Chomsky), 4.13.
1 april 2003: 4.14 (K3), 4.26, 4.18.
8 april 2003: 5.1 (b, c, c', d), 5.2 (b, c).
15 april 2003: 5.4 (4.11), 5.5, 5.6.
22 april 2003: nabespreking huiswerkopgave 2, 5.9, 5.11, 5.15 (b (first)).
12 mei 2003: nabespreking huiswerkopgave 3, 5.15 (b), 5.16.

Huiswerkopgaven

(This part of the page is also available in English).
In de loop van het college zijn enkele huiswerkopgaven opgegeven. Studenten die die opgaven oplosten en de oplossingen op tijd (daar waren we strict in) inleverden, konden daarmee per keer 0.20 of 0.25 punt bonus verdienen voor het tentamen. Wie maar een deel van de huiswerkopgaven inleverde, kon ook maar een deel van de maximale bonus verdienen. De bonus was alleen geldig voor het tentamen van dinsdag 27 mei 2003. Oplossingen konden ingeleverd worden bij Rudy van Vliet.

Huiswerkopgave 1

Op het werkcollege van 4 februari 2003 hebben we het eerste deel van opgave 3.21 gemaakt. De aanwezigen weten nu hoe ze een eindige automaat (met λ-takken) kunnen maken die de gegeven taal K herkent.
Construeer nu een deterministische eindige automaat (zonder λ-takken) voor K en bepaal met behulp van de methode van Brzozowski en McCluskey een reguliere expressie voor K. Geef hierbij ook tussenresultaten.
Inleverdatum: Uiterlijk 18 februari 2003.
Maximale bonus: 0.20 punt.
Deze huiswerkopgave is nagekeken! Je kunt je uitwerkingen met commentaar ophalen bij Rudy van Vliet. Ook kun je dan de bonus zien die je met de opgave gescoord hebt.

Huiswerkopgave 2

Op het werkcollege van 18 februari 2003 hebben we het eerste deel van opgave 3.34(a) gemaakt. Maak dit onderdeel af. Lever heel 3.34(a) in. Gebruik in principe steeds de officiële constructie, zoals beschreven in paragraaf 3.11 van het dictaat. Alleen de deelformule `i<k<j' hoef je niet om te schrijven tot `i<j ∧ j<k'. Die deelformule mag je in een keer in een eindige automaat vangen.
Inleverdatum: Uiterlijk 11 maart 2003.
Maximale bonus: 0.25 punt.
Deze huiswerkopgave is nagekeken! Je kunt je uitwerkingen met commentaar ophalen bij Rudy van Vliet. Ook kun je dan de bonus zien die je met de opgave gescoord hebt.

Huiswerkopgave 3

In deze huiswerkopgave moet je aan de slag met het pomplemma voor context-vrije talen (Stelling 4.42). De huiswerk opgave bestaat uit twee delen: opgave 4.14 (K1) en opgave 4.15, beide uit het opgaven dictaat.
In opgave 4.14 (K1) moet je aantonen dat de gegeven taal K1 niet context-vrij is. Dit kan met behulp van het pomplemma.
In opgave 4.15 moet je laten zien dat je het pomplemma niet kunt omkeren: er zijn talen die je wel kunt `pompen', terwijl ze niet context-vrij zijn. De gegeven taal K is daar een voorbeeld van, en dat moet je bewijzen. Laat dus zien dat K wel de eigenschap van het pomplemma heeft (K kan `gepompt' worden), maar dat K niet context-vrij is. Voor dit laatste deel kun je gebruik maken van de afsluitingseigenschappen van CF uit paragraaf 4.9 van het dictaat (eventueel in combinatie met het pomplemma).
Inleverdatum: Uiterlijk 15 april 2003.
Maximale bonus: 0.25 punt.
Deze huiswerkopgave is nagekeken! Je kunt je uitwerkingen met commentaar ophalen bij Rudy van Vliet. Ook kun je dan de bonus zien die je met de opgave gescoord hebt.

Huiswerkopgave 4

In deze huiswerkopgave moet je laten zien dat je de constructie uit Stelling 5.16 kunt toepassen `in de praktijk'. Gegeven zijn de context-vrije taal K = {aⁱb^jc^k | i, j, k ≥ 1, i = j+2k} en het homomorfisme h van Φ = {a, b, c, d} naar Δ = {a, b, c} dat gedefinieerd wordt door h(a) = aabc, h(b) = bc, h(c) = λ (lambda), h(d) = a. Construeer nu een stapelautomaat voor h^-1(K). De totale constructie bestaat uit zes stappen. Je dient al deze stappen te doorlopen (wat minder erg is dan het misschien lijkt):

Stap 1: Construeer een context-vrije grammatica G voor K. Het kan met vier producties. Als je er zelf meer hebt, kan dat betekenen dat je later meer werk te doen hebt.
Stap 2: Breng G in Chomsky normaalvorm of Greibach normaalvorm. Je mag zelf kiezen.
Stap 3: Construeer een stapelautomaat A zodat K de lege-stapel-taal van A is. Gebruik hiervoor de constructie van Lemma 5.10.
Stap 4: Construeer een stapelautomaat A' zodat K de eindtoestands-taal van A' is. Gebruik hiervoor de constructie van Lemma 5.7.
Stap 5: Bepaal de verzameling Buf uit het bewijs van Stelling 5.16, behorend bij het homomorfisme h.
Stap 6: Construeer een stapelautomaat A'' zodat h^-1(K) de eindtoestands-taal van A'' is. Gebruik hiervoor de constructie van Stelling 5.16. Je mag `nutteloze' toestanden weglaten/verwijderen. Maak in dat geval echter wel duidelijk waarom de weggelaten/verwijderde toestanden `nutteloos' waren.

Na beëindiging van deze constructie: beredeneer hoe h^-1(K) eruit ziet, d.w.z.: welke woorden allemaal in h^-1(K) zitten.
Inleverdatum: Uiterlijk maandag 12 mei 2003.
Maximale bonus: 0.25 punt.
Deze huiswerkopgave is nagekeken! Je kunt je uitwerkingen met commentaar ophalen bij Rudy van Vliet. Ook kun je dan de bonus zien die je met de opgave gescoord hebt.

Meer informatie

Meer informatie over dit college is te vinden op de hoofdpagina van het college.

Laatste wijziging: 6 augustus 2015

Vragen en opmerkingen kunnen worden gestuurd naar: rvvliet@liacs.nl.