Linguagens
Recursivamente Enumeráveis
e
Recursivas
1
Definição:
Uma linguagem é
recursivamente enumerável
se existe alguma Máquina de Turing
que aceita tal linguagem
2
Seja
L uma linguagem recursivamente enumerável
e
M uma Máquina de Turing que a aceita
Para um string
w:
se
w L então M pára em um estado final
se
w L
então
M pára em estado não final
ou entra em loop infinito
3
Definição:
Uma linguagem é
recursiva
se existe uma MT que aceita a linguagem e
que pára para qualquer string de entrada
Em outras palavras:
Uma linguagem é recursiva se existe um
algoritmo de pertinência para essa linguagem
4
Seja
e
L uma linguagem recursiva
M uma máquina de Turing que a aceita
Para qualquer string
w :
se
w L então M pára em um estado final
se
w L
então M pára em um estado não final
5
Vamos provar que:
1. Existe uma linguagem específica
que não é recursivamente enumerável
(não é aceita por nenhuma Máquina de Turing)
2. Existe uma linguagem específica
que é recursivamente enumerável
mas não é recursiva
6
Não Recursivamente Enumerável
Recursivamente Enumerável
Recursiva
7
Primeiro vamos provar provar:
• Se uma linguagem é recursiva então existe
um procedimento de enumeração para ela
• Uma linguagem é recursivamente enumerável
se e somente se existe
um procedimento de enumeração para ela
8
Teorema:
Se L é uma linguagem recursiva
então
existe um procedimento de enumeração
para L
9
Prova:
Máquina Enumeradora
~
M
Enumera todos os strings
do alfabeto de entrada
M
Aceita
L
10
Se o alfabeto é {a, b} então
~
M pode enumerar os strings do seguinte modo:
a
b
aa
ab
ba
bb
aaa
aab
......
11
Procedimento de Enumeração
Repita:
~ gera um string w
M
M verifica se w L
SIM: imprime
NÃO:
w na saída
ignoraw
Fim da Prova
12
Exemplo:
~
M
a
b
aa
ab
ba
bb
aaa
aab
......
L  {b, ab, bb, aaa,....}
L(M )
Saída do
Enumerador
b
b
ab
ab
bb
aaa
bb
aaa
......
......
13
Teorema:
Se uma linguagem L
é recursivamente enumerável então
existe um procedimento de enumeração para ela
14
Prova:
Máquina Enumeradora
~
M
Enumera todos os strings
do alfabeto de entrada
M
Aceita
L
15
Se o alfabeto é {a, b} então
~ pode enumerar os strings como:
M
a
b
aa
ab
ba
bb
aaa
aab
16
ABORDAGEM INGÊNUA
Procedimento de Enumeração
Repita:
~ gera um string w
M
M verifica se w L
SIM: imprime
NÃO: ignora
Problema: Se w L
a máquina
w na saída
w
M pode ficar em loop
17
ABORDAGEM MELHOR
~ Gera o primeiro string w
M
1
M executa o 1o. passo sobre w1
~ Gera o segundo string w
M
2
M executa o 1o. passo sobre w2
e o 2o. passo sobre
w1
18
~ Gera o terceiro string
M
w3
M executa o 1o. passo sobre w3
o 2o. passo sobre
w2
o 3o. passo sobre
w1
E assim por diante............
19
Passo
no
string

w1
w2
w3
w4
1
1
1
1
2
2
2
2
3
3
3
3

20
Se, para um dado string wi ,
a máquina M pára em um estado final,
então ela imprime wi na fita de saída
Fim da Prova
21
Teorema:
Se existe um procedimento de enumeração
para uma linguagem L
então L é recursivamente enumerável
22
Prova:
fita de entrada
w
Máquina que
aceita L
Enumerador
para L
Compara
23
Máquina de Turing que aceita L
Para um string de entrada
w
Repita:
• Usando o enumerador,
gere o próximo string de
L
• Compare o string gerado com
w
Se for igual, aceite e termine o loop
Fim da Prova
24
Provamos:
Uma linguagem L é recursivamente enumerável
se e somente se
existe um procedimento de enumeração p/ L
25
Uma Linguagem que
não é
Recursivamente Enumerável
26
Queremos encontrar uma linguagem que
não seja Recursivamente Enumerável
Tal linguagem não é aceita por nenhuma
Máquina de Turing
27
Considere o alfabeto
Strings:
{a}
a, aa, aaa, aaaa, 
1
a a
2
a
3
a
4

28
Considere as Máquinas de Turing
que aceitam linguagens sobre o alfabeto {a}
Esse conjunto de MTs é contável:
M1, M 2 , M 3 , M 4 , 
29
Exemplo de linguagem aceita por
Mi
L(M i )  {aa, aaaa, aaaaaa}
L( M i )  {a , a , a }
2
4
6
Representação alternativa
1
2
a
a
L( M i ) 0
1
a
3
0
4
a
1
0
a
5
a
6
1
a
7
0


30
1
a
a
2
3
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

a
4

31
Considere a linguagem
L  {a : a  L( M i )}
i
i
L consiste dos strings que têm 1 na diagonal
32
1
2
3
4

a
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

a
L  {a , a ,}
3
a
4
33
Considere a linguagem
L
L  {a : a  L( M i )}
i
i
L  {a : a  L( M i )}
i
i
L consiste dos strings que têm 0 na diagonal
34
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
L  {a , a ,}
1
a
4

2
35
Teorema:
A linguagem L não é
recursivamente enumerável
36
Prova:
Suponha por contradição que
L
seja recursivamente enumerável
Então deve existir alguma máquina
que aceita L
L( M k )  L
Mk
37
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

Questão:
3
a
4

M k  M1 ?
38
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

1
Resposta: M k  M1
a  L( M k )
1
a  L ( M1 )
39
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

Questão: M k  M 2 ?
40
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

2
Resposta: M k  M 2
a  L( M k )
2
a  L( M 2 )
41
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

Questão: M k  M 3 ?
42
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

3
Resposta: M k  M 3
a  L( M k )
3
a  L( M 3 )
43
De maneira análoga:
M k  Mi
para qualquer i
Porque temos que:
a  L( M k )
i
a  L( M i )
i
a  L( M k )
i
ou
a  L( M i )
i
44
Então, a máquina
M k não pode existir
Portanto, a linguagem L
não é recursivamente enumerável
Fim da Prova
45
Observação:
Não existe algoritmo que descreva
L
(caso contrário L seria aceita por
alguma Máquina de Turing)
46
Não Recursivamente Enumerável
L
Recursivamente Enumerável
Recursiva
47
Uma Linguagem que é
Recursivamente Enumerável
e não é Recursiva
48
Queremos encontrar uma linguagem L que seja
recursivamente
enumerável
Existe uma MT M
que aceita
a linguagem L
mas não
recursiva
A máquina M
não pára para
alguma entrada
49
Vamos provar que a linguagem
L  {a : a  L( M i )}
i
i
É recursivamente enumerável
mas não recursiva
50
1
2
3
4

a
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

a
L  {a , a ,}
3
a
4
51
Teorema:
A linguagem
L  {a : a  L( M i )}
i
i
é recursivamente enumerável
52
Prova:
Vamos mostrar uma Máquina de Turing
que aceita L
53
Máquina de Turing que aceita
Para qualquer string
L
w
• Compute i , para o qual
wa
i
• Encontre a Máquina de Turing
Mi
(usando o procedimento de enumeração
para máquinas de Turing)
• Simule
Mi
• Se
aceita, então aceita
Mi
sobre a entrada
Fim da Prova
a
i
w
54
Observação:
Recursivamente enumerável
i
i
L  {a : a  L( M i )}
Não recursivamente enumerável
i
i
L  {a : a  L( M i )}
(Portanto, não recursiva)
55
Teorema:
A linguagem
L  {a : a  L( M i )}
i
i
não é recursiva
56
Prova:
Suponha por contradição que
Então
L
L seja recursiva
é recursiva:
Tome a Máquina de Turing
M que aceita L
M pára para qualquer entrada:
Se
Se
M aceita então rejeita
M rejeita então aceita
57
Portanto:
L seria recursiva
Mas sabemos que:
L não é recursivamente enumerável
e, portanto, não é recursiva
CONTRADIÇÃO!!!!
58
Portanto,
L não é recursiva
Fim da Prova
59
Não Recursivamente Enumerável
L
Recursivamente Enumerável
L
Recursiva
60