TEMA 9 - Propriedades de Linguagens Recursivas e Recursivamente Enumeráveis

Prévia do material em texto

Propriedades de Linguagens Recursivas e 
Recursivamente Enumeráveis 
Prof. Ricardo P. Mesquita
Propriedades das Linguagens Recursivamente Enumeráveis 
e Recursivas
 O complemento de uma linguagem recursiva é uma linguagem recursiva; 
 Uma linguagem é recursiva se e somente se a linguagem e seu complemento 
são linguagens recursivamente enumeráveis. 
 A classe das linguagens recursivas está contida propriamente na classe das 
linguagens recursivamente enumeráveis.
02/23Prof. Ricardo Mesquita
Propriedades
Teorema – O complemento de uma linguagem recursiva é recursiva 
 Se uma linguagem L sobre um alfabeto Σ qualquer é recursiva, então o seu 
complemento ~L também é uma linguagem recursiva.
Prova:
 Suponha L uma linguagem recursiva sobre Σ. Então existe M, máquina de 
Turing, que aceita a linguagem e sempre para para qualquer entrada. Ou seja:
03/23Prof. Ricardo Mesquita
Propriedades
 Seja Inverte uma máquina de Turing que inverte as condições de ACEITA
por REJEITA e vice-versa. 
 Seja M’ uma máquina de Turing resultante da composição das máquinas 
Inverte e M, 
04/23Prof. Ricardo Mesquita
Propriedades
 Claramente, M’ aceita a linguagem ~L e sempre para para qualquer entrada, 
ou seja:
 Portanto, o complemento de uma linguagem recursiva é uma linguagem 
recursiva.
05/23Prof. Ricardo Mesquita
Propriedades
Teorema – Linguagem recursiva × recursivamente enumerável 
 Uma linguagem L sobre um alfabeto Σ qualquer é recursiva se e somente se L e ~L 
são recursivamente enumeráveis. 
Prova:
 () Suponha L uma linguagem recursiva sobre Σ. Então, como foi mostrado no 
teorema anterior (o complemento de uma linguagem recursiva é recursiva), ~L é 
recursiva. Como toda linguagem recursiva também é recursivamente enumerável, 
então L e ~L são recursivamente enumeráveis.
06/23Prof. Ricardo Mesquita
Propriedades
 () Suponha L uma linguagem sobre Σ tal que L e ~L são recursivamente 
enumeráveis. Então existem M1 e M2, máquinas de Turing, tais que:
 Seja Inverte uma máquina de Turing que inverte as condições de ACEITA por 
REJEITA e vice-versa. Seja M uma máquina de Turing resultante da composição das 
máquinas M1, M2 e Inverte:
07/23Prof. Ricardo Mesquita
Propriedades
 ou seja: 
 composição não determinística de M1 com M2; 
 composição sequencial de M1 com Inverte. 
 Para qualquer palavra de entrada, M aceita se M1 aceita, e M rejeita se M2
aceita. Portanto, claramente, M sempre para. Logo, L é recursiva.
08/23Prof. Ricardo Mesquita
Propriedades
Teorema – Linguagem não-recursivamente enumerável
 Seja Σ = {a, b}.
a) Suponha que Xi representa o i-ésimo elemento na ordenação lexicográfica de Σ*. Por exemplo (o
valor de i ∈ N e o correspondente elemento de Σ* na ordenação lexicográfica estão na primeira
e segunda colunas, respectivamente):
0 ε
1 a
2 b
3 aa
… …
b) É possível codificar todas as máquinas de Turing como uma palavra sobre Σ de tal forma que cada
código represente uma única máquina de Turing. Suponha o conjunto dos códigos ordenados
lexicograficamente e suponha que Ti representa o i-ésimo código nesta ordenação. Então, o
conjunto que segue não é linguagem recursivamente enumerável:
L = {Xi | Xi não é aceita por Ti}
09/23Prof. Ricardo Mesquita
Propriedades
Teorema – Linguagens recursivas ⊂ recursivamente enumeráveis
 A classe das linguagens recursivas está contida propriamente na classe das linguagens recursivamente 
enumeráveis. 
Prova: 
 Para mostrar que a inclusão é própria, basta mostrar que existe pelos menos uma linguagem 
recursivamente enumerável que não é recursiva. A linguagem recursivamente enumerável que segue é 
não recursiva, e Xi e Ti são como definidas no teorema anterior (cuidado para não confundir com a 
linguagem {Xi | Xi não é aceita por Ti}):
L = {Xi | Xi é aceita por Ti}
 L é recursivamente enumerável.
10/23Prof. Ricardo Mesquita
Propriedades
 Segue um esboço da construção de uma máquina de Turing M que aceita uma palavra w 
qualquer pertencente a L:
a. M gera as palavras X1, X2,… em ordem lexicográfica, comparando-as com w. Quando Xi = 
w, M sabe que w é a i-ésima palavra na enumeração;
b. M gera Ti, a i-ésima máquina de Turing;
c. M simula Ti para a entrada w = Xi e, se w pertence a ACEITA(Ti), então w pertence a 
ACEITA(M)
 Portanto, M aceita w se, e somente se, Xi = w é aceita por Ti. Logo, L é recursivamente 
enumerável.
 L não é recursiva. Conforme o teorema – Linguagem recursiva × recursivamente enumerável, 
L é recursiva se, e somente se, L e seu complemento são recursivamente enumeráveis. 
Como o complemento de L, conforme o teorema – Linguagem não recursivamente 
enumerável, não é recursivamente enumerável, então L é não recursiva.
11/23Prof. Ricardo Mesquita
Conclusões
 As linguagens formais oferecem meios para modelar e desenvolver ferramentas que 
especificam linguagens e seus processos de análise, bem como suas propriedades e 
limitações algorítmicas. 
 Alguns problemas referentes às linguagens formais, embora atuais, possuem questões 
em aberto, como:
a. A tradução de linguagens, principalmente as naturais; 
b. No caso específico dos autômatos finitos, o desenvolvimento de soluções (possivelmente) 
complexas frequentemente exige um número excessivo de estados, resultando em uma 
explosão de estados. O tratamento da explosão de estados é um importante tema de 
pesquisa, tanto para a interface humano × máquina como para a implementação 
computacional;
12/23Prof. Ricardo Mesquita
Conclusões
c. O tratamento de linguagens n-dimensionais, com destaque para as bi e as 
tridimensionais, com importantes aplicações como:
 processamento de imagens; 
 animações; 
 sistemas biológicos: simulação do desenvolvimento de sistemas vivos), etc., tanto no plano, 
quanto no espaço; 
 sistemas concorrentes (eventualmente distribuídos e/ou comunicantes): especificação formal e 
prova de propriedades.
13/23Prof. Ricardo Mesquita
Gramáticas de Grafos
 Como ilustração de uma abordagem das linguagens formais às linguagens n-
dimensionais, no que segue é apresentada a noção de gramática de grafos.
 A ideia básica das gramáticas de grafos é análoga à das gramáticas de Chomsky, ou 
seja: 
 regras de produção são pares (mas de grafos); 
 uma derivação é a substituição de um subgrafo de acordo com uma regra de produção.
14/23Prof. Ricardo Mesquita
Gramáticas de Grafos
 As gramáticas de grafos constituem um caso particular das gramáticas categoriais 
(nenhum conceito de teoria das categorias é formalmente introduzido nesta 
publicação). 
 A ideia básica é substituir palavras por grafos no conceito de gramática de Chomsky. 
Mas, observe que, na realidade, a noção categorial de gramática é bem mais 
expressiva, pois: 
 gramáticas categoriais podem ser usadas sobre palavras, grafos, conjuntos parcialmente 
ordenados, redes, autômatos, máquinas, linguagens de programação e outros tipos de objetos, 
desde que sejam satisfeitas determinadas condições; 
 as derivações (aplicações de regras de uma gramática) são generalizadas. 
15/23Prof. Ricardo Mesquita
Gramática de Grafos: PacMan
 O jogo PacMan (simplificado) possui um tabuleiro juntamente com algumas entidades 
especiais como um PacMan e dois conjuntos, um de fantasmas e outro de maçãs. 
 A figura a seguir ilustra um grafo representando um estado do sistema no qual, para 
facilitar a visualização, as entidades PacMan, fantasmas e maçãs são representadas por 
nodos com simbologia própria.
16/23Prof. Ricardo Mesquita
Gramática de Grafos: PacMan
 Na figura, vê-se que: 
 os nodos pretos representam os lugares do tabuleiro, e as correspondentes arestas, os 
caminhos possíveis entre dois lugares; 
 para as entidades PacMan, fantasmas e maçãs, os correspondentes arcos denotam o 
seu posicionamento no tabuleiro; 
 uma maçã cujo nodo destino é o nodo branco denota uma maçã já comida; 
 a aresta numerada com origem e destino no nodo branco identificaa fase em que se 
encontra o jogo (no caso, a segunda fase).
17/23Prof. Ricardo Mesquita
Gramática de Grafos: PacMan
 A figura ao lado ilustra as seguintes regras 
de produção: 
 move: o PacMan move-se para uma casa 
adjacente; 
 come: o PacMan come a maçã. A maçã comida é 
posicionada no nodo branco; 
 mata: o fantasma mata o PacMan. O PacMan é 
excluído.
18/23Prof. Ricardo Mesquita
Gramática de Grafos: PacMan
 Por fim, a figura ao lado ilustra um possível 
grafo resultante da aplicação da regra 
move ao grafo ilustrado na primeira figura 
do exemplo. 
 Observe que, no grafo transformado, o 
PacMan encontra-se em um lugar onde 
existe um fantasma. 
 Assim, a próxima produção a ser aplicada 
pode ser morre ou move.
19/23Prof. Ricardo Mesquita
Gramática de Grafos
 Comparativamente com as gramáticas de Chomsky, as gramáticas de grafos: 
 em geral, não distinguem entre variáveis e terminais (todos os símbolos – no caso, 
grafos – são tratados como terminais); 
 possui um símbolo inicial (no caso, grafo inicial); 
 a linguagem gerada é o conjunto de grafos que podem ser gerados, via derivações, a 
partir do grafo inicial.
20/23Prof. Ricardo Mesquita
Exercício
 Desenvolva uma gramática de grafos para o jogo da velha de tal forma que: 
 considere jogadas alternadas de dois jogadores; 
 apresente condição de parada quando um dos jogadores completa uma linha de três 
casas (horizontal, vertical ou oblíqua).
21/23Prof. Ricardo Mesquita
Exercício
 Desenvolva uma gramática de grafos para o jogo de damas, prevendo que o 
jogador com as pedras brancas inicia o jogo. 
 Dica: na definição da regra “comer uma pedra”, lembre-se de que o movimento é 
sempre em “linha reta” (não pode fazer uma “curva” de 90° no tabuleiro).
22/23Prof. Ricardo Mesquita
Dúvidas?
Prof. Ricardo Mesquita 23/23