CS259 - Formal Languages

Table of contents

• Content & Summaries
• Reading List

Multi

Module Info

Module Webpage/Online Material/Lecture Notes

Professor: Ramanujan Maadapuzhi Sridharan
Term: 2
Status: Core
Assessment: 70% exam, 20% programming coursework, 10% class test

• Past Papers

Rating

Difficulty:
Professor:
Teaching Style:
Would take again?

Content & Summaries

Topic	Rating	Summary
Regular languages		finite automata, non-determinism, regular expressions, pumping lemma, non-regular languages, minimisation, translations between automata and regular expressions, closure properties
Context-free languages		context-free grammars, ambiguity, Chomsky normal form, pushdown automata, pumping lemma, translations between automata and grammars, closure properties
Turing-recognisable languages		Turing machines, Church-Turing thesis, decidability, reducibility, the halting problem

Reading List

Talis Aspire