Slide 01 TCP

Prévia do material em texto

Prof. Dr. Boente, Alfredo (PhD)
alfredo.boente@live.estacio.br
COMPUTAÇÃO
Teoria da Computação
Teoria da Computação
COMPUTAÇÃO
Apresentação
• Prof. Dr. Alfredo Boente
• alfredo.boente@live.estacio.br
Teoria da Computação
COMPUTAÇÃO
Teorias e Construção do Conhecimento
• Fundamentos de Teoria da Computação;
Autômatos Finitos (AFD e AFND);
Linguagens Regulares; Linguagens Não-
Regulares; Programas, Máquinas,
Computação e Função Computada;
Máquinas Universais; Funções
Recursivas; Teoria da Computabilidade;
Complexidade Computacional;
Modificações sobre Máquinas Universais,
Estudo de Caso.
Teoria da Computação
COMPUTAÇÃO
Bibliografia Recomendada
Teoria da Computação
COMPUTAÇÃO
Critérios de Avaliação
AV1 e AV2:
• Prova ........................................... 8,0
• Trabalhos (Lista de Exercícios) ............. 2,0
AV3:
• Prova .......................................... 10,0
Teoria da Computação
COMPUTAÇÃO
Provas
• AV1 ............................................... 8,0
• AV2 ............................................... 8,0
• AV3 ............................................... 10,0
• Conteúdo AV1: Unidade 01 até unidade 05
• Conteúdo AV2: Unidade 06 até unidade 10
• Conteúdo AV3: Unidade 01 até unidade 10
Teoria da Computação
COMPUTAÇÃO
Trabalhos AV1 e AV2
• Lista de Exercícios................... 2,0
Teoria da Computação
COMPUTAÇÃO
Calendário de Provas
• AV1: 28/04/2021
• AV2: 16/06/2021
• AV3: 30/06/2021
Teoria da Computação
COMPUTAÇÃO
AULA 1:
Fundamentos de
Teoria da Computação
Teoria da Computação
COMPUTAÇÃO
Introdução
A teoria da computação representa um campo da ciência da
computação e matemática que busca determinar quais
problemas podem ser computados em um determinado tipo de
modelo de computação.
A computação pode ser definida como a solução de um
problema ou, formalmente, o cálculo de uma função por meio
de um algoritmo computacional. Apesar de ser intuitivo na
história humana, o conceito de execução de uma tarefa com
passos finitos a fim de se obter um resultado, ou seja, um
algoritmo, não possuía uma definição formal até a
conceituação do modelo de Máquina de Turing.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
LINGUAGEM
Linguagem é um conceito fundamental no estudo da Teoria da
Computação, pois trata-se de uma forma precisa de expressar
problemas, permitindo um desenvolvimento formal adequado
ao estudo da computabilidade.
O dicionário Aurélio define linguagem como:
"o uso da palavra articulada ou escrita como meio de
expressão e comunicação entre pessoas".
Esta definição não é suficientemente precisa para permitir o
desenvolvimento matemático de uma teoria sobre linguagens.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
As definições que seguem são construídas usando como base a
noção de Símbolo ou Caractere, que é uma entidade abstrata
básica, não sendo definida formalmente. Letras e dígitos são
exemplos de símbolos frequentemente usados.
ALFABETO
Um Alfabeto é um conjunto finito de símbolos ou caracteres.
• um conjunto infinito não é um alfabeto;
• o conjunto vazio é um alfabeto.
Os seguintes conjuntos são exemplos de alfabetos:
• {a, b, c};
• conjunto vazio.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
Os seguintes conjuntos não são exemplos de alfabetos:
• conjunto dos números naturais;
• {a, b, aa, ab, ba, bb, aaa,...}.
CADEIA DE SÍMBOLOS E PALAVRA
Uma Cadeia de Símbolos sobre um conjunto é uma sequência
de zero ou mais símbolos (do conjunto) justapostos. Uma
Cadeia de Símbolos Finita é usualmente denominada de
Palavra.
ε denota a cadeia vazia ou palavra vazia.
Se Σ representa um conjunto de símbolos (um alfabeto),
Σ* => o conjunto de todas as palavras possíveis sobre Σ;
Σ+ denota Σ* - { ε }.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
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.
PREFIXO, SUFIXO E SUBPALAVRA
Um Prefixo (respectivamente, Sufixo) de uma palavra é
qualquer sequência inicial (respectivamente, final) de
símbolos da palavra. Uma Subpalavra de uma
palavra é qualquer sequência de símbolos
contígua da palavra.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
Exemplos de Palavra, Prefixo, Sufixo, Tamanho:
a) abcb é uma palavra sobre o alfabeto {a, b, c};
b) Se Σ = {a, b}, então:
Σ+ = {a, b, aa, ab, ba, bb, aaa,...}
Σ* = {ε , a, b, aa, ab, ba, bb, aaa,...}
c) |abcb| = 4 e |ε| = 0;
d) Relativamente à palavra abcb, tem-se que:
ε, a, ab, abc, abcb são os prefixos;
ε, b, cb, bcb, abcb são os respectivos sufixos.
e) Qualquer prefixo ou sufixo de uma palavra
é uma subpalavra.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
LINGUAGEM FORMAL
Uma Linguagem Formal ou simplesmente Linguagem é um
conjunto de palavras sobre um alfabeto.
Suponha o alfabeto Σ = {a, b}.
Então:
a) O conjunto vazio e o conjunto formado pela palavra vazia
são linguagens sobre Σ. Obviamente, { } ≠ { ε }.
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.
ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa,...
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
Dados L1={r, rs} e L2=(r, sr}, linguagens sobre {s, r}.
Qual o resultado de L1L2 ?
L1L2 = {r, rs, sr}
Qual o resultado de L1L2 ?
L1L2 = {r}
Qual o resultado de L1–L2 ?
L1–L2 = {rs}
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
Dados L1={r, rs} e L2=(r, sr}, linguagens sobre {s, r}.
Qual o resultado de L1.L2 ?
L1.L2 = {r, rr, rsr, rs, rsr, rssr}
Qual o resultado de L12=L1.L1 ?
L12=L1.L1 = {rr, rrs, rsr, rsrs}
Qual o resultado de 2L1 ?
2L1 = {2r, 2rs}
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
CONCATENAÇÃO DE PALAVRAS
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:
• não necessariamente é fechada em L; a concatenação de
duas palavras de uma linguagem não necessariamente resulta
em uma palavra da linguagem.
• é associativa; v(wt) = (vw)t = vwt
• possui elemento neutro à esquerda e à direita, o qual é a
palavra vazia. ε w = w = wε
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
Suponha o alfabeto Σ = {a, b}.
Então, para as palavras v = baaaa e w = bb, tem-se que:
• vw = baaaabb
• vε = v = baaaa
CONCATENAÇÃO SUCESSIVA DE UMA PALAVRA
A Concatenação Sucessiva de uma Palavra (com ela mesma) ou
simplesmente Concatenação Sucessiva, representada na forma
de um expoente (suponha w uma palavra):
wn onde n é o número de concatenações sucessivas, é definida
indutivamente a partir da operação de concatenação binária.
Teoria da Computação
COMPUTAÇÃO
Alfabetos e Linguagens
Veja:
w0 = ε;
wn = wn-1w, para n > 0.
Vamos a um exemplo: Sejam w uma palavra e a um símbolo.
Então:
w3 = www
w1 = w
a5 = aaaaa
an = aaa...a (o símbolo a repetido n vezes)
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
O estudo das linguagens regulares ou tipo 3, é abordado
usando o seguinte formalismo:
a) Expressão Regular: Trata-se de um formalismo
denotacional, também considerado gerador, o qual é
definido a partir de conjuntos (linguagens) básicos e das
operações de concatenação e de união;
b) Gramática Regular: Trata-se de um formalismo axiomático
ou gerador, o qual, como o nome indica, é uma gramática,
mas com restrições de forma das regras de produção.
c) Autômatos Finitos: Trata-se de um formalismo operacional
ou reconhecedor, sendo, basicamente, um sistema de
estados finitos;
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
As linguagens regulares constituem a classe das linguagens
mais simples, sendo possível desenvolver algoritmos de
reconhecimento, de geração ou conversão entre formalismo de
pouca complexidade,de grande eficiência e de fácil
implementação.
Nesta aula iremos abordar a expressão regular e a gramática
regular, deixando para a próxima aula o estudo dedicado aos
Autômatos Finitos.
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
EXPRESSÃO REGULAR
As Linguagens Regulares são classes de linguagem simples de
cunho importante para o contexto. Elas estão presentes,
direta ou indiretamente, na modelação de sistemas físicos, nos
compiladores etc. Elas são, em geral, infinitas, pelo que se
torna necessário a existência de caracterizações finitas dessa
linguagem.
Uma possibilidade é o recurso à teoria dos conjuntos, como no
exemplo: L = {anbm, n, m ≥ 0}
Estas descrições com base em conjuntos têm, no entanto, um
problema: não são operacionais.
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
EXPRESSÃO REGULAR
Elementos e instrumentos de descrição de linguagem:
- Expressões regulares
- Gramáticas regulares
- Autômatos finitos
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
Dada uma expressão regular sobre um alfabeto  se define por
indução:
Ø,  e a  a  , são expressões regulares.
Se r1 e r2 são expressões regulares, então:
r1 + r2
r1 . r2
r*1
(r1)
Também são expressões regulares.
Nada mais é uma expressão regular que não resulte
especificamente da aplicação das regras 1 e 2.
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
Existe uma relação evidente entre expressões regulares sobre
um alfabeto  e uma linguagem sobre este mesmo alfabeto.
Assim:
Teoria da Computação
COMPUTAÇÃO
Linguagens Regulares
GRAMÁTICA REGULAR
Uma gramática G = (N, T, , P) diz-se regular se e somente se
todas as suas produções forem da forma:
e diz-se que a gramática é linear à direita ou exclusivo.
e agora dizemos que é linear à esquerda. As
gramáticas regulares são utilizadas, como um exemplo prático,
em projetos de desenvolvimento de compiladores para
linguagens de programação.
Teoria da Computação
COMPUTAÇÃO
Propriedades de Linguagens Regulares
Como ilustração de uma abordagem das Linguagens Formais às
linguagens n-dimensionais, no que segue é apresentada a
noção de Gramática de Grafos.
No caso de reescrita de grafos como termos, os grafos têm que
ser necessariamente dirigidos, etiquetados e com ordenação
nas arestas, e as operações são caracterizadas sobre
uma especificação de grafo, definida como:
G = <|{1=t1, ..., n=tn}>
Teoria da Computação
COMPUTAÇÃO
Propriedades de Linguagens Regulares
Em que 1 é um par disjunto de nós (com variáveis) e ti um
termo. Também, o nó  indica a raíz do grafo.
nó raíz (  )
Teoria da Computação
COMPUTAÇÃO
Propriedades de Linguagens Regulares
A idéia básica da gramática de grafos é análoga à das
gramáticas de Chomsky, ou seja:
- regras de produção são pares (mas de grafos);
- uma derivação é a substituição de um sub-grafo de acordo
com uma regra de produção.
As gramáticas de grafos constituem um caso particular de
gramáticas das categorias.
A idéia básica é substituir palavras por grafos no conceito do
contexto.
Teoria da Computação
COMPUTAÇÃO
Lista de Exercícios
Teoria da Computação
COMPUTAÇÃO
Lista de Exercícios
Exercício 01: Dados L1={a, ab} e L2=(ε, a, ba}, linguagens
sobre {a, b}, determine:
a. L1L2
b. L1L2
c. L1–L2
d. L2–L1
e. L1.L2
f. L2.L1
g. L12=L1.L1
h. L22=L2.L2
Teoria da Computação
COMPUTAÇÃO
Lista de Exercícios
Exercício 02: Dados L1={x, xy} e L2={λ, x, yx}, linguagens sobre
Σ={x, y}, determine:
a. L1L2
b. L1L2
c. L1–L2
d. L2–L1
e. L1.L2
f. L2.L1
g. L12=L1.L1
h. L22=L2.L2
Teoria da Computação
COMPUTAÇÃO
Lista de Exercícios
Exercício 03: Prove que se uma cadeia x é prefixo de uma
cadeia y e y também é prefixo de x, então x e y são iguais.
Exercício 04: Prove que se uma cadeia x é prefixo de uma
cadeia y e y é prefixo de uma cadeia z, então x é prefixo de z.
Exercício 05: Fazer uma análise crítica sobre o filme “O Jogo
da Imitação”, às vistas da Teoria da Computação.
Teoria da Computação
COMPUTAÇÃO
Lista de Exercícios
Então, assistir o filme “O Jogo da Imitação” e fazer uma
análise crítica sobre ele às vistas da Teoria da Computação.
Sinopse: Em 1939, a recém-criada agência de
inteligência britânica MI6 recruta Alan Turing,
um aluno da Universidade de Cambridge, para
entender códigos nazistas, incluindo o "Enigma",
que criptógrafos acreditavam ser inquebrável. A
equipe de Turing, incluindo Joan Clarke, analisa
as mensagens de "Enigma", enquanto ele constrói
uma máquina para decifrá-las. Após desvendar as
codificações, Turing se torna herói. Porém, em
1952, militares revelam sua homossexualidade, e
a vida dele vira um pesadelo.
Teoria da Computação
COMPUTAÇÃO
Lista de Exercícios
Link para o filme “O Jogo da Imitação:
https://www.youtube.com/watch?v=b8d_oX9Ewok
A Máquina de Turing
https://www.youtube.com/watch?v=b8d_oX9Ewok