Baixe o app para aproveitar ainda mais
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
Compartilhar