DM15 Syllabus

• Functional programming in Miranda • Relgular languages

– Regular sets

– Regular grammars

– Finite automata

– Pumping lemma

• Context-free languages – Context-free grammars

– Parsing of context-free grammars (general introduction)

– Pushdown automata

– Pumping lemma

• Context-sensitive languages and LBAs • Computability

– Phrase structure grammars

– Turing machines

– Recursive sets

– Recursively enumerable sets

– Undecidability

– Uncomputable functions

– Primitive recursive functions

– μ-recursive functions

• (Typed) lambda calculus – Lambda notation

– Currying

– Reductions (types of and orders of)

– Recursion and fixed-point operators