Formalismos para descrição de linguagens. Linguagens regulares, autômatos finitos, gramáticas lineares e expressões regulares. Linguagens livres de contexto, autômatos com pilha e gramáticas livres de contexto. Máquinas de Turing e gramáticas sensíveis ao contexto. Computabilidade e decidibilidade.