Modulcode:	infAAT-01a
Englische Bezeichnung:	Algebraic Automata Theory
Modulverantwortliche(r):	Dr. Pamela Fleischmann
Turnus:	jedes Jahr im WS (WS21/22 WS22/23 WS23/24 WS24/25 WS25/26)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) TI (MSc Inf (15)) WI (MSc Inf (15))
Lehrsprache:	Englisch
Voraussetzungen:	Inf-LogInf Inf-Math-A Inf-TGI infBL-01a

Kurzfassung:

Next to the perspective of automata taught in Theoretical Computer Science, there is an algebraic way to investigate automata. Using algebraic tools, we will look into different types of automata.

Lernziele:

This lecture provides the basic approach to solve problems with abstract algebraic methods. The students obtain the ability to connect the notions of (semi) group and syntactical monoid with the notions of automata theory.

Lehrinhalte:

After a short introduction of the required fundamentals of semi groups, state machines are investigated under this new perspective. Afterwards, the question is tackled how state machines can be simulated by other state machines which includes the idea of finding a smallest equivalent state machine. Here, the holonomy decomposition is presented. Afterwards recognisers and recognisable sets are investigated. At the end Mealy machines are presented.

Weitere Voraussetzungen:

Knowledge in basic automata theory and formal languages is required (e.g. TGI or BuL-B). Moreover, the basic concepts of proving are necessary (e.g. Logik or BuL-L).

Prüfungsleistung:

Written or oral exam at the end of the semester.

Lehr- und Lernmethoden:

Slides, Whiteboard

Verwendbarkeit:

Literatur:

Algebraic Automata Theory by W.M.L. Holcombe, Cambridge University Press, 1982

Verweise:

Kommentar: