This course covers more advanced topics in formal languages and automata theory. In CS345 we covered the basics of finite automata and regular languages -- here we will consider more advanced automata, such as Mealy and Moore machines, 2-way automata, and others. Moreover, we consider concepts such as the combinatorics of words, and the descriptional complexity of finite automata. Finally, we will spend some time on cellular automata.

Teaching mode in 2021

This course will be offered via augmented learning type 2 or 3, for lectures and tutorials. Assessments will be open book and online via sunLearn or git submissions.


  • Please note that this course has as prerequisite a pass mark in CS345.


Prof L van Zijl
Office: A520, General Engineering Building,
Email: lvzijl -at- cs.sun.ac.za

Meeting times

Tuesday 09h00 to 11h00 (discussion, both in CS committee room and online)
Thursday 13h00 to 15h00 (tutorial, on Teams)

Prescribed text

All material to be provided.