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 2022

The mode of offering for this course is currently augmented learning type 2 or 3, for lectures and tutorials. In practise, all lectures will be face to face and tutorials will be online. 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, in CS committee room only (not online))
Friday 12h00 to 14h00 (tutorial, on Teams only)

Prescribed text

All material to be provided.