Linguagens Formais: A hierarquia de Chomsky

As várias classes de linguagens formais são classificadas numa hierarquia, proposta pelo linguista Noam Chomsky. Nesta apresentação, falarei dos vários formalismos para representação de linguagens formais, incluindo gramáticas e autómatos, e da forma como se relacionam. As linguagens regulares serão abordadas de uma forma mais aprofundada, com a introdução da álgebra das expressões regulares. No final da apresentação, mostrarei a utilização do Otter, um sistema de demonstração automática de teoremas, para demonstrar alguns resultados da álgebra das expressões regulares.