Faculdade Anhanguera de Taubaté – Ciência da Computação
Teoria
da
Computação
Aula
Prof. Fabiano Sabha
1
1
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Conteúdo
 Introdução e Conceitos Básicos
 Alfabeto;
 Cadeia de símbolos, palavra;
 Linguagem formal;
 Palavras e Subpalavras;
 Concatenações;e
 Exercícios de Fixação.
Prof. Fabiano Sabha
2
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
O que é Teoria da Computação?
Pode ser vista como um guia (um roteiro) que nos orienta no
sentido de informar o que pode e o que não pode ser
efetivamente computável, explicando porque, de que
forma e com que complexidade.
Neste sentido, a Teoria da Computação classifica os
problemas computacionais em três classes:
Prof. Fabiano Sabha
3
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Classes dos problemas computacionais
 Problemas Indecidíveis (ou impossíveis de serem
solucionados);
 Problemas Intratáveis (possíveis com recursos
ilimitados, porém impossíveis com recursos limitados);
 Problemas Tratáveis (possíveis de serem solucionadas
com recursos limitados).
Esta classificação engloba problemas de toda a natureza, envolvendo
desde problemas clássicos que fundamentam a teoria da computação
até problemas (ou instâncias de problemas) práticos da ciência da
computação, tais como:
Prof. Fabiano Sabha
4
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Problemas computacionais
 Existe programa para solucionar um determinado
problema?
 Qual o poder de expressão de um determinado modelo de
especificação?
 Dado um programa qualquer, ele sempre tem parada
garantida?
 Dois programas P1 e P2 são equivalentes entre si?
 Uma determinada solução é a melhor solução para um
dado problema?
 Qual o significado de um determinado programa?
 Dado um programa qualquer, este programa está correto?
Prof. Fabiano Sabha
5
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
O Propósito da Teoria da Computação
 Formalização dos conceitos de programa e de máquina
 Existem diferentes computadores, com diferentes arquiteturas, e
existem diversos tipos de linguagens de programação,
 Modelos matemáticos simples.
 Programas e máquinas são tratados como entidades distintas, mas
complementares e necessárias para a definição de computação.
Prof. Fabiano Sabha
6
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Conceitos Básicos - Conjuntos
 Conjunto é um grupo de objetos representado como uma
unidade. Os conjuntos podem conter qualquer tipo de
objeto. Esses objetos são chamados de elementos ou
membros.
 {7,21,57} – é a notação de um conjunto que contem os
elementos ou membros 7, 21, e 57, a ordem não importa.
 Alguns símbolos :
 Pertence e não Pertence
 Subconjunto e Subconjunto próprio
 União
 Interseção
Prof. Fabiano Sabha
7
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Conceitos Básicos - Conjuntos
 Multiconjunto: Consideramos a repetição dos elementos
 Conjunto Finito: Contém uma quantidade finita de elementos
 Conjunto Infinito: Contém uma quantidade infinita elementos
 Conjunto Vazio: conjunto sem elementos
 Conjuntos “elementares”
 Conjunto dos números naturais
 {1,2,3...}
 Conjunto dos números inteiros
 {...,-2 ,-1,0,1,2...}
Prof. Fabiano Sabha
8
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Conceitos Básicos - Alfabeto
 Para o nosso propósito definimos um ALFABETO como
podendo ser qualquer conjunto finito não vazio.
 Normalmente usamos a letra grega ∑ (sigma) para
designar alfabetos, como nos exemplos abaixo:
 ∑ = {0,1}
 ∑ = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,x,z}
Prof. Fabiano Sabha
9
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Cadeia de Símbolos, palavra
 Uma Cadeia de Símbolos sobre um conjunto é uma
seqüência de zero ou mais símbolos (do conjunto)
justapostos.
 Uma Cadeia de Símbolos Finita é usualmente denominada
de Palavra.
 ε (epsilon) Representa uma cadeia ou palavra vazia.
 Se ∑ representa um conjunto de símbolos (um alfabeto),
∑ * denota o conjunto de todas as palavras
possíveis sobre ∑;
∑+ denota ∑* - {ε}
Prof. Fabiano Sabha
10
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Comprimento ou Tamanho de uma Palavra.
 O Comprimento ou Tamanho de uma palavra w,
representado por |w|, É o número de símbolos que
compõem a palavra.
Exemplos:
|011| = 3
| | = 0
|abba| = 4
 Palavra de comprimento zero = palavra nula = 0;
Prof. Fabiano Sabha
11
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Prefixo, Sufixo e Subpalavra
 Um Prefixo (respectivamente, Sufixo) de uma palavra é
qualquer seqüência inicial (respectivamente, final) de
símbolos da palavra. Uma Subpalavra de uma palavra é
qualquer seqüência de símbolos contígüa da palavra.
Exemplos:
abcb é uma palavra sobre o alfabeto {a, b, c};
Qualquer prefixo ou sufixo de uma palavra é uma sub-palavra.
Se ∑ = {a, b}, então:
∑ + = {a, b, aa, ab, ba, bb, aaa,...}
 , a, ab, abc, abcb são os prefixos;
 , b, cb, bcb, abcb são os respectivos sufixos.
Prof. Fabiano Sabha
12
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
SubPalavras
 Subpalavra = Qualquer cadeia finita de símbolos de
constante em W.
 Uma palavra x é subpalavra de y e escrevemos x<<y.
 Se existirem palavras u e v tal que u
x
v= y
 Exemplo:
A) 415 << 415  u =0 ; v = 0;
B) 755 << 37554  u = 3; v =4;
Prof. Fabiano Sabha
13
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Concatenação
 A Concatenação de Palavras é uma operação binária,
definida sobre uma linguagem L, a qual associa a cada par
de palavras uma palavra formada pela justaposição da
primeira com a segunda tal que:
 é associativa; v(wt) = (vw)t = vwt
 possui elemento neutro à esquerda e à direita, o qual é a
palavra vazia. ε w = w = w ε
Prof. Fabiano Sabha
14
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Concatenação
 Exemplos:
 Suponha o alfabeto ∑ = {a, b}.
Então, para as palavras v = baaaa e w = bb, tem-se que:
a) vw = baaaabb
b) v ε = v = baaaa
c) w4 = bbbbbbbb (concatenação sucessiva)
 35
8 = 358
e
cas
e
x
a = casa
Note que:
0
x =x
Prof. Fabiano Sabha
0=x
15
(y
z) = (x
y)
Teoria da Computação
z
Faculdade Anhanguera de Taubaté – Ciência da Computação
Linguagem Formal
 Uma Linguagem Formal ou simplesmente Linguagem
é um conjunto de palavras sobre um alfabeto.
Exemplo
 Suponha o alfabeto ∑ = {a, b}. Então:
a) O conjunto vazio e o conjunto formado pela palavra vazia
são linguagens sobre ∑. Obviamente, { } ¹ { e }.
b) O conjunto de palíndromos (palavras que têm a mesma
leitura da esquerda para a direita e vice-versa) sobre å é
um exemplo de linguagem infinita.
e, a, b, aa, bb, aaa, aba, bab, bbb, aaaa,...
Prof. Fabiano Sabha
16
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Exercícios de Fixação
 Com suas palavras defina conjunto:
 Defina:
 Multiconjunto:
 Conjunto Finito:
 Conjunto Infinito:
 Conjunto Vazio:
 O que é uma cadeia de símbolos?
 O que é um alfabeto?
 Defina subpalavra.
Prof. Fabiano Sabha
17
Teoria da Computação