CTC34 - Automata e Linguagens Formais 2009

Nova página de CTC34 (notas de aula, calendário, etc) em https://tidia.ita.br/portal

Descrição

Este curso cobre os fundamentos teóricos da Ciência da Computação. A Teoria de Linguagens Formais é a base para a definição das linguagens de programação usuais e para o projeto de compiladores, e os Automata são máquinas abstratas que computam funções e reconhecem as propriedades sintáticas destas linguagens.

Bibliografia Básica

	HOPCROFT, J., ULLMAN, J. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
	SUDKAMP, T. Languages and Machines. Addison-Wesley, 1997.
	SIPSER, M. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

	aula 1  Motivação, bibliografia, orientações gerais - Teoria da Computação: Visão Geral - Teoria dos Conjuntos - Grafos e árvores - Provas - Strings, alfabetos e linguagens - Definições recursivas e com operadores
	aula 2   Automata finitos: definição e exemplos - Automata finitos e máquinas de estados - Linguagens regulares - AFs não-determinísticos - AFs e expressões regulares
	aula 3  AFs bidirecionais - Máquinas de Mealy e Moore - Propriedades das Linguagens regulares - Lema do bombeamento (Pumping Lemma) para linguagens regulares
	aula 4 Algoritmos de decisão para AFs - Minimização de AFs
	aula 5  Gramáticas: definições e exemplos - Derivações e árvores de derivação - A hierarquia de Chomsky - Tipos de gramáticas - Gramáticas regulares e AFs - Normalização de GLCs - Formais normais de Chomsky e Greibach
	aula 6  Análise sintática para GLCs - Gramáticas ambíguas - Métodos de análise top-down e bottom-up
	aula 7   Automata de pilha: definições e exemplos - APs e linguagens livres de contexto - Lema do bombeamento (Pumping Lemma) para linguagens livres de contexto - Propriedades das linguagens livres de contexto
	aula 8  Máquinas de Turing - Linguagens e MTs - MTs e funções inteiras - Linguagens recursivamente enumeráveis - Projeto de MTs - Variações da MT
	aula 9   Linguagens recursivas - Problemas de decisão - Hipótese de Church - O problema da parada em MTs
	aula 10    Redução de problemas - Teorema de Rice - O Problema de Correspondência de Post e as GLCs

	Alan M. Turing: o "pai" da Teoria da Computação. Em sua homenagem foi criado o Prêmio Turing, um verdadeiro prêmio Nobel para os "computeiros".
	Noam Chomsky: um dos grandes nomes no estudo de gramáticas e linguagens.
	O pumpíng lemma na forma de poema...
	O problema da parada em MTs na forma de poema...