Ementa: Conceitos básicos: conjuntos, lógica, símbolos, cadeias, linguagens. Linguagens regulares: gramáticas regulares, expressões regulares e autômatos finitos. Linguagens livres de contexto: gramáticas livres de contexto, árvores de derivação, autômatos à pilha. Lema do bombeamento. Linguagens sensíveis ao contexto e recursivamente enumeráveis: máquinas de Turing. Tese de Church-Turing. Decidibilidade e complexidade.