Chomsky Hierarchy in groups

The Chomsky Hierarchy classifies formal languages in four types, according to the automata which generates them. An analogous hierarchy can be built for groups by relating properties of the groups with properties on their language of the Word Problem. The first two steps of such hierarchy were built with the results from Anisimov and from Muller & Schupp, the first stating that a group is finite if and only if it is a regular group; the second stating that a group is virtually free if and only if it is context-free. The next step is currently believed to have relation with co-context-free groups.

In this talk we introduce some automata theory, defining the Chomsky Hierarchy for languages and giving the main properties of regular and context-free languages, in order to present Anisimov’s, Herbst’s and Muller & Schupp’s theorems. After that, we give some important closure properties of the co-context-free groups, as well as some examples. We finish stating the still open conjecture from Lehnhert about co-context-free groups.