Modelos de Computação

Código:

CC218

Sigla:

CC218

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2009/2010 - 2S

Ativa?	Sim
Página Web:	http://www.ncc.up.pt/%7Ervr/MC.09/MC0910.html
Unidade Responsável:	(X) Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Geologia

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:AST	0	Plano de Estudos a partir de 2008	3	-	5	49	135
L:B	0	Plano de estudos a partir de 2008	3	-	5	49	135
L:CC	69	Plano de estudos de 2008 até 2013/14	2	-	5	49	135
L:F	0	Plano de estudos a partir de 2008	3	-	5	49	135
L:G	0	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	5	49	135
		P.E - estudantes com 1ª matricula em 09/10	3	-	5	49	135
L:M	0	Plano de estudos a partir de 2009	3	-	5	49	135
L:Q	0	Plano de estudos Oficial	3	-	5	49	135
MI:ERS	76	Plano de Estudos a partir de 2007	2	-	5	49	135

Língua de trabalho

Português

Objetivos

Introdução ao estudo das linguagens formais. Pretende-se que o aluno seja capaz de especificar linguagens formais usando formas de descrição alternativas e determinar a sua classificação na hierarquia de poder computacional.

Programa

Noção de linguagem formal. Autómatos finitos determinísticos e não determinísticos. Expressões regulares e autómatos finitos. Propriedades das linguagens regulares. Minimização de autómatos finitos. Lema da repetição para linguagens regulares. Linguagens e gramáticas independentes de contexto. Árvores de derivação. Ambiguidade. Simplificações de gramáticas independentes de contexto e formas normais. Propriedades das linguagens independentes de contexto (LIC). Lema da repetição para LICs. Máquinas de Turing e noção de computabilidade.

Bibliografia Obrigatória

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006. ISBN: 0-321-47617-4
Dexter C. Kozen; Automata and Computability, Sringer, 1997. ISBN: ISBN 0-387-94907-0
Mark V. Lawson; Finite Automata, Chapman & Hall/CRC, 2004. ISBN: 1-58488-255-7

Tipo de avaliação

Avaliação por exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	49,00
	Total:	-	0,00