Buscar

ITC aula1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

09/03/2012
1
HISTÓRICO E CONCEITOS 
INICIAIS
INTRODUÇÃO À TEORIA DA 
COMPUTAÇÃO
1
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Histórico
� A Teoria da Computação tem como objetivo estudar os
fundamentos da computação e entender o
funcionamento de máquinas simples que resultaram
nos computadores atuais
� Estas máquinas foram projetadas inicialmente em
papel e depois construídas fisicamente a partir de
modelos matemáticos
2
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Histórico
� Os modelos matemáticos foram criados com o
objetivo de estudar a complexidade dos algoritmos
para resolver determinados tipos de problemas
� Para entender os princípios da Teoria da Computação,
vamos construir modelos de computadores abstratos
para resolução de pequenos problemas
3
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
2
Histórico
� Existem vários modelos de máquinas, sendo
Autômato Finito a mais simples
� Autômato é uma máquina que possui todas as
características indispensáveis a um computador
digital: entrada, saída, armazenamento temporário e
tomada de decisão
4
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Histórico
� Autômato é uma maquinas que reconhece uma
linguagem, ou seja, reconhecem palavras ou cadeia de
caracteres
� O conceito de Linguagem é fundamental para Teoria
da Computação, pois trata-se de uma forma precisa de
expressar problemas
5
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Histórico
� A linguagem humana direta (falada ou escrita) é difícil
de ser entendida pelo computador dado o número
enorme de possibilidades de significados de uma
mesma palavra, além das variações de construções de
frases
6
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagem é o uso da palavra articulada ou escrita como 
meio de expressão e comunicação entre as pessoas. 
Dicionário Aurélio
09/03/2012
3
Histórico
� Há a necessidade de uma definição de linguagem mais
precisa para permitir o desenvolvimento matemático
de uma teoria baseada em linguagem
� Para diminuir o distanciamento entre a língua humana
(por exemplo: o português, o inglês, etc.) e a
programação de computadores foram criadas as
linguagens de programação, também conhecidas por
linguagens formais
7
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Linguagem formal é uma abstração das
características gerais da linguagem de programação ,
possuindo um conjunto de símbolos ou caractere,
regras de formação de sentenças
8
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Agora, vamos então conhecer definições formais, 
necessárias aos estudos posteriores 
Conceitos Iniciais
� Alfabeto é um conjunto finito de símbolos ou
caracteres
� Símbolos ou Caracteres são letras e dígitos
� Um Alfabeto é representado pelo símbolo ∑
9
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
4
Conceitos Iniciais
� Os seguintes conjuntos são Alfabetos:
� ∑ = { a, b, c}
� ∑ = ∅ (conjunto vazio)
� ∑ = { 0,1,2,…,9}
� Portanto:
� Um conjunto infinito não é um alfabeto
� O conjunto vazio é um alfabeto
10
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Uma Cadeia de Símbolos sobre um conjunto é uma
seqüência de zero ou mais símbolos (do conjunto)
justapostos
� Uma Palavra é uma Cadeia de Símbolos finita
representada pelo símbolo w
� Exemplo:
� ∑ = { a,b }, temos as seguintes palavras ou cadeias:
aabab, bb, abab
11
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Portanto:
� ε ou λ denota a cadeia vazia ou palavra vazia
� ∑ * conjunto de todas as palavras possível de ∑
o ∑ + denota ∑ * - { ε }
� Se ∑ = { a,b }
� ∑ * = {ε , a, b, aa, ab, ba, aabab, bb, abab, ...}
� ∑ + = {a, b, aa, ab, ba aabab, bb, abab,}
12
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
5
Conceitos Iniciais
� O Comprimento ou Tamanho de uma Palavra ou
Cadeia w, é representado por |w|
� |w| é o número de símbolos que compõem a palavra ou
cadeia
� Exemplos:
� | aabab | = 5
� | abab | = 4
� | ε | = 0
13
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Prefixo de uma palavra é qualquer seqüência inicial de
símbolos da palavra
� Sufixo de uma palavra é qualquer seqüência final de
símbolos da palavra
� Uma Subpalavra ou Subcadeia de uma palavra é
qualquer seqüência de símbolos contígua da palavra
14
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� abcb é uma palavra sobre o alfabeto { a, b, c}
� ε, a, ab, abc, abcb são prefixos
� ε, b, cb, bcb, abcb são sufixos
� Qualquer prefixo ou sufixo de uma palavra é uma
subpalavra
15
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
6
Conceitos Iniciais
� Uma Linguagem Formal ou Linguagem L é um
conjunto de palavras sobre um alfabeto
� Suponha o alfabeto ∑ = { a, b}, então
� O conjunto vazio e o conjunto formado pela palavra vazia são
linguagens sobre ∑. { } ou ∅ ≠ {ε }
� O conjunto dos palindromos (palavras que tem a mesma
leitura da esquerda para direita e vice-versa) sobre ∑ é um
exemplo de linguagem infinita. Assim, são palavras desta
linguagem: ε , a, b, aa, bb, aaa, bbb, aba, bab, bbb, aaaa ....
16
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� A Concatenação é uma operação binária, definida
sobre uma linguagem, a qual associa a cada par de
palavras uma palavra formada pela justaposição da
primeira com a segunda.
� Uma Concatenação é denotada pela justaposição dos
símbolos que representam as palavras componentes.
17
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� A operação de Concatenação satisfaz às seguintes
propriedades (suponha v, w, t palavras):
� Associatividade.
� v(wt) = (vw)t � vwt
� Elemento Neutro à Esquerda e à Direita.
� ε w = w = w ε 
18
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
7
Conceitos Iniciais
� Suponha o alfabeto ∑ = { a, b}. Então, para as palavras
v=baaaa e w = bb, tem-se que:
� vw = baaaabb
� ε w = w = bb
� ε v = v = baaaa
19
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Uma operação de concatenação definida sobre uma
linguagem L não é, necessariamente, fechada sobre L
� A concatenação de duas palavras de L não é, necessariamente,
uma palavra de L.
� Suponha a linguagem L de palíndromos sobre o
alfabeto ∑ = { a, b}.
� A concatenação das palavras aba e bbb resulta na palavra
ababbb a qual não é palíndromo. Portanto, a operação de
concatenação não é fechada sobre L
20
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� A Concatenação Sucessiva de uma palavra (com ela
mesma), representada na forma de um expoente w
onde w é uma palavra e n indica o número de
concatenações sucessivas
a n Significa uma cadeia de a ‘s de tamanho n.
� Exemplos:
a5 = aaaaa
a1 = a
a0 = ε
21
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
8
Conceitos Iniciais
� Define-se para uma linguagem L qualquer, o seu
fechamento como sendo L* ou L +
� Se L = { a,b }
� L * = {ε , a, b, aa, ab, ba, aabab, bb, abab, ...}
� L + = {a, b, aa, ab, ba aabab, bb, abab,}
22
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Desde que uma linguagem é definida comoum
conjunto, operações de união, intersecção e diferença
podem ser aplicadas
� União: L1 ∪ L2 = { w | w ∈ L1 ou w ∈ L2}
� Intersecção : L1 ∩ L2 = { w | w ∈ L1 e w ∈ L2 }
� Diferença : L1 − L2 = { w | w ∈ L1 e w ∉ L2 }
23
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� Suponha L1 = {a, b, aa, ab, abb, aab, aaa } e
L2 = {a, aa, aaa, aaaa }
� União: L1 ∪ L2 = {a, b, aa, ab, abb, aab, aaa , aaaa }
� Intersecção : L1 ∩ L2 = {a, aa, aaa }
� Diferença : L1 − L2 = {b, ab, abb, aab}
24
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
09/03/2012
9
Conceitos Iniciais
� O complemento de uma linguagem é definido como
todos os elementos que não pertencem a essa
linguagem
� Seja ∑ = { a,b }
� Seja L = { an : n >= 0}, L = { ε, a, aa, aaa, aaaa … }
� Então, L = {b, ab, aab, bba}
25
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Conceitos Iniciais
� O complemento de uma linguagem é definido como
todos os elementos que não pertencem a essa
linguagem
� Seja ∑ = { a,b }
� Seja L = { an : n >= 0}, L = { ε, a, aa, aaa, aaaa … }
� Então, L = {b, ab, aab, bba}
26
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Revisar para a próxima aula
� Conjunto
� Elementos
� Operações sobre os conjuntos
� Propriedades das operações
27
Profa. Ellen Souza - https://sites.google.com/site/ellenuast

Outros materiais