The aim of the course is twofold: the first is to show how algebraic methods are used in characterizing certain automata and languages in the Chomsky hierarchy, the second one is to show how to use typical tools in automata theory to face certain algebraic problems in group and semigroup theory.

The timetable of the two parts will depend on the background and interests of the students attending the course. Roughly the course will be structured as follows:

1. Basic concepts: foundamentals of semigroups, groups. Cayley graphs, free groups and presentation of groups, Dehn’s algorithmic problems is groups and semigroups. (4 hours).
2. Finite automata, regular languages, syntactic monoid of a language, rational and recognizable languages, Schutzenberger’s theorem on star free languages. The “passepartout” of several undecidability results: the Post correspondence problem and the equalizer of two morphisms. (6 hours)
3. A glimpse of automata methods in group and semigroup theory: Stallings’s construction, the Nielsen-Schreier theorem. An outline to the word problem for free inverse semigroups and groups. (4 hours)
4. Automata groups: the Burnside problem and the Grigorchuck’s group (6 hours)
5. Growth of groups and the Grigorchuck’s group, and some mentions to amenability of groups, paradoxical decompositions, random walks on groups (5 hours)