people.cs.kuleuven.be Open in urlscan Pro
2a02:2c40:500:a030:c515:1337:0:32  Public Scan

Form analysis
0 forms found in the DOM

Text Content

--------------------------------------------------------------------------------


AB 2021-2022

--------------------------------------------------------------------------------

Cursusnotas [UP TO DATE: meest recente aanpassing 29 september 2021]

Errata:

 * p. 31, onderaan "Of in de nieuwe notatie, als {w | delta*(p,w) \in F} = {w |
   delta*(ps,w) \in F}.": verander ps in q.
 * Definitie 2.12.5 op p. 38 verwijst naar een figuur die niet ingevuld is en op
   p. 39 had moeten staan. De oorzaak is een bug in Latex. De figuur is deze.
   Het laat het isomorfisme zien.
   

De inhoud van de cursus kan je op veel plaatsen in boeken terugvinden, want het
gaat om klassieke theorie die in elke opleiding
informatica/computerwetenschappen voorkomt. Aanraders zijn o.a. "Introduction to
the Theory of Computation" van Michael Sipser en "Automata and Computability"
van Dexter C. Kozen voor hoofdstukken 2 en 3. Voor hoofdstuk 4, zie de reflijst
in sectie 4.4.

--------------------------------------------------------------------------------

Het examenverloop De lessen en het wekelijkse filmpje De planning Wat
examenvragen van vroeger Regels vd gekwoteerde oefenzittingen De oefenzittingen

--------------------------------------------------------------------------------

Het examenverloop

In corona-tijden zal het examen schriftelijk zijn en 2uur duren. De vragen zijn
van soortgelijke aard als anders.
In corona-vrije omstandigheden is het examen mondeling met "schriftelijke"
voorbereiding, gesloten boek en gaat hoofdzakelijk over de theorie.
De "schriftelijke" voorbereiding duurt ongeveer 1 uur, de mondelinge
ondervraging ongeveer 15 minuten.
Het examen gaat over de theorie in de cursustekst. Varianten van constructies en
stellingen kunnen gevraagd worden om verder inzicht en vaardigheid in het
toepassen van de theorie na te gaan.
In twee oefenzittingen krijgen de studenten de kans om schriftelijk en
individueel een opdracht te maken die telkens op 3/20 punten staat. Die punten
worden overgedragen naar de 2de examenkans zonder mogelijkheid die opnieuw te
behalen: het gaat immers om (partiele) permanente evaluatie. Wie niet slaagt
voor het examen tijdens de examenperiode kan niet slagen voor het vak.

--------------------------------------------------------------------------------

De "lessen" en het wekelijkse filmpje

AB gaat door in het eerste semester, maar wordt niet op de klassieke manier
gedoceerd. De syllabus heeft 4 delen: Automaten en Talen, Berekenbaarheid,
Herschrijfsystemen en Andere Paradigmas. Er zijn cursusnotas in het nederlands.
Ze worden verspreid langs de WINA-cursusdienst, en zullen hier beschikbaar
blijven. Mogelijk worden een paar aanvullingen in de les verspreid, tegen
minimale kost (maar de pdf's zal je hier altijd kunnen downloaden).

Bij elke les hoort een kort introductiefilmpje. Hoe maak je er gebruik van ...
hier een suggestie: bekijk/beluister het filmpje, bestudeer dan de
overeenkomstige cursustekst, en bekijk/beluister het filmpje nog eens. Is nog
niet alles duidelijk, dan heb je vragen om in de les te stellen. Is alles
duidelijk ... dan heb je waarschijnlijk een en ander gemist, en is het nuttig om
naar de les te komen om nog wat bij te leren.

Lessen kunnen on-line gevolgd worden via de Collaborate course meeting room op
Toledo. Opnames zullen ter beschikking gesteld worden.

Mocht blijken dat er een voorkeur bestaat om de lessen helemaal on-line te
organiseren, dan zullen we daartoe overgaan.

Bereid de les en de oefenzitting voor !

--------------------------------------------------------------------------------

De planning



Datum les Datum Oefenzitting Voorbereiden bijhorend filmpje-slides opmerkingen 4
okt cursus t.e.m. 2.8 filmpje1 en slides1 11 okt cursus t.e.m. 2.12 filmpje2 en
slides2 12 okt Opgave oefenzitting 1 een oplossing Hint voor vraag 3b):
definieer n toestanden q0,..,qn-1, definieer delta zodanig dat na het parsen van
de deelstring p1..pk van de volledige string p1..pl we in toestand qi zitten
waarbij i=(p1..pk)modulo n. Bv. na het parsen van de string '11' zitten we in de
toestand pi, met i= 3 modulo n. Na het parsen van '111' zitten we in toestand
pj, met j = 7 modulo n. 18 okt cursus t.e.m. 2.18 filmpje3 en slides3 Is RegLan,
de verzameling van reguliere talen regulier? Om te beginnen, is dit wel een
zinvolle vraag? Een taal is een verzameling van strings, terwijl RegLan een
verzameling van verzamelingen van strings is. De signatuur klopt niet. Een
betere vraag zou zijn: is de verzameling van reguliere expressies een reguliere
taal? Ook hierbij is er een probleem: een reguliere taal is een verzameling van
strings over een vast vocabularium, terwijl reguliere expressies over
willekeurige vocabuaria bestaan. Dit kan verholpen worden door in reguliere
expressies de symbolen te encoderen, bv. als strings tussen vierkante haakjes
[1], [11], [111], ... Het vocabularium van RegLan is dan {epsilon, phi, [, 1, ],
(, ), |, *}. Hiermee kan elke reguliere expressie geencodeerd worden. Is de
resulterende taal regulier, en hoe dit te bewijzen? Als ze regulier is dan
bestaat een pomplengte d zodat elke string s met |s|>d van de vorm is s = xyz,
zodat xyiz behoort tot RegLan voor alle i, |xy|<d en |y|>0. Merk nu op dat in
reguliere expressies, het aantal haakjes ( en ) altijd gelijk zijn. Neem een
reguliere expressie s zodat de eerste d symbolen linkerhaakjes ( zijn. Dan bevat
y enkel linkerhaakjes, en zal bij het pompen onevenwicht ontstaan met het aantal
rechterhaakjes. Dus, RegLan is niet regulier. H Maar is het een CFL? 19 okt
Opgave oefenzitting 2 een oplossing 25 okt cursus t.e.m. 2.21 filmpje4 en
slides4 26 okt Opgave oefenzitting 3 een oplossing 8 nov cursus t.e.m. 3.3
filmpje5 en slides5 9 nov Opgave oefenzitting 4 een oplossing 15 nov cursus
t.e.m. 3.13 filmpje6 en slides6 16 nov Opgave oefenzitting 5 een oplossing.
Slides. 22 nov cursus t.e.m. 3.16 filmpje7 en slides7 23 nov Gekwoteerde
oefenzitting, cursus t.e.m. p80 Bekijk ook oefenzitting 5! 29 nov cursus t.e.m.
3.19 filmpje8 en slides8 30 nov Opgave oefenzitting 6 een oplossing 6 dec geen
les 7 dec Opgave oefenzitting 7 een oplossing 13 dec cursus tot aan einde ;
Vragen over cursus en examen filmpje9 en slides9 14 dec Opgave oefenzitting 8
een oplossing Bijkomende oefeningen over vanalles 20 dec geen les 21 dec
gekwoteerde oef, t.e.m. herschrijfsystemen -



De gekwoteerde oefenzittingen

De gekwoteerde oefenzittingen gaan door op 23 nov en 21 december. Tijdens de
gekwoteerde oefenzitting mag je de cursusnota's op papier gebruiken, met daarin
je eigen aantekeningen (eventueel op aparte bladen papier), maar geen
(opgeloste) oefeningen behalve de "Zelf doen"s uit de cursus.

Ze zijn verplicht. Voor wie 1x gewettigd afwezig is, zal de oefening niet
hernomen worden maar de examenscore wordt geschaald van 17 naar 20. Wie 2x
gewettigd afwezig is, zal een speciale gekwoteerde oefensessie krijgen.

De oefenzittingen

De andere oefenzittingen zijn gepland op dinsdagen vanaf begin oktober. De
oefenzittingen moeten voorbereid worden: de opgaven zullen hierboven
verschijnen, en later ook oplossingen.



--------------------------------------------------------------------------------

Mogelijke examenvragen



Gebruik deze lijst verstandig en voorzichtig. Geen enkele poging werd gedaan om
een volledige lijst op te stellen of om alle topics uit de cursus te bedekken.
Er is ook geen garantie dat de vragen uit deze lijst effectief zullen gesteld
worden op het examen.

--------------------------------------------------------------------------------