6 ECTS credits
150 u studietijd

Aanbieding 2 met studiegidsnummer 1007146BNR voor alle studenten in het 2e semester met een verdiepend bachelor niveau.

Semester
2e semester
Inschrijving onder examencontract
Niet mogelijk
Beoordelingsvoet
Beoordeling (0 tot 20)
2e zittijd mogelijk
Ja
Inschrijvingsvereisten
Studenten bachelor ingenieurswetenschappen en studenten bachelor wiskunde & data science hebben ‘Higher-Order Programming’ gevolgd, alvorens ‘Automaten en berekenbaarheid’ op te nemen. Studenten uit de bachelor computerwetenschappen hebben ‘Structuur van computerprogramma's 1’ gevolgd alvorens ‘Automaten en berekenbaarheid' op te nemen.
Onderwijstaal
Engels
Faculteit
Faculteit Wetenschappen en Bio-ingenieurswetensch.
Verantwoordelijke vakgroep
Computerwetenschappen
Onderwijsteam
Antonio Paolillo (titularis)
Onderdelen en contacturen
26 contacturen Hoorcollege
26 contacturen Werkcolleges, practica en oefeningen
110 contacturen Zelfstudie en externe werkvormen
Inhoud

1. Syntax (formal languages):

1.1. Regular languages and finite automata: equivalence, (non)determinism, optimization.
1.2. Context free grammars: definitions and general properties (e.g. normalforms), pushdown automata.
1.3. Context-sensitive grammars: definitions and general properties, linear bounded automota
1.4. Introduction to parsing.

2. Computability: Solvable and unsolvable problems, Theorem of Church, Turing Machines.

3. Computability with respect to Formal Languages.
 

Studiemateriaal
Digitaal cursusmateriaal (Vereist) : Automaten en berekenbaarheid, Kopieën van de slides van de titularis, Leerplatform
Handboek (Vereist) : An Introduction to Formal Languages and Automata, Peter Linz, 6de, Jones & Bartlett Learning, 9781284077247, 2017
Bijkomende info

Copies of the slides, summaries of the courses and detailed proofs are available on Canvas. 
Warning: the slides and/or summaries are not sufficient material to pass the exam; the handbook is mandatory.

Handbook: Linz: 'An Introduction to Formal Languages and Automata,Jones & Bartlett Learning, 2017.

Additional material:

Inleiding in de theorie van de formele talen,V.J. Rayward-Smith
Berekenbaarheid,V.J. Rayward Smith 
 

Leerresultaten

Algemene competenties


Knowledge:
The student knows the basic concepts introduced in this course (such as: regular language, context-free language, finite automaton, Turing machine, context-sensitive grammar, ...) and can define them.

Insight:
The student can reason about the possibilities and restrictions of formal languages (regular languages, contextfree languages, context-sensitive languages, ... ) and their corresponding automata.
The student can explain the basic concepts of this course. 
The student can reconstruct proofs and explain details of them orally. 

The use of knowledge and insight:
The student can apply the theorems and techniques on unseen languages/automata/grammars.

Judgement ability:
The student can judge where in the Chomsky hierarchy a formal language resides and argue correctness of this answer. 
The student can judge whether some previously unseen problem is (semi-)decidable or (semi-)computable.
The student can identify mistakes in a given mathematical proof. 

Creation:
The student can can create correct mathematical proofs voor variants of a known theorem.
The student can create an automoaton/grammar that accepts a given formal language. 

Beoordelingsinformatie

De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Mondeling bepaalt 50% van het eindcijfer

Examen Schriftelijk bepaalt 50% van het eindcijfer

Binnen de categorie Examen Mondeling dient men volgende opdrachten af te werken:

  • Mondeling theorie examen met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

    Toelichting: Het examen is een gesloten boek examen. Om een voldoende te behalen moet een student goed scoren op een 2-tal basisvragen. De bijkomende vragen hebben een hogere moeilijkheidsgraad en bepalen de graad.

Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:

  • Schriftelijk oefeningen examen met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

    Toelichting: Er is een verplicht schriftelijk oefeningenexamen. Dit examen is ook geloten boek.

Aanvullende info mbt evaluatie

50% exercises
50% theory

Theory: There is a mandatory closed book oral exam. To pass the exam the student should score well on two or three basic questions. The additional question will make up the final degree.

Exercises: There is a mandatory closed book written exam.

Both exams are organised in the second semester

Toegestane onvoldoende
Kijk in het aanvullend OER van je faculteit na of een toegestane onvoldoende mogelijk is voor dit opleidingsonderdeel.

Academische context

Deze aanbieding maakt deel uit van de volgende studieplannen:
Bachelor in de ingenieurswetenschappen: elektronica en informatietechnologie Profiel profiel computerwetenschappen
Bachelor in de ingenieurswetenschappen: verkort traject elektronica en informatietechnologie na vooropleiding industriële wetenschappen
Bachelor in de computerwetenschappen: Standaard traject
Bachelor in de wiskunde en Data Science: Standaard traject
Bachelor in de artificiële intelligentie: Standaard traject