Course for international guest/part time students
- Faculty
- Faculty of Humanities
- Organization
- BTK Institute of Philosophy
- Code
- BMI-LOTD-328E.07
- Title
- Proof theory I: Formal languages and automata
- Usual semester
- Autumn
- ECTS
- 4
- Language
- Learning outcomes
- Knowledge: - Learning the basic mathematical concepts, theorems, and tools related to formal languages, automata, and formal grammars Skills: - Acquiring skills related to formal methods: understanding and producing proofs, definitions, and algorithms - Understanding the formal modeling of natural language: recognizing parallels and differences between formal languages and natural languages, and between concepts related to formal languages and those related to natural languages Attitude: - Open attitude toward analyzing natural languages using formal tools Autonomy: - Independent understanding of formal methods and linking them to natural language concepts Responsibility: - Knowing the limitations of certain formal methods and applying them to natural languages with care
- Course content
- - Finite-state automata, regular operations - Regular expressions, Kleene’s theorem - Non-regularity: pumping lemma, Myhill–Nerode theorem - Context-free grammars, pushdown automata - CYK parsing algorithm - Non-context-freeness: Bar-Hillel lemma - Formal properties of natural language phenomena - Context-sensitive and tree-adjoining (TAG) grammars - Turing machines, uncomputability - Complexity, reducibility, NP-completeness - Probabilistic automata and grammars - Learnability of formal languages
- Assessment method
- Ways to earn points: - Submission of homework every week (3 points per week) - One written midterm test (5 points once) Grading based on the percentage of total points achieved: - From 80%: grade 5 - From 70%: grade 4 - From 60%: grade 3 - From 50%: grade 2
- Bibliography
- - Sipser (2013): Introduction to the theory of computation
- Recommended bibliography
- - Sipser (2013): Introduction to the theory of computation