Automata and Computability

5 ECTS credits
150 u studietijd

Aanbieding 1 met studiegidsnummer 2019970BNW voor werkstudenten 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

Inschrijvingsvereisten

'Automaten en berekenbaarheid’ opnemen houdt in dat je gelijktijdig ‘Structuur van computerprogramma's 1’ of 'Higher-Order Programming' volgt of reeds geslaagd bent voor ‘Structuur van computerprogramma's 1’ of 'Higher-Order Programming'.

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
125 contacturen Zelfstudie en externe werkvormen

Inhoud

yntax (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 transparanten 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:

Oral exam theory met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

Toelichting: The exam is a closed book exam. To obtain a passing grade, a student must score well on two basic questions. The additional questions have a higher degree of difficulty and determine the grade.

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

Written exam exercises met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

Toelichting: There is a mandatory written exercise exam. This exam is also a closed book.

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