Buscar

itc-aula5(Ellen Souza)

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 22 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 22 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 22 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

Prévia do material em texto

27/09/2012
1
LINGUAGENS ENUMERÁVEIS 
RECURSIVAMENTE
E SENSÍVEIS AO CONTEXTO
INTRODUÇÃO À TEORIA DA 
COMPUTAÇÃO
1
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Enumeráveis Recursivamente
e Sensíveis ao Contexto
� Correspondência entre as classes de linguagens,
gramáticas e reconhecedores
2
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagem Gramática Reconhecedor
Tipo 0: 
enumerável 
recursivamente
irrestrita máquinas de 
Turing
Tipo 1: sensível 
ao contexto
sensível ao 
contexto
autômato 
limitado 
linearmente
Tipo 2: livre do contexto livre do contexto autômatos com pilha
Tipo 3: regular regular autômatos finitos
Máquina de Turing 
com Fita Limitada
27/09/2012
2
Linguagens Enumeráveis Recursivamente
e Sensíveis ao Contexto
� Para as linguagens Regulares (tipo 3) foram estudados
os formalismos:
� Operacional ou reconhecedor: Autômato Finito
� Axiomático ou gerador – Gramática Regular
� Denotacional – Expressão Regular
� Para as linguagens Livres de Contexto (tipo 2) foram
estudados os formalismos:
� Operacional ou reconhecedor: Autômato com Pilha
� Axiomático ou gerador – Gramática Livre de Contexto
3
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Enumeráveis Recursivamente
e Sensíveis ao Contexto
� Para as Linguagens Sensíveis ao Contexto (tipo 1)
serão estudados os formalismos:
� Operacional ou reconhecedor: Máquina de Turing com Fita
Limitada
� Axiomático ou gerador – Gramática Sensível ao Contexto
� Para as Linguagens Enumeráveis Recursivamente
(tipo 0) serão estudados os formalismos:
� Operacional ou reconhecedor: Máquina de Turing
� Axiomático ou gerador – Gramática Irrestrita
4
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
3
Linguagens Enumeráveis Recursivamente
e Sensíveis ao Contexto
� Como a Máquina de Turing será usada como um
formalismo reconhecedor das Linguagens Sensíveis ao
Contexto e Enumeráveis Recursivamente, vamos
estudar Máquina de Turing de uma forma geral
5
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Enumeráveis Recursivamente
e Sensíveis ao Contexto
� Ciência da Computação é o conhecimento
sistematizado relativo à computação.
� Sua origem é remota, tendo exemplos :
� Na antiga Grécia (século III a.C., no desenho de algoritmos por
Euclides) e
� Na Babilônia (com estudos sobre complexidade e reducibilidade
de problemas)
6
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
4
Linguagens Enumeráveis Recursivamente
e Sensíveis ao Contexto
� No início do século XX, diversas pesquisas foram
desenvolvidas com o objetivo de definir um modelo
computacional suficientemente genérico, capaz de
implementar qualquer "função computável“
� Em 1936, Alan Turing propôs um modelo conhecido
como Máquina de Turing.
7
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Alan Turing
� Alan Mathison Turing
� Matemático, lógico,
criptoanalista e cientista
da computação
� Nasceu em Londres, no
dia 23 de junho de 1912
8
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
5
Alan Turing
� Um dos principais prêmios internacionais da área de
Computação leva o seu nome, o ACM Turing Award
� Este ano (2012), é celebrado o Ano Internacional de
Turing em comemoração ao centenário de seu nascimento
� Com 24 anos de idade, apresentou uma formalização do
conceito de algoritmo e computação
� Máquina de Turing
� Contribuição imprescindível para o desenvolvimento do computador
moderno
9
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� Atualmente, a Máquina de Turing é aceita como uma
formalização de um procedimento efetivo ( algoritmo
ou função computável),
� Isto é, uma seqüência finita de instruções, as quais podem ser
realizadas mecanicamente, em um tempo finito
� Ainda em 1936, Alonzo Church apresentou a
Hipótese de Church:
� Afirma que qualquer função computável pode ser processada
por uma Máquina de Turing, ou seja, existe um procedimento
expresso na forma de uma Máquina de Turing capaz de
processar qualquer função.
10
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
6
Máquina de Turing
� Contudo, como a noção intuitiva de procedimentos
não é matematicamente precisa, é impossível
demonstrar formalmente se a Máquina de Turing é,
efetivamente, o mais genérico dispositivo de
computação
� Entretanto, foi mostrado que todos os demais
modelos propostos possuem, no máximo, a mesma
capacidade computacional da Máquina de Turing, o
que reforça a Hipótese de Church
11
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Enumeráveis Recursivamente
� As Linguagens Enumeráveis Recursivamente ou Tipo
0 são aquelas que podem ser reconhecidas por uma
Máquina de Turing.
� Considerando que, segundo a Hipótese de Church, a
Máquina de Turing é o mais geral dispositivo de
computação, então a Classe das Linguagens
Enumeráveis Recursivamente representa o conjunto
de todas as linguagens que podem ser reconhecidas
mecanicamente e em um tempo finito.
12
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
7
Linguagens Enumeráveis Recursivamente
� As Linguagens Enumeráveis Recursivamente ou
Tipo 0 são aquelas que podem ser reconhecidas por
uma Máquina de Turing.
� Considerando que, segundo a Hipótese de Church, a
Máquina de Turing é o mais geral dispositivo de
computação, então a Classe das Linguagens
Enumeráveis Recursivamente representa o conjunto
de todas as linguagens que podem ser reconhecidas
mecanicamente e em um tempo finito.
13
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Enumeráveis Recursivamente
� O estudo das Linguagens Enumeráveis
Recursivamente ou Tipo 0, pode ser abordado através
de formalismos:
� Operacional ou reconhecedor (máquina):
� Máquina de Turing: modelo formal de procedimento efetivo,
algoritmo ou função computável
� Axiomático ou gerador (gramática):
� Gramática Irrestrita: gramática que não possui qualquer restrição
sobre a forma das produções
14
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
8
Linguagens Sensíveis ao Contexto
� As Linguagens Sensíveis ao Contexto ou Tipo 1 estão
contidas propriamente nas Enumeráveis
Recursivamente
15
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Fonte: (Menezes,1999)
Linguagens Sensíveis ao Contexto
� O estudo das Linguagens Sensíveis ao Contexto ou
Tipo 1 , pode ser abordado através de formalismos:
� Operacional ou reconhecedor (máquina):
� Máquina de Turing com Fita Limitada: trata-se de uma Máquina de
Turing com limitação no tamanho da fita a qual, portanto, é finita
� Axiomático ou gerador (gramática):
� Gramática Sensível ao Contexto: o termo "sensível ao contexto"
deriva do fato de que o lado esquerdo das produções da gramática
pode ser uma palavra de variáveis ou terminais, definindo um
"contexto" de derivação
16
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
9
Máquina de Turing
� A Máquina de Turing para ser considerada como um
modelo formal de procedimento efetivo, algoritmo ou
função computável deve satisfazer às seguintes
propriedades, entre outras:
� A descrição do algoritmo deve ser finita e
� Deve consistir de passos:
� discretos;
� executáveis mecanicamente;
� em um tempo finito.
17
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� O modelo proposto por Alan Turing (1936), conhecido
como Máquina de Turing, consiste de 3 partes:
� Fita. Usada simultaneamente como dispositivode entrada, saída
e memória de trabalho;
� Unidade de Controle. Reflete o estado corrente da máquina.
Possui uma unidade de leitura e gravação (cabeça da fita) a qual
acessa uma célula da fita de cada vez e movimenta-se para a
esquerda ou direita;
� Programa ou Função de Transição. Função que comanda as
leituras e gravações, o sentido de movimento da cabeça e define
o estado da máquina.
18
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
10
Máquina de Turing
� A fita é finita à esquerda e infinita à direita, sendo
dividida em células, onde cada uma armazena um
símbolo.
� Os símbolos podem pertencer
� Ao alfabeto de entrada,
� ao alfabeto auxiliar ou ainda,
� ser "branco" ou
� "marcador de início de fita”
19
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� Inicialmente, a palavra a ser processada (ou seja, a
informação de entrada para a máquina) ocupa as
células mais à esquerda, após o marcador de início de
fita, ficando as demais espaços com "branco"
20
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ b b a c β β …
Unidade de 
Controle
Cabeça da 
Fita
Entrada Branco
Marcador de
iníco de fita
q0
27/09/2012
11
Máquina de Turing
� A unidade de controle possui um número finito e
predefinido de estados
� A cabeça da fita lê o símbolo de uma célula de cada vez
e grava um novo símbolo.
� Após a leitura/gravação, a cabeça move uma célula para a direita
ou esquerda. O símbolo gravado e o sentido do movimento são
definidos pelo programa.
� O programa é uma função que, dependendo do estado corrente
da máquina e do símbolo lido, determina o símbolo a ser
gravado, o sentido do movimento da cabeça e o novo estado.
21
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� Uma Máquina de Turing é uma 8-upla, onde:
� ∑ alfabeto de símbolos de entrada;
� Q conjunto de estados possíveis da máquina o qual é finito;
� δ programa ou função de transição:
� δ: Q (∑ ∪ V ∪ { β, ⊛}) → Q X (∑ ∪ V ∪ {β, ⊛}) {E,D}, a qual é parcial
� q0 estado inicial da máquina tal que q0 é elemento de Q;
� F conjunto de estados finais tal que F está contido em Q;
� V alfabeto auxiliar (pode ser vazio);
� Β símbolo especial branco;
� ⊛ símbolo ou marcador de início da fita
22
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
M = (∑ , Q, δ, q0, F, V, β, ⊛ )
27/09/2012
12
Máquina de Turing
� O símbolo de início de fita sempre ocorre exatamente
uma vez e na célula mais à esquerda da fita, auxiliando
na identificação de que a cabeça da fita se encontra na
célula mais à esquerda da fita.
� A função programa, considera o estado corrente e o
símbolo lido da fita para determinar o novo estado, o
símbolo a ser gravado e sentido de movimento da
cabeça onde esquerda e direita são representados por
E e D, respectivamente
23
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� Representação da função programa da Máquina de
Turing como um grafo
24
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
13
Máquina de Turing
� O processamento de uma Máquina de Turing
M=(∑,Q,δ, q0, F, V, β,⊛), para uma palavra de entrada
w, consiste na sucessiva aplicação da função programa
a partir do estado inicial q0 e da cabeça posicionada na
célula mais à esquerda da fita até ocorrer uma
condição de parada.
� O processamento de M para a entrada w, pode parar
ou ficar em loop infinito. A parada pode ser de duas
maneiras: aceitando ou rejeitando a entrada w.
25
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� As condições de parada são as seguintes:
� A máquina assume um estado final: a máquina para e a palavra
de entrada é aceita;
� A função programa é indefinida para o argumento (símbolo lido e
estado corrente): a máquina para e a palavra de entrada é
rejeitada;
� O argumento corrente da função programa define um movimento
à esquerda e a cabeça da fita já se encontra na célula mais à
esquerda: a máquina para e a palavra de entrada é rejeitada.
26
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
14
Máquina de Turing
� Suponha que M é uma Máquina de Turing:
� ACEITA(M) ou L(M): conjunto de todas as palavras de ∑* aceitas
por M;
� REJEITA(M): conjunto de todas as palavras de ∑* rejeitadas por
M;
� LOOP(M): conjunto de todas as palavras de ∑* para as quais M
fica processando indefinidamente.
27
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� Resumindo:
28
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
A aceitação de uma cadeia pela Máquina de Turing 
acontece quando o estado final é atingido independente 
de onde a cabeça está na fita. Se a Máquina de Turing 
para em algum estado não final ou simplesmente entrar 
em “loop” infinito, a cadeia não é aceita.
27/09/2012
15
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� Considere a linguagem: L1 = { an bn | n ≥ 0 }
� A Máquina de Turing: M1 = ({ a, b }, { q0, q1, q2, q3, q4 }, δ1, q0, {
q4 }, { A, B }, β , ⊛), onde δ1 é:
29
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ1 ⊛ a b A B β
q0 (q0, ⊛, D) (q1, A, D) (q3, B, D) (q4, β, D)
q1 (q1, a, D) (q2, B, E) (q1, B, D)
q2 (q2, a, E) (q0, A, D) (q2, B, E)
q3 (q3, B, D) (q4, β, D)
q4
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
30
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
16
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� Apresente a sequência do processamento da Máquina de Turing
para a entrada w = aabb
� δ1 (q0, ⊛)=(q0, ⊛, D)
� δ1 (q0, a)=(q1, A, D)
31
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ a a b b β β …
q0
⊛ a a b b β β …
q0
⊛ A a b b β β …
q1
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� δ1 (q1, a)=(q1, a, D)
� δ1 (q1, b)=(q2, B, E)
32
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ A a b b β β …
q1
⊛ A a B b β β …
q2
⊛ A a b b β β …
q1
27/09/2012
17
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� δ1 (q2, a)=(q2, a, E)
� δ1 (q2, A)=(q0, A, D)
33
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ A a B b β β …
q2
⊛ A a B b β β …
q0
⊛ A a B b β β …
q2
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� δ1 (q0, a)=(q1, A, D)
� δ1 (q1, B)=(q1, B, D)
34
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ A A B b β β …
q1
⊛ A A B b β β …
q1
⊛ A a B b β β …
q0
27/09/2012
18
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� δ1 (q1, b)=(q2, B, E)
� δ1 (q2, B)=(q2, B, E)
35
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ A A B B β β …
q2
⊛ A A B b β β …
q1
⊛ A A B B β β …
q2
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� δ1 (q2, A)=(q0, A, D)
� δ1 (q0, B)=(q3, B, D)
36
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ A A B B β β …
q0
⊛ A A B B β β …
q2
⊛ A A B B β β …
q3
27/09/2012
19
Máquina de Turing
� Exemplo 1: Máquina de Turing - Duplo Balanceamento
� δ1 (q3, B)=(q3, B, D)
� δ1 (q3, β)=(q4, β, D)
37
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
⊛ A A B B β β …
q3
⊛ A A B B β β …
q4
⊛ A A B B β β …
q3
Máquina de Turing
� Algumas variações sobre a Máquina de Turing
� Diferentes símbolos.
� Alguns autores utilizam osímbolo ⎕ para representar o espaço em
branco (β)
� O movimento de direita (D) e esquerda (E) podem ser representador
pela letra (R) Right = Direita e (L) Left = Esquerda
� Inexistência de marcador de início. Algumas máquinas não
possuem o símbolo de marcador de início de fita (⊛). Neste caso,
o símbolo branco (⎕ ou β ) pode ser utilizado para entrada vazia
ou nenhum símbolo, onde a célula mais esquerda contém o
primeiro símbolo da palavra de entrada.
38
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
20
Máquina de Turing
� Algumas variações sobre a Máquina de Turing
� Cabeça de Fita não se move em uma Leitura/Gravação. A
movimentação da cabeça da fita tem como objetivo facilitar a
especificação da função programa, bem como reduzir o número
de transições necessárias.
� Estado Final de Rejeição. Pode der definido para explicitar a
condição de parada com rejeição de entrada. Facilita a
compreensão da lógica da função programa.
39
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Máquina de Turing
� Exercício 1: Máquina de Turing - Duplo
Balanceamento
� Apresente a sequência do processamento da Máquina de Turing
para a entrada w = aaab
40
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
21
Máquina de Turing
� Exercício 3: Dada a Máquina de Turing que aceita a
linguagem denotada pela Expressão Regular ER = 0*,
definida como:
� M = ({ q0, q1 }, {0}, { 0, ⎕}, δ, q0, { q1 }, onde δ é:
� δ(q0,0) = (q0,0,R) e
� δ(q0,⎕) = (q1,⎕,R)
� Apresente a sequência do processamento da Máquina de Turing
para uma entrada válida.
� Apresente a sequência do processamento da Máquina de Turing
para uma entrada inválida.
� Utilize a ferramenta JFLAP para construir o autômato e
reconhecer cadeias
41
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Modelos Equivalentes a Máquina de Turing
� Uma das razões para considerar a Máquina de Turing
como o mais geral dispositivo de computação é o fato
de que todos os demais modelos e máquinas
propostos, bem como diversas modificações da
Máquina de Turing, possuem, no máximo, o mesmo
poder computacional da Máquina de Turing
42
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27/09/2012
22
Modelos Equivalentes a Máquina de Turing
� As modificações apresentadas a seguir são
freqüentemente usadas.
�Autômato com Múltiplas Pilhas
�Máquina de Turing Não-Derminística
�Máquina de Turing com Fita Infinita à Esquerda e à
Direita.
�Máquina de Turing com Múltiplas Fitas
�Máquina de Turing Multidimensional
�Máquina de Turing com Múltiplas Cabeças
�Combinações de Modificações sobre a Máquina de
Turing
43
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Pesquisa
� Quais foram as contribuições de Alan Turing para a
Ciência da Computação?
� Elaborar texto com, no máximo, 30 linhas
� Fonte arial 10, sem espaçamento e tamanho de margem normal
� Entregar dia 15/05
� Vale 0,5 ponto para a nota da 1a VA
� Indicar as fontes de pesquisa
44
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Textos (ou parte de textos) 
copiados não serão avaliados!

Outros materiais