Teoria da Computação
(BBC244)
Professor: Anderson Almeida Ferreira
[email protected]
http://www.decom.ufop.br/anderson
Sala COM 10
DECOM-UFOP
Ementa
• Gramáticas.
• Linguagens.
• Operações com Linguagens.
• Propriedades de Linguagens.
• Autômatos Finitos.
• Autômatos de Pilha.
• Máquinas de Turing.
• Hierarquia de Chomsky.
• Tese de Church.
• Problemas Indecidíveis.
Objetivos
• Ao final do curso é esperado que os
alunos:
– Compreendam as definições e propriedades
de modelos matemáticos de computação, tais
como, linguagens, autômatos e gramáticas.
– Compreendam os conceitos de
computabilidade e decidibilidade de
problemas.
Programa do Curso
1. Conceitos Preliminares
2. Maquinas de Estados Finitos
3. Autômatos com Pilha
4. Maquinas de Turing
5. Tese de Church
6. Problemas Indecidíveis
Teoria da Computação
• Explora alguns modelos teóricos de
computação, que estão diretamente
relacionados aos computadores que
usamos atualmente, abordando os
seguintes tópicos:
1. Teoria de autômatos
2. Gramáticas
3. Algoritmos
4. Linguagens Formais
Teoria de autômatos
• Estuda máquinas abstratas para
computação. Vários modelos são
estudados, cada um com diferentes
habilidades e limitações.
• OBJETIVO: Descrever precisamente o
poder computacional de cada máquina.
Gramáticas
• Consiste de um conjunto de regras que
determina o que é e o que não é sintaticamente
correto.
• Exemplo em português: “Eu livros leio”
– Viola a gramática portuguesa.
• Exemplo Java:
public class Wrong {
private x int
}
– Viola a especificação da linguagem Java
Gramáticas
• OBJETIVO: Podemos automatizar o
processo de encontrar erros sintáticos,
transformando uma especificação na
forma de uma gramática em um programa
de Computador?
• Em caso afirmativo, qual dos modelos de
computação estudados na Teoria de
Autômatos é adequado para tal situação?
Algoritmos
• Dada a especificação de problemas, tais como:
– Somar dois números
– Determinar se um string é um palíndromo
– O problema do caixeiro viajante
• Que autômato é capaz de resolver o problema?
Que gramáticas podem descrever o problema?
Existem problemas que não são solúveis por
quaisquer computadores, ou que não podem ser
formalmente descritos? ...
Linguagens formais
• Servem como a ligação entre essas três
perspectivas.
• Definição preliminar: Uma linguagem
formal é um conjunto de strings.
– Java é o conjunto de todos os programas
Java que compilam.
Linguagens formais
• Teoria de autômatos: Computadores são
definidos de modo a agir puramente sobre
strings e portanto, definir determinadas
linguagens.
• Gramáticas: Gramáticas especificam
linguagens, por meio de regras que derivam um
subconjunto de todos os strings de um alfabeto
• Linguagens: Conjunto de strings definidos sob
um alfabeto.
Visão geral
• Autômatos, gramáticas e linguagens são
explorados simultaneamente ao longo de
modelos computacionais:
– Autômatos Finitos
– Autômatos com Pilha (Pushdown Automata)
– Máquinas de Turing
Hierarquia de Chomsky
Todas
Recursiva
Livre de Contexto
Regular
Finita
Teoria vs. Prática
• Esse é um curso eminentemente teórico
– Definições/Exemplos/Teoremas/Provas.
– Todos os objetos estudados são de natureza
matemática.
– Nenhuma programação: exceto o uso de
algumas ferramenta simples.
Teoria vs. Prática
• Então porque esse curso?
– Toda área científica requer fundamentação teórica
sólida
– Modelos teóricos refletem a essência de situações
reais ou práticas
• Mas qual a utilidade na prática?
– Reconhecimento de padrão, detecção de intrusão,
engenharia de software (UML), programação GUI
(event-listeners), segurança em redes (protocolos),
verificação formal (descoberta de erros em chips),
processamento de linguagem natural, computação
genômica (sequenciamento de DNA), implementação
de compiladores, definição de documentos, etc.
Bibliografia
• M. SIPSER, Introduction to the Theory of Computation,
PWS Publishing Company, 1996.
• N. J. VIEIRA, Introdução aos Fundamentos da
Computação, Pioneira Thomson Learning, 2006.
• T. A. SUDKAMP, Languages and machines: an
introduction to the theory of computer science, Pearson
Education, 2006.
• J. E. HOPCROFT, R. MOTWANI, J. D. ULLMAN,
Introduction to Automata Theory, Languages and
Computation, 3/e, Pearson Education, 2006.
• Daniel I. A. Cohen, Introduction to Computer theory,
Willey, 1997.
Avaliação
• 3 provas
– 30 pontos cada
• Exercícios – 10 pontos
