Seminário de Álgebra - "A Hierarquia de Chomsky em Grupos"

The Chomsky Hierarchy classifies languages in four types (0 to 3): recursively enumerable, context sensitive, regular and context free ones. Studying these languages allows one to define corresponding types of groups, where some properties will be strongly associated with properties of the language. In this talk we will define the types 2 and 3 languages, introducing graphs and automata, and will see which groups they characterize with Anisimov’s, Herbst’s and Muller & Schupp’s theorems. This results will lead to the construction of an analogous hierarchy classifying groups and we end presenting the still open conjecture from Lehnert about co-context free groups.