---

Formal Languages and Computability
INF3 Semester
Syllabus for the Course and Exam Questions

---

Key Topics Covered in the Course

• Regular Languages: (non)deterministic finite automata, conversion from nondeterministic to deterministic automata, regular expressions, equivalence between finite automata and regular expressions, closure properties of regular languages, the Pumping Lemma for regular languages, applications of the pumping lemma.

• Context-free Languages: context-free languages, context-free grammars, derivations, parse trees, Chomsky normal form.

• Computability Theory: Turing machines and their variants, decidable and recognizable languages, closure properties of decidable and recognizable languages, undecidability of A_TM, reduction between problems and how to use it to show undecidability results.

• Complexity Theory: Measuring the time efficiency of algorithms, the complexity class P, examples of problems in P, and closure properties of P. The complexity class NP, the "P=NP problem", examples of problems in NP, polynomial time reductions, and the notion of NP-completeness.

Reading Material

List of Exam Questions

1. Finite Automata: Deterministic, nondeterministic finite automata and their equivalence.
2. Regular expressions and their connection with finite automata.
3. The Pumping Lemma for regular languages and its applications.
4. Context-free grammars and closure properties of context-free languages.
5. Decidable and Recognizable Languages: Definitions and closure properties.
6. The undecidability of A_TM and HALT_TM.
7. Reduction and its use in undecidability proofs.
8. The complexity class P: Definition, examples and closure properties.
9. The complexity class NP, and the concept of NP-completeness.