Languages, automata and computations 1000-214bJAO
- Elements of formal languages: words, languages, regular expressions.
- Finite automata and the Kleene theorem on effective equivalence of finite automata and regular expressions.
- Automata optimisation constructions - determinisation, minimalisation.
- Context-free languages: grammars and their normal forms.
- Equivalence of context-free grammars and nondeterministic pushdown automata.
- Necessary conditions for regular and context-free languages: pumping lemmas.
- Algorithmic questions: emptiness and membership for automata and grammars.
- Example applications of automata and grammars.
- Universal computation models: Turing machines and variants.
- Limits of computability: undecidability of the halting problem, examples of practical undecidable problems.
-Conclusion: classification of grammars and computation models in the Chomsky hierarchy.
- Introduction to complexity theory: P and NP.
- The Cook-Levin theorem on NP-completeness of SAT.
- The P=/=NP conjecture and its practical implications, information on positive applications of hard computational problems, e.g. in cryptography.
Type of course
Requirements
Discrete mathematics
Foundations of mathematics
Introductory programming
Course coordinators
Assessment criteria
* 4 homework problems, 5 pts each.
* 8 online tests jointly for 8 pts.
* final exam for ~30 pts.
* star problems allowing students to get additional points.
To be allowed for the first-term exam, at least 14 pts are required (this threshold might be lowered).
To pass the subject, one is required to get at least 12 pts on the exam (this threshold might be lowered).
The final grade in the first term is 1/10 of the sum of all the points (rounded down to 0.5).
Second-term final exam will be resulting in a final grade (without any impact from the above score).
Bibliography
1. J. E. Hopcroft, R. Motwani, J. D. Ullman, ntroduction to Automata Theory, Languages, and Computation, Addison Wesley, 2000
2. Ch. Papadimitriou, Computational Complexity, Addison Wesley, 199
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Bachelor's degree, first cycle programme, Mathematics
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: