Teoria da Computação - Aula 01

Prévia do material em texto

Teoria da Computação
Aula 1: Fundamentos
Apresentação
Esta aula consiste em apresentar as de�nições básicas de Teoria dos Autômatos, gramáticas, linguagens formais e
conceitos básicos da disciplina.
Objetivo
Identi�car o contexto teórico do início da Teoria da Computação;
Descrever a importância da Linguagem Natural;
Narrar os conteúdos a serem estudados, como: Autômatos Finitos e Expressões Regulares, Linguagens Livres de
Contexto, Gramática Livre de Contexto, Máquina de Turing e Complexidade.
Teoria da Computação
A Ciência da Computação baseia-se em resoluções de problemas envolvendo o processamento de dados e apresenta dois
itens essenciais:
1
Modelos teóricos e ideias fundamentais da computação.
2
Estudo de engenharia de software e hardware voltados para
a construção de sistemas computacionais.
Áreas correlatas
A Teoria da Computação deu-se por meio do estudo em diversas áreas:
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
1
Na Biologia, pela análise de neurônios evoluindo, assim,
para as redes neurais;
2
Na Engenharia Elétrica, com os conceitos de circuitos
elétricos;
3
Na Matemática, com o aprendizado em Lógica e evoluindo
para a Lógica da Computação;
4
Na Linguística, baseando-se tendo como base o
conhecimento em Gramáticas de Linguagens Naturais,
evoluindo para o Processamento de Linguagem Natural.
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Linguagens Formais
A Teoria da Computação apresenta várias áreas de conhecimento, porém a vertente que será estudada é a Linguagem
Natural. Atualmente, é essencial para o estudo em Inteligência Arti�cial e, também, em Ciência da Computação pelas
Linguagens.
Em Linguagem Natural para a disciplina de Teoria da Computação é preciso um conhecimento prévio sobre:
Teoria dos Grafos;
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Autômatos Finitos e Expressões Regulares;
Linguagens Regulares e Gramática Livre de Contexto;
Máquina de Turing e Teoria da Computabilidade;
Complexidade Computacional.
Leiamos, no texto a seguir, sobre cada um.
 Conceitos computacionais e linguagens
 Clique no botão acima.
Teoria dos Grafos
Os grafos são utilizados para modelar problemas das mais variadas áreas, como redes de transportes, problemas
de telecomunicações etc. Para entender melhor a Teoria dos Grafos, é necessário remeter ao conceito básico em
que é baseada essa abordagem, onde tem-se problemas para ir de uma cidade a outra e vários caminhos para
chegar ao destino �nal.
 As cidades são representadas por nós/vértices e os caminhos são representados por arestas. Pode-se dizer,
então, que Grafos são um conjunto de vértices (ou nós), interconectados dois a dois por arestas.
Autômatos Finitos e Expressões Regulares
Os Autômatos Finitos são a base operacional para reconhecer sentenças em um sistema de estados �nitos.
Já as Expressões Regulares são usadas para identi�car caracteres por meio de geradores de sentenças e
conjuntos (linguagens) básicos de�nidos por operações de concatenação e união.
Os dois conceitos podem ser aplicados em analisadores léxicos, sistemas de auxílio para a construção de
compiladores, processadores de textos e programas de busca de arquivos, por exemplo.
Linguagens Regulares e Gramática Livre de Contexto
A Gramática Livre de Contexto é usada para identi�car caracteres por meio de geradores de sentenças e
conjuntos (linguagens) básicos de�nidos por operações de concatenação e união, assim como as Expressões
Regulares, porém sua gramática tem restrições nas regras de produção.
O autômato com pilha é um autômato com propriedades de uma pilha. Diferente de um Autômato Finito, usa a
informação que está no topo da pilha para decidir qual transição deve ser efetuada e ainda pode manipular a pilha
ao efetuar uma transição.
Os dois conceitos podem ser aplicados em compiladores responsáveis pela análise sintática (parsers) e
especi�cações formais em linguagens de programação.
Máquina de Turing e Teoria da Computabilidade
A Máquina de Turing é um modelo de computador com fundamentos lógicos em seu funcionamento. Ela faz
análise de computação, combinação e extenção das Máquinas de Turing, por exemplo.
A Teoria da Computabilidade analisa a Tese de Church, as funções primitivas recursivas, as Máquinas de Turing
universais, a não computabilidade, o problema de parada em Máquinas de Turing,  a enumerabilidade, a
aceitabilidade e a decidibilidade.
Os dois conceitos podem ser aplicados em solução de problemas de reconhecedores e geradores de
determinadas linguagens.
Complexidade Computacional
A Complexidade Computacional analisa as Máquinas de Turing limitadas em tempo e espaço, o grau de
crescimento de funções, as simulações limitadas em tempo, as classes P e NP, NP-completude e hierarquia de
complexidade.
Conceitos básicos de conjuntos e álgebra
Conjunto
É um agrupamento contendo zero ou mais objetos diferentes, chamados de elementos de um conjunto.
Propriedades
Vejamos algumas propriedades e suas representações:
A está contido em B / A é subconjunto de B / B contém A.
 
 
A está contido propriamente em B / A é subconjunto próprio de B / B contém propriamente A.
 
 
A é igual a B / A está contido em B, assim como B está contido em A.
a  ∈  A,  a  ∉  A 
A  ⊆  B ou B  ⊇  A  
A  ⊂  B ou B  ⊃  A
A  =  B
A  ⊆  B e B  ⊆  A
De�nições
Um conjunto pode ser �nito ou in�nito.
O conjunto �nito pode ser apresentado por meio de sua descrição
Exemplo: {a, b, c}.
O conjunto vazio é aquele que não tem elementos.
Exemplo: { } símbolo usado para representar um conjunto �nito.
             ∅ símbolo usado para representar um conjunto in�nito.
Propriedades de conjuntos
Os conjuntos podem ser de�nidos como:
N: Conjunto dos Números Naturais;
Z: Conjunto dos Números Inteiros;
Q: Conjunto dos Números Racionais;
I: Conjunto dos Números Irracionais;
R: Conjunto dos Números Reais.
Operações em conjuntos
União
A ∪ B = {x | x ϵ A ou x ϵ B}
Exemplo
Seja A = {0, 1, 2} e B = {2, 3}, então A ∪ B = {0, 1, 2, 3}.
Intersecção
A ∩ B = {x | x ϵ A e x ϵ B}
Exemplo
Seja A = {0, 1, 2} e B = {2, 3}, então A ∩ B = {2}.
Diferença
A − B = {x | x ϵ A e x ∉ B}
Exemplo
Seja A = {0, 1, 2} e B = {2, 3}, então A - B = {0, 1}.
Complemento
= {x | x ϵ U e x ∉ A}A′
Exemplo
Seja A = {0, 1, 2} e B = {2, 3}, então A' = {x ∈ N | x > 2}.
Conjunto das partes
2A = { S | S ⊆ A}
Exemplo
Seja A = {0, 1, 2} e B = {2, 3}, então 2B = {∅, {2}, {3}, {2, 3}}.
Produto cartesiano
AxB = {( a, b ) | a ∈ A e b ∈ B}
Exemplo
Seja A = {0, 1, 2} e B = {2, 3}, então A×B = {(0, 2), (0, 3), (1, 2), (1, 3), (2, 2), (2, 3)}.
Propriedades de operações de conjuntos
Propriedades de relações
Considerando dois conjuntos, A e B (relacionados entre sí, ou seja, envolvidos em uma relação chamada R), dizemos que A
é domínio e B é contradomínio. Logo, aRb denota (a, b) ∈ R.
Considerando A um conjunto e R uma relação em A, há algumas propriedades a serem respeitadas. Vejamos:
Propriedades de ordem (R em A)
A seguir, algumas propriedades de ordem:
Álgebra
Uma álgebra é de�nida pelo trio A = (S, O, E), onde:
S é um conjunto de portadores;
O é um conjunto de operações;
E é um conjunto de equações.
O par (S, O) de�ne a base da álgebra e E de�ne a sua semântica. A álgebra é considerada uma linguagem de especi�cação
algébrica. Conclui-se, então, que, para os conhecimentos posteriores, é imprescindível o conhecimento algébrico.
Sequências, alfabetos e linguagens
Sequência é uma sobreposição �nita de símbolos. Símbolos são entidades abstratas não de�nidas formalmente, como
letras e dígitos. Uma sequência é representada por w. Consideramos em sequência, sequências vazias, que são
representadas por Є.
Propriedades de uma sequência
Clique nos botões para ver as informações.
Dizemos que o comprimento |w| de uma sequência w é igual ao número de símbolos dessa sequência.
Ex.: Considerando w = a, b, c, d, então |w|= 4.
Considerando w = Є, então |w|= 0.
Comprimento 
Um pre�xo de uma sequênciaé qualquer número de símbolos portador dessa sequência. Um su�xo é qualquer
número de símbolos continuadores dessa sequência. São chamados de pre�xos ou su�xos próprios de uma
sequência qualquer pre�xo ou su�xo de uma sequência diferente dela mesma.
Exemplo:  Considerando w = a, b, c, então:
Os pre�xos são: Є, a, a b, a b c.
Os su�xos são: Є, c, b c, a b c.
Pre�xo e su�xo 
A concatenação de sequências é uma sequência formada pela concatenação de ambas. Em concatenação dizemos
que Є é a identidade da concatenação.
Exemplo:  Considerando w1 = casa e w2 = mata, então:
Concatenação: w = casamata.
Identidade da concatenação: Є w = w Є = w = casamata,
Concatenação 
Atividade
Atividade do objetivo 1.
Sejam A = {0, 1} e B = {1, 2, 3}, onde m e n representam o número de elementos de cada conjunto, m = 2 e n = 3, faça a
operação de união.
Atividade do objetivo 2.
Sejam A = {1, 2} e B = {0, 2, 4}, onde m e n representam o número de elementos de cada conjunto, m = 2 e n = 3, faça a
operação de intersecção.
Atividade do objetivo 3.
Sejam A = {0, 2} e B = {0, 1, 3, 5}, onde m e n representam o número de elementos de cada conjunto, m = 2 e n = 4, faça a
operação da diferença.
Atividade do objetivo 4.
Sejam A = {0, 2} e B = {1, 3, 5}, onde m e n representam o número de elementos de cada conjunto, m = 2 e n = 3, faça a
operação de produto cartesiano.
Atividade do objetivo 5.
Dada a sequência w1 = consoantes do alfabeto e w2 = vogais do alfabeto, determine:
a. A concatenação dessas sequências;
b. A identidade dessa concatenação;
c. O comprimento |w| dessa sequência.
Referências
HOPCROFT, Ullman and Motwani. Introdução à teoria dos autômatos, linguagens e computação. Tradução da 2.ed. original de
Vandenberg D. de Souza. Rio de Janeiro: Elsevier, 2002 (tradução de: Introduction to automata theory, languages, and
computation – ISBN 85-352-1072-5).
SIPSER, Michael. Introdução à teoria da computação. Tradução técnica de Rui José Guerra Barretto de Queiroz. Revisão
técnica de Newton José Vieira. São Paulo: Thomson Learning, 2007 (título original: Introduction to the theory of computation.
“Tradução da segunda edição norte-america” – ISBN 978-85-221-0499-4).
Próxima aula
Teoria dos Grafos;
Alfabetos e linguagens;
Grafos;
Árvores.
Explore mais
Pesquise, na internet, sites, vídeos e artigos relacionados ao conteúdo visto. Em caso de dúvidas, converse com seu professor
online por meio dos recursos disponíveis no ambiente de aprendizagem.