6 ECTS credits
150 u studietijd
Aanbieding 2 met studiegidsnummer 1007146BNR voor alle studenten in het 2e semester met een verdiepend bachelor niveau.
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.
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
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.
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:
Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:
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
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