Plano de Curso
DCE 130 - Linguagens Formais e Autômatos
PROFESSOR
SEMESTRE
Humberto César Brandão de Oliveira
2008/1
Ementa
O curso de Linguagens Formais e Autômatos (LFA) é dado para alunos do curso de
graduação em Ciência da Computação (bacharelado) e abrange os seguintes temas:
1. Classificação das Gramáticas;
2. Propriedades das Gramáticas;
3. Autômatos;
4. Linguagens Formais;
5. Decidibilidade.
Programa
1. Conceitos Preliminares:
a. Grafos;
b. Linguagens Formais;
c. Gramáticas.
2. Linguagens Formais:
a. Linguagens regulares:
b. Expressões regulares;
c. Gramáticas regulares;
d. Autômatos finitos;
e. Propriedades.
3. Linguagens livres do contexto:
a. Gramáticas livres do contexto;
b. Autômatos de pilha;
c. Propriedades.
4. Linguagens sensíveis ao contexto:
a. Gramáticas sensíveis ao contexto;
b. Autômatos linearmente limitados;
c. Propriedades.
5. Linguagens recursivamente enumeráveis:
a. Gramáticas irrestritas;
b. Máquinas de Turing;
c. Linguagens recursivas;
d. Propriedades.
6. Decidibilidade:
a. Problemas de decisão;
b. Tese de Church-Turing;
c. O problema da parada;
d. Máquina de Turing universal;
e. Redutibilidade;
f. Exemplos de problemas indecidíveis.
Texto
O programa será desenvolvido com base no livro-texto:
• Introdução aos Fundamentos da Computação, Pioneira Thomson Learning,
2006. Autor: Newton Vieira.
O aluno pode se basear na apostila:
• Fundamentos Teóricos da Computação, UFMG, 2002. Autor: Newton Vieira.
Leitura adicional
•
•
Linguagens Formais e Autômatos, Sagra Luzzatto, 2004 (4ª. ed). Autor:
Menezes, P. B.
Hopcroft, J.E., Motwani, R., Ullman, J.D. Introduction to Automata Theory,
Languages and Computation, 2nd ed., Addison-Wesley, 2001.
Distribuição dos pontos
A distribuição de pontos da disciplina será feira segundo a Tabela 1.
Tabela 1 – Tabela de distribuição de pontos
Avaliação
Lista 1
Lista 2
Lista 3
Prova 1
Prova 2
Prova 3
Trabalho prático 1
Trabalho prático 2
Seminário
Tipo
Individual
Individual
Individual
Individual
Individual
Individual
Individual
Individual
Em grupo
Pontos
5,00
5,00
5,00
20,00
20,00
20,00
7,50
7,50
10,00
Sobre as listas de exercícios:
• As listas serão disponibilizadas no site com no mínimo uma semana de
antecedência das provas e elas deverão ser entregues no dia da prova.
• O adiamento na entrega de cada lista de exercícios pode ser feito por no
máximo uma aula acarreta na perda de 50% do valor da lista de exercícios.
Sobre as provas:
• Cada prova tem caráter de avaliação individual;
• Antes de cada prova deve ser entregue a lista de exercícios referente a matéria
da prova.
Sobre os trabalhos práticos (TP):
• Os temas dos trabalhos práticos serão divulgados no site;
• Cada trabalho prático tem caráter de avaliação individual;
• Cada trabalho prático deve ser implementado em linguagem de programação
divulgada no site;
• Havendo cópia entre alunos, ambos perdem a nota de todo o TP;
• A entrega do TP deve seguir os moldes divulgados no site;
• Havendo atraso na entrega do trabalho, serão perdidos 20% da nota total para
cada dia. Exemplos: 1 dia de atraso, 20%; 3 dias de atraso, 60%; 5 dias de
atraso, 100%;
• A pontuação dada a cada trabalho será baseada em regras definidas no site.
• Para cada TP é necessário entregar um relatório sobre o tema. Sugestão: 3
páginas A4.
• O relatório terá peso de 30% na nota do TP.
Sobre o seminário:
• A quantidade de pessoas em cada grupo será definida pelo professor (baseado
nas aulas disponíveis para apresentações e no número de alunos matriculados);
• A apresentação de cada grupo deverá ser programada para 30 minutos;
• A nota é composta de uma avaliação individual e de uma avaliação do grupo
(boa separação do tema e seqüência nas apresentações).
• Os temas devem ser sugeridos pelos alunos devem ter aprovação do professor;
• O professor deve aprovar o tema sugerido pelo grupo com no mínimo uma
semana antes da apresentação. Caso contrário, 20% da nota do grupo será
perdida.
• O seminário ocorre dependendo da quantidade de aulas livres antes do fim do
semestre. No caso do cancelamento dos seminários, os pontos serão
proporcionalmente distribuídos nos trabalhos práticos.
Comentários gerais:
• Para cada prova, será assumido que o aluno domina o assunto relativo aos
capítulos anteriores aos marcados para a prova. Assim, na formulação das
questões poderão ser utilizados conceitos e terminologias de assuntos cobertos
em provas anteriores.
• Durante as aulas poderão ser propostos outros exercícios, provas ou quaisquer
outros tipos de atividades valendo pontos extras ou para substituir itens da
avaliação normal. No entanto, o professor não vai se preocupar em divulgar
para alunos faltosos quaisquer destas atividades. Assim, pode ser conveniente
que o aluno procure saber o que ocorreu nas aulas de que não tenha
participado.