Inhoud

Automaten en talen (10 u.)
- Taal – grammatica – BNF
- Reguliere – context vrije taal
- FSA – push-down automaat – Turing (*)
- Samenstelling van automaten (en verband met programmacompositie)
- Verband met parsing
 
Berekenbaarheid (6 u.)
- Recursieve functies
- Berekenbare functies
- Beslisbare talen
 
Rekenen met herschrijfsystemen (8 u.)
- Lambda-calculus
- Horn-clausus
 
Rekenen volgens andere paradigmas (2 u.)
- Quantum computing
- Ant computing
- Dna computing
- …
 
Meer gedetailleerd zullen de volgende topics aan bod komen:
finite state automata reguliere grammaticas reguliere talen; stelling van Kleene; het "pumping" lemma voor reguliere talen; beslisbaarheid van de eindigheid van reguliere talen; invariantie onder unie, complement, doorsnede, concatenatie, repetitie; minimisatie van een FSA; het product van FSAs; van een niet-deterministische naar een deterministische FSA; transducers m.b.v. FSAs; kracht van een FSA: (optelling – niet vermenigvuldiging); andere formalismen (bijvoorbeeld neurale netten); context vrije grammatica; equivalente grammaticas (Chomsky normal form, Greibach normal form); het "pumping" lemma voor context vrije talen; ambigue grammar – derivatie; beslisbaarheid van de eindigheid van reguliere talen;
invariantie onder unie, complement, doorsnede, concatenatie, repetitie; LR(k); deterministische en niet-deterministische PDA; berekenbare functies; recursieve functies; simpele/algemene recursieve functies (met mogelijke motivatie uit arithmetizatie van TMs); partiele/totale recursieve functies; recursieve verzamelingen; equivalente TM met varianten (multitape …); universele TM; halting probleem; andere onbeslisbare problemen; de berekenbare reele getallen; definitie van lineair begrensde automaat – context sensitieve taal; er bestaat een context sensitieve taal die niet context vrij is; definitie van herschrijfsysteem; berekeningskracht; definieren van functies m.b.v. een herschrijfsysteem; lambda-calculus, reductie, conversie; recursieve functies; reductiestrategie; Horn clause logica, resolutie; selectiestrategie; vragen over beslisbaarheid en eindigheid in dit kader.
Bedoeling is een eerder oppervlakkige, intuitieve behandeling van de andere paradigmas.

Studiemateriaal

Cursustekst van de docent, uitgegeven door studentencursusdienst, en vrij op het net te vinden.

Toelichting werkvorm

De studenten bereiden een stuk uit de cursus voor en hebben tijdens de les
de gelegenheid om vragen te stellen. Occasioneel geeft de docent een
klassiek hoorcollege.

De oefeningen worden aangeboden in de vorm van take-home opdrachten
die de student dient te maken voor de zitting: tijdens de zitting
worden de gemaakte opdrachten besproken in groep.
De opdrachten hebben als bedoeling de student te leren de theorie toe te passen passen op problemen.

Inhoud

De oefenzittingen hebben tot doel de begrippen en algoritmen uit de
hoorcolleges beter te laten begrijpen door de theoretische leerstof
toe te passen in concrete opdrachten. De student leert ook
verschillende onderdelen van de cursus samen te voegen om nieuwe
resultaten te verkrijgen. De invulling hiervan bestaat uit
    - uit een beschrijving van een taal een NFA of Reguliere Expressie voor die taal maken
    - van een operatie op talen bepalen of die operatie inwendig is in de reguliere talen
    - omzetten van een NFA op een DFA op concrete voorbeelden uitwerken
    - varianten van NFA's en DFA's en bewijzen dat ze even krachtig zijn
    - bewijzen dat sommige talen niet regulier zijn door toepassen
van het pompend lemma voor reguliere talen
    - van een operatie op talen bepalen of die operatie inwendig is in de contextvrije talen
    - de contextvrije grammatica geven van een taal gespeficieerd in verzamelingnotatie
    - de PDA construeren voor een gegeven contextvrije taal
    - omzetten van een CFG naar zijn Chomsky-normaalvorm
    - bewijzen dat een gegeven taal contextvrij is of het tegendeel
    - varianten van PDA's met identieke berekeneningskracht
    - varianten van Turingmachines die zwakker of even sterk zijn
    - aantonen dat gegeven talen beslisbaar/herkenbaar zijn
    - toepassen van de notie van (Turing)reduceerbaarheid
    - bewijzen dat gegeven functies (mu-)recursief zijn
    - inoefenen conversieregels van de lambda-calculus
 

De oefeningen worden aangeboden in de vorm van take-home opdrachten
die de student dient te maken voor de zitting: tijdens de zitting worden de gemaakte opdrachten besproken in groep.

Studiemateriaal

Zelfde als voor het vak.

Toelichting werkvorm

De oefeningen worden aangeboden in de vorm van take-home opdrachten
die de student dient te maken voor de zitting: tijdens de zitting worden de gemaakte opdrachten besproken in groep.