Aspectos Teóricos da
Computação
Prof. Luiz Fernando R B Corrêa
O Professor




Mestre em Engenharia de Software –
CESAR.EDU
Especialista em Planejamento e Gestão
Organizacional – FCAP/UPE
Especialista em TI – CIN/UFPE
Graduado em Ciência da Computação UNICAP
Durante as aulas

Não conversar

Participar das discussões e exercícios

Celulares desligados ou no silencioso
(exceções)

Pontualidade

Assiduidade
Faltas



Máximo 25% das aulas
Justificativa até a aula seguinte ou 7
dias úteis. O que ocorrer primeiro
Depois do prazo de justificativa de
faltas, só com a secretaria/coordenação
Chamada

No fim de cada aula
Cargas Horárias


Semanal: 3 horas-aula
Semestral: 66 horas-aula
Horário

Terças-feiras



Primeira Aula: 19:10h - 20:25h
Intervalo: 20:25h – 20:40h
Segunda Aula: 20:40h - 21:55h
Ementa

Elementos de linguagens formais,
cadeias, alfabetos, linguagens,
gramáticas e reconhecedores.

Hierarquia de Chomsky.

Expressões regulares.

Autômatos finitos determinísticos e
não determinísticos.
Objetivos Gerais

Ao término desta disciplina o aluno
deverá conhecer:

Tipos de linguagens, as gramáticas que
as geram e os autômatos que as
reconhecem. Visando a especificação /
implementação de linguagens de
programação.
Objetivos Específicos

Fornecer ao aluno subsídios para que o
mesmo possa definir linguagens de
programação, isto é, sua sintaxe e
semântica, através do estudo das
gramáticas formais. De tal forma que o
mesmo passe a conhecer o processo de
especificação e implementação de
linguagens de programação, a partir do
estudo dos conceitos, modelos, técnicas
e ferramentas que compõem a Teoria
das Linguagens Formais.
Conteúdo Programático

Fundamentos Matemáticos




Tipos de relações em conjuntos
Fecho de uma relação
Grafos bidirecionais.
Conceitos Básicos de Linguagens




Alfabetos
Palavras sobre um alfabeto
Linguagens
Gramática Irrestrita: definição, regras
de produção e derivação.
Conteúdo Programático

Gramática Sensível ao Contexto.

Gramáticas Livres de Contexto

Linguagens Livres de Contexto.


Árvores de derivação
Ambigüidade.
Conteúdo Programático

Linguagens Regulares





Autômatos finitos determinísticos e nãodeterminísticos
Expressões regulares
Técnicas para identificar e descrever
linguagens regulares
Técnicas para mostrar que uma linguagem
não é regular
Propriedades de tais linguagens.
Estratégia de Trabalho


Aulas expositivas seguidas de
desenvolvimento de exercícios
práticos.
Lista de exercícios/projetos para
serem resolvidas fora da sala de
aula para fixação dos assuntos
abordados nas aulas expositivas.
Avaliação

Média das provas bimestrais com a
nota das listas de exercício/projetos.

O conteúdo das provas será baseado no
que foi visto em sala de aula.
Bibliografia
Básica



LEWIS, Harry R. & PAPADIMITRIOU, Christos H.
Elementos de Teoria da Computação. 2.ed.
Porto Alegre, Bookman, 2000.
MENEZES, Paulo Blauth. Linguagens formais
e autômatos. 2.ed. Porto Alegre, Sagra
Luzzatto, 1998. 165p.
HOPCROFT, JOHN E.; ULLMAN, Jeffrei D.;
MOTWANI, Rajeev; Introdução À Teoria de
Autômatos, Linguagens e Computação; 2002;
Ed Campus.
Bibliografia
Complementar





DIVERIO, T. A. E Menezes, P.B. Teoria da Computação
Máquinas Universais e Computabilidade, Série Livros Didáticos
Número 5, Instituto de Informática, da UFRGS, Editora Sagra
Luzzatto, 1a edição, 1999.
BRAINERD, W. S.; Landweber, L. H. Theory of computation.
New York: John Wiley & Sons, 1974.
SIPSER, Michael; Introdução à Teoria da Computação; 2007;
Ed. Thomson Pioneira.
LEWIS, HARRY ; PAPADIMITRIOU, Christos H.; Elementos de
Teoria da Computação; 2a Ed 2004; Ed BOOKMAN
COMPANHIA.
BLAUTH, Paulo; HAPULER, Edward Hermann; Teoria das
Categorias para Ciência da Computação.
Bibliografia
Suporte

Wikipedia: http://www.wikipedia.org

Scribd: http://www.scribd.com
Aluno








Nome
Expectativa
Trabalha? Com que?
Programa?
Inglês?
Período
Já pagou a disciplina de Grafos?
Já pagou a disciplina de Lógica?
O que é?
Computação

WordNet



the procedure of calculating; determining
something by mathematical or logical
methods
problem solving that involves numbers or
quantities
Houaiss

cômputo, cálculo, contagem; operação
matemática ou lógica realizada por regras
práticas preestabelecidas
O que é?
Computação

Wikipedia

Solução de um problema ou, formalmente,
o cálculo de uma função, através de um
algoritmo
O que é?
Ciência da Computação

Sabha

conhecimento sistematizado relativo à
computação
 O estudo das bases e modelos que
fundamentam o funcionamento de
processamentos computacionais.
O que é?
Teoria da Computação

Sub-campo da ciência da computação
(CC) e matemática, que busca
determinar quais problemas podem
ser computados em um dado modelo
de computação.

Fundamentação teórica para a CC

Tratamento matemático da CC
O que é?
Teoria da Computação: Contextualização

Questões Centrais



Quais as capacidades e limitações
fundamentais dos computadores?
O que pode e o que não pode (problema)
ser resolvido por computadores?
O que faz alguns problemas serem
computacionalmente mais difíceis que
outros?
O que é?
Teoria da Computação: Contextualização

Áreas Centrais

Teoria dos Autômatos


Teoria da Computabilidade


definição e propriedades de modelos
matemáticos de computação
tese de Church-Turing (algoritmos),
decidibilidade e indecidibilidade
Teoria da Complexidade Computacional

classificação de problemas como fáceis ou
difíceis (polinomiais x exponenciais).
Tipos de Problemas


Não-Tratáveis: Não existe algoritmo
que resolva o problema.
Tratáveis: Existe um algoritmo que
resolve o problema.
Como começou ?

Com as perguntas:
1.
COMO ? (as linguagens são definidas)
Estudo de gramáticas de Noam Chomsky
Fonte: HARA, 2009
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o
que é um algoritmo?)
I.
O algoritmo deve ser completo, finito e
determinístico.
 completo: sempre produz um resultado
 finito: tem uma seqüência finita de
instruções
 determinístico: sempre produz o
mesmo resultado para a mesma
entrada
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o
que é um algoritmo?)
II. necessidade de um modelo formal e
abstrato de computação
III. Exemplo: funções recursivas, cálculo
lambda, máquinas RAM, máquinas de
Turing (provado que são todos
equivalentes)
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o
que é um algoritmo?)
IV. Hipótese de Church-Turing: um problema
tem uma solução algorítmica se, e
somente se, pode ser resolvido por um
dos sistemas computacionais
mencionados na transparência anterior
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o
que é um algoritmo?)
V. Problemas com solução computacional ou
sem solução computacional
IV.


Exemplo de problemas sem solução:
Determinar se um programa termina para
todas as entradas possíveis
Determinar se dois programas computam a
mesma função
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o que
é um algoritmo?)
Um Modelo de Computação: Máquina Abstrata.
Deve capturar aspectos relevantes
O
conj. de símb. para representar dados é finito (fin).
Cada dado é representado de forma fin.
A ação a ser executada em cada momento é
determinada com base no dado que está sendo
observado e no estado interno.
Cada ação é executada mecanicamente, em tempo
fin.
O núm de possíveis estados internos distintos é fin.
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o que
é um algoritmo?)
Um Modelo de Computação: Máquina Abstrata.
E abstrair aspectos irrelevantes
A
velocidade de execução.
A capacidade da memória.
Como começou ?
Continuação
2.
O QUE ? (o que conseguimos computar? o que
é um algoritmo?)
Um Modelo de Computação
Deve ser tão simples quanto possível
Conj.
de símbolos para representar dados: {0; 1}.
Apenas 1 símbolo é observado de cada vez.
Uma ação consiste simplesmente em:
ler um símbolo
Verificar o estado atual
mudar o estado interno
mudar a posição de leitura do próximo símbolo
Um estado interno pode ser um estado de parada.
Como começou ?
3.
QUANTO CUSTA? (computar)
 problemas tratáveis ou intratáveis
 Ex: intratáveis (tem solução com
recursos ilimitados): computar todas
as possíveis jogadas de xadrez com
1000 movimentos
Histórico/Evolução

O que os computadores podem
calcular? (~1930)


~1935




Resposta necessitava de um modelo
formal de computabilidade
Kurt Göedel : funções μ-recursivas
Alonso Church: λ-Calculus
Alan Turing: Máquina de Turing
~1940 - Baseado nessas e em
outras idéias foram construídos os
primeiros computadores
Exemplos de Aplicação



Análise léxica e análise sintática de
linguagens de programação
Modelagem de circuitos lógicos ou
redes lógicas
Modelagem de sistemas biológicos
Sintaxe e Semântica

Linguagens Formais


problemas sintáticos das linguagens
Sintaxe e Semântica
Sintaxe e Semântica

Historicamente, o problema sintático


Mais simples que o semântico
Reconhecido/tratado antes do problema
semântico
Sintaxe e Semântica

Conseqüência



Maior ênfase à sintaxe
Criando a impressão que as questões
relativas às resumiam-se às questões da
sintaxe
Teoria da sintaxe possui construções
matemáticas


Bem definidas e universalmente
reconhecidas
Exemplo: Gramáticas de Chomsky
Sintaxe e Semântica

Linguagem de programação (ou
qualquer modelo matemático) pode ser
vista como uma entidade


livre, sem qualquer significado associado
juntamente com uma interpretação do seu
significado
Sintaxe e Semântica


Sintaxe
 Trata das propriedades livres da
linguagem
 Ex: verificação gramatical de
programas
Semântica
 objetiva dar uma interpretação para a
linguagem
 Ex: significado ou valor para um
determinado programa
Sintaxe e Semântica

Ou seja, a sintaxe:



manipula símbolos
Não considera os seus significados
Para problemas reais


Necessário interpretar semanticamente os
símbolos
exemplo: estes símbolos representam os
inteiros
Sintaxe e Semântica

Sintaticamente "errado“



não existe tal noção de programa
simplesmente não é um programa da
linguagem
Sintaticamente válido ("correto")

pode não ser o programa que o
programador esperava escrever
Sintaxe e Semântica

Programa "correto" ou "errado“


se o mesmo modela adequadamente o
comportamento desejado
Limites entre a sintaxe e a semântica



nem sempre são claros
exemplo: ocorrência de um nome em um
programa pode ser tratado facilmente com
um problema sintático ou semântico
entretanto, em linguagens artificiais

distinção entre sintaxe e semântica é (em
geral) óbvia para a maioria dos problemas
relevantes
Sintaxe e Semântica

Análise Léxica






tipo especial de análise sintática
centrada nas componentes básicas da
linguagem
portanto, também é ênfase das Linguagens
Formais
Processo de converter uma sequência de
caracteres em uma sequência de tokens
(símbolos léxicos)
Verifica determinado alfabeto
Vem antes da análise sintática
propriamente dita
Ferramentas

JFLAP


SCTMF


http://www.jflap.org/
http://www.din.uem.br/~yandre/sctmf/
Visual Automata Simulator

http://www.cs.usfca.edu/~jbovet/vas.html
Instalação do JFlap


Ferramenta visual usada para criar e
simular diversos tipos de autômatos, e
converter diferentes representações de
linguagens.
JFLAP JAVA Formal Language and
Automata Package http://homepages.dcc.ufmg.br/~nvieir
a/cursos/tl/a05s2/relatorio_curso.doc
Instalação do JFlap

JFLAP 7.0 Tutorial:

http://www.cs.duke.edu/csed/jflap/tutorial/
Referências
Aula







WordNet - http://wordnet.princeton.edu/
Dicionário Houaiss da Lingua Portuguesa http://houaiss.uol.com.br
Wikipedia – http://www.wikipedia.org
http://en.wikipedia.org/wiki/Theory_of_computation
CI059 - Introdução a Teoria da Computação - Segundo
Semestre de 2009 - Profa. Carmem Hara .
http://www.inf.ufpr.br/carmem/ci059/
Teoria da Computação. Prof. Fabiano Sabha.
http://www.fabianosabha.com.br
Linguagens Formais e Automatos. Prof. Eduardo Araujo
Oliveira. http://sites.google.com/site/eaoufpe/