Buscar

itc aula7(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 11 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 11 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 11 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

19/10/2012
1
GR AM ÁT IC AS IR R EST R ITAS
GR AM ÁT IC AS SENSÍVEI S AO CONT EXTO
L INGUAGEM ENUM ER ÁVEL 
R EC URSIVAM ENT E ( T IPO 0)
L INGUAGE NS SENSÍVEI S AO CONT EXTO 
( T IPO 1)
INTRODUÇÃO À TEORIA DA 
COMPUTAÇÃO
1
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática
� Uma Gramática é uma quádrupla ordenada
G = (V, T, P, S) onde:
� V
� conjunto finito de símbolos
� variáveis ou não-terminais
� T
� conjunto finito de símbolos
� terminais
� disjunto de V
2
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
19/10/2012
2
Gramática
� Uma Gramática é uma quádrupla ordenada 
G = (V, T, P, S) onde:
� P
� conjunto finito de pares (α,β) = α →β
� denominados regras de produção
� α é palavra de (V ∪ T)+
� β é palavra de (V ∪ T)*
� S
� elemento de V
� variável inicial
3
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática Irrestrita
� Podem existir variáveis e terminais no lado direito e 
esquerdo das produções.
� A única restrição é não permitir o λ no lado esquerdo
4
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Uma Gramática G = (V, T, P, S) é chamada Irrestrita se
todas as produções são da forma:
u � v
onde u ∈ (V ∪ T)+ e v ∈ (V ∪ T)*
19/10/2012
3
Gramática Irrestrita
� Exemplo 1: Seja L={anbncn | n ≥ 0}, então a Gramática 
Irrestrita G = ({S,C}, {a,b,c}, S, P)
� P = { S � abc | λ
ab � aabbC
Cb � bC
Cc � cc}
� Seja w = a3b3c3
� w = aaabbbccc
5
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática Irrestrita
� Exemplo 1:
� Seja L={anbncn | n ≥ 0},
� P = { S � abc | λ
ab � aabbC
Cb � bC
Cc � cc}
� Seja w = a3b3c3
� w = aaabbbccc
6
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
� Derivação de w = aaabbbccc
Derivação Regra de Produção
S ⇒ abc (ab � aabbC)
⇒ aabbCc (ab � aabbC)
⇒ aaabbCbCc (Cb � bC)
⇒ aaabbbCCc (Cc � cc)
⇒ aaabbbCcc (Cc � cc)
⇒ aaabbbccc
19/10/2012
4
Gramática Irrestrita
� Exemplo 2: Seja L={anb2nan | n ≥ 0}, então a Gramática 
Irrestrita G = ({S,C}, {a,b,a}, S, P)
� P = { S � aAbba
aAb � aabbbA | ab
bAb �bbA
bAa � Bbaa
bB � Bb
aB � aA}
� Seja w = a3b6c3, 
� Forneça as regras de derivação da palavra w = 
aaabbbbbbaaa
7
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagem Recursivamente Enumerável
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
8
� Dado que existe uma Gramática Irrestrita G, L = L(G) é 
uma Linguagem Recursivamente Enumerável
� Dados que L é uma Linguagem Recursivamente 
Enumerável então L é gerada por uma Gramática 
Irrestrita
� É possível gerar uma Gramática Irrestrita a partir de 
uma Máquina de Turing (algoritmo)
L é uma Linguagem Recursivamente Enumerável se, e 
somente se, L é gerada por uma Gramática Irrestrita G
19/10/2012
5
Linguagem Recursivamente Enumerável
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
9
� Sabe-se que, na Máquina de Turing:
� A aceitação de uma cadeia acontece quando o estado final é 
atingido independente de onde a cabeça está na fita.
� Se a Máquina de Turing pára em algum estado não final ou 
simplesmente entrar em loop infinito, então a cadeia não é 
aceita.
Uma Linguagem L é dita ser uma Linguagem 
Recursivamente Enumerável se existe uma Máquina 
de Turing, M = (∑ , Q, δ, q0, F, V, β, ⊛), que a aceita
Linguagem Recursivamente Enumerável
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
10
� Temos:
� ACEITA(M): conjunto de todas as palavras de ∑* aceitas por M;
� REJEITA(M): conjunto de todas as palavras de ∑* não aceitas por 
M;
� LOOP(M): conjunto de todas as palavras de ∑* que entram em 
ciclo infinitos em M
� Então: 
� ∑* = ACEITA(M) ∪ REJEITA(M) ∪ LOOP(M)
� ∅ = ACEITA(M) ∩ REJEITA(M) ∩ LOOP(M)
� L(M) = ACEITA(M)
� REJEITA(M) = ∑* - {L(M) ∪ LOOP(M)}
19/10/2012
6
Linguagem Recursivamente Enumerável
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
11
� Para sabermos de uma cadeia pertence à Linguagem 
Recursivamente Enumerável, é só verificar se uma Máquina 
de Turing a aceita
� Difícil é saber quando uma cadeia não pertence à Linguagem, 
já que, na rejeição da cadeia, a Máquina de Turing pode não 
parar (loop)
� Também, podem existir linguagens que não conhecidas por 
uma Máquina de Turing, ou seja, pode não ser possível 
construir uma Máquina de Turing que a aceite e portanto 
linguagens que não são recursivamente enumeráveis
Linguagem Recursivamente Enumerável
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
12
� Logo, concluímos que:
� Existem problemas sem solução na forma de algoritmo, já que 
existem linguagens que não são reconhecidas por Máquina de 
Turing
� O conjunto de todos os problemas solucionáveis (reconhecidos 
por Máquinas de Turing) é infinitamente contável
� O conjunto de todos os problemas não solucionáveis é 
infinitamente não contável
� Computacionalmente, existem mais problemas que algoritmos 
para resolvê-los
Para qualquer alfabeto não vazio, ∑, existem 
linguagens que não são recursivamente enumeráveis
19/10/2012
7
Linguagem Recursivamente Enumerável
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
13
� Assim, a hierarquia de Chomsky pode ser modificada 
para:
Universo de Todas as 
Linguagens
Linguagem 
Recursivamente 
Enumeráveis
Linguagens Sensíveis 
ao Contexto
Linguagens Livres 
de Contexto
Linguagens 
Regulares
Linguagens Recursivas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
14
� Como fica difícil determinar se uma cadeia não 
pertence à linguagem, já que ao processar uma cadeia 
a Máquina de Turing pode entrar em loop infinito
� É possível restringir as Linguagens Recursivamente 
Enumeráveis, dizendo que elas devem ter o conjunto 
LOOP (M) = ∅, ou seja,
� ACEITA(M1) = L(M1) = L1
� REJEITA(M1) = ∑* - L1
� LOOP(M) = ∅
19/10/2012
8
Linguagens Recursivas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
15
� Ao restringir a Linguagem Recursivamente 
Enumerável, cria-se um outro subconjunto: o 
subconjunto da Linguagem Recursiva
Uma Linguagem L é dita ser Recursiva se existe 
uma Máquina de Turing que aceita L e que pára
em cada w em ∑+
Linguagens Recursivas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
16
� Hierarquia de Chomsky pode ser modificada para:
Universo de Todas as Linguagens
Linguagem Recursivamente 
Enumeráveis
Linguagens Recursivas
Linguagens Sensíveis ao 
Contexto
Linguagens Livres de 
Contexto
Linguagens 
Regulares
19/10/2012
9
Linguagens Recursivas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
17
� Algumas propriedade relacionadas às Linguagens 
Recursivas (LR)
� Se L é uma LR então seu complemento também é uma LR
� L é uma LR se, e somente se, L e seu complemento são LRE
� A classe de LRs está contida propriamente na classe das LREs
Gramática Sensível ao Contexto
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
18
� A cada etapa da derivação, o tamanho da palavra 
derivada não pode diminuir
� Exceção para gerar a palavra vazia, se esta pertencer à linguagem
Uma Gramática Irrestrita G = (V, T, P, S) é chamada 
Gramática Sensível ao Contexto se todas as 
produções são da forma:
u � v ∈ P, 
tem a propriedade | u | ≤ | v | 
19/10/2012
10
Linguagens Sensíveis ao Contexto
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
19
Uma Linguagem L é Sensível ao Contexto se existe 
uma Gramática Sensível ao Contexto, tal que L = L(G) 
ou L = L(G) ∪ {λ}
Gramática Sensível ao Contexto� Exemplo 3: Seja L={anbncn | n ≥ 1}, então a Gramática 
Sensível ao Contexto G = ({S,C}, {a,b,c}, S, P)
� P = { S � abc
ab � aabbC
Cb � bC
Cc � cc}
20
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
19/10/2012
11
Gramática Sensível ao Contexto
� Exemplo 4: Seja L={anb2nan | n ≥ 1}, então a Gramática 
Livre do Contexto G = ({S,C}, {a,b,a}, S, P)
� P = { S � aAbba | abba
aAb � aabbbA
Bb � bB
Ba � Caa | aa
bCa � Cba
bC � Cb
aCb � aAb } 
21
Profa. Ellen Souza - https://sites.google.com/site/ellenuast

Outros materiais