- 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. Introduction to parsing.
- Computability: Solvable and unsolvable problems, Theorem of Church, Turing Machines.
- Introduction to logic and basic theorem proving
The corresponding competences:
The objective of this course is to acquaint students in Apllied Computer Science with the formal background of their discipline.
- Knowledge and Insight:
- The student knows the Chomsky hierarchy of formal languages, and has insight in the generative power of the different classes and their corresponding automata.
- The student has gained insight into what problems can be can be solved and computed w.o.w. which problems belong to the class of (semi-)decidable or (semi-)computable problems.
- The student has sufficient knowledge about logic in order to be able to learn other types of logic.
- The use of Knowledge and Insight:
- The student can specify a grammar or an automaton of the appropriate class given an description of a previously unseen language.
- The students knows the basics of logic, more in particular proposition logic and predicate logic, so that they are able to use this knowledge to formulate and solve problems.
The student can present the content of their final project to the other students and communicate his ideas on the solutions.
- The course contributes to development of the skills necessary to solve mathematically formulated problems.
The majority of students in this program have a technological background and lack grounding in the fundamentals of computer science.
All detailed and official information about the course here >