View
123
Download
1
Category
Preview:
Citation preview
1
Linguagens
Recursivamente Enumeráveis
e Recursivas
2
Definição:
Uma linguagem é recursivamente enumerável
se existe alguma Máquina de Turing que aceita tal linguagem
3
Para um string :
Seja uma linguagem recursivamente enumerávelL
e uma Máquina de Turing que a aceitaM
Lw
w
se então pára em um estado finalM
Lwse então pára em estado não final
M
ou entra em loop infinito
4
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
5
Para qualquer string :
Seja uma linguagem recursivaL
e uma máquina de Turing que a aceitaM
Lw
w
se então pára em um estado finalM
Lwse então pára em um estado não final
M
6
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
7
Recursiva
Recursivamente Enumerável
Não Recursivamente Enumerável
8
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
9
Teorema:
Se é uma linguagem recursiva entãoexiste um procedimento de enumeração para
L
L
10
Prova:
MM~
Máquina Enumeradora
Aceita LEnumera todos os strings do alfabeto de entrada
11
Se o alfabeto é então pode enumerar os strings do seguinte modo:
},{ baM~
abaaabbabbaaaaab......
12
Procedimento de Enumeração
Repita:
M~ gera um string
M
w
verifica se Lw
SIM: imprime na saídaw
NÃO: ignoraw
Fim da Prova
13
Exemplo:
M~
abaaabbabbaaaaab......
)(ML
b
ab
bbaaa
......
,....},,,{ aaabbabbL Saída do
Enumerador
b
ab
bbaaa
......
14
Teorema:
Se uma linguagem é recursivamente enumerável entãoexiste um procedimento de enumeração para ela
L
15
Prova:
MM~
Máquina Enumeradora
Aceita LEnumera todos os stringsdo alfabeto de entrada
16
Se o alfabeto é então pode enumerar os strings como:
},{ baM~
abaaabbabbaaaaab
17
Procedimento de Enumeração
Repita: M~ gera um string
M
w
verifica se Lw
SIM: imprime na saídaw
NÃO: ignora w
ABORDAGEM INGÊNUA
Problema:Se a máquina pode ficar em loop
LwM
18
M~
M
1w
executa o 1o. passo sobre
ABORDAGEM MELHOR
1w
M~ Gera o segundo string 2w
M executa o 1o. passo sobre 2w
e o 2o. passo sobre 1w
Gera o primeiro string
19
M~ Gera o terceiro string 3w
M executa o 1o. passo sobre 3w
o 2o. passo sobre 2w
o 3o. passo sobre 1w
E assim por diante............
20
1w 2w 3w 4w
1
Passo nostring
1 1 1
2 2 2 2
3 3 3 3
21
Se, para um dado string ,a máquina pára em um estado final,então ela imprime na fita de saída
Miw
iw
Fim da Prova
22
Teorema:
Se existe um procedimento de enumeraçãopara uma linguagem então é recursivamente enumerável
L
L
23
Prova:
wfita de entrada
Enumeradorpara L
Compara
Máquina queaceita L
24
Máquina de Turing que aceita L
Repita:
• Usando o enumerador, gere o próximo string de L
Para um string de entrada w
• Compare o string gerado comw
Se for igual, aceite e termine o loop
Fim da Prova
25
Provamos:
Uma linguagem é recursivamente enumerávelse e somente seexiste um procedimento de enumeração p/
L
L
26
Uma Linguagem que não é
Recursivamente Enumerável
27
Queremos encontrar uma linguagem quenão seja Recursivamente Enumerável
Tal linguagem não é aceita por nenhumaMáquina de Turing
28
Considere o alfabeto }{a
Strings: ,,,, aaaaaaaaaa
1a 2a 3a 4a
29
Considere as Máquinas de Turingque aceitam linguagens sobre o alfabeto }{a
Esse conjunto de MTs é contável:
,,,, 4321 MMMM
30
Exemplo de linguagem aceita por
},,{)( aaaaaaaaaaaaML i
},,{)( 642 aaaML i
iM
Representação alternativa
1a 2a 3a 4a 5a 6a 7a
)( iML
0 1 1 10 0 0
31
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
32
Considere a linguagem
)}(:{ iii MLaaL
Lconsiste dos strings que têm 1 na diagonal
33
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
},,{ 43 aaL
34
Considere a linguagem
)}(:{ iii MLaaL
Lconsiste dos strings que têm 0 na diagonal
)}(:{ iii MLaaL
L
35
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
},,{ 21 aaL
36
Teorema:
A linguagem não é recursivamente enumerável
L
37
Prova:
seja recursivamente enumerávelL
Suponha por contradição que
Então deve existir alguma máquinaque aceita
kML
LML k )(
38
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
Questão: ?1MMk
39
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
Resposta: 1MMk )(
)(
11
1
MLa
MLa k
40
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
Questão: ?2MMk
41
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
Resposta: 2MMk )(
)(
22
2
MLa
MLa k
42
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
Questão: ?3MMk
43
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
Resposta: 3MMk )(
)(
33
3
MLa
MLa k
44
De maneira análoga: ik MM
)(
)(
ii
ki
MLa
MLa
)(
)(
ii
ki
MLa
MLa
para qualquer i
Porque temos que:
ou
45
Então, a máquina não pode existir kM
Portanto, a linguagemnão é recursivamente enumerável
L
Fim da Prova
46
Observação:
Não existe algoritmo que descrevaL
(caso contrário seria aceita por alguma Máquina de Turing)
L
47
Recursiva
Recursivamente Enumerável
Não Recursivamente Enumerável
L
48
Uma Linguagem que é Recursivamente
Enumerável e não é Recursiva
49
Queremos encontrar uma linguagem que seja
Existe uma MT que aceita a linguagem
A máquina não pára paraalguma entrada
recursivamente enumerável
mas nãorecursiva
50
Vamos provar que a linguagem
)}(:{ iii MLaaL
É recursivamente enumerávelmas não recursiva
51
1a 2a 3a 4a
)( 1ML
0 1 10
)( 2ML
)( 3ML
01 0 1
0 1 11
)( 4ML 0 10 0
},,{ 43 aaL
52
A linguagem
Teorema:
)}(:{ iii MLaaL
é recursivamente enumerável
53
Prova:
Vamos mostrar uma Máquina de Turing que aceita L
54
Máquina de Turing que aceita LPara qualquer string w
• Compute , para o qualiaw
• Encontre a Máquina de Turing iM(usando o procedimento de enumeração para máquinas de Turing)
• Simule sobre a entradaiM ia
• Se aceita, então aceitaiM w
i
Fim da Prova
55
Observação:
)}(:{ iii MLaaL
)}(:{ iii MLaaL
Recursivamente enumerável
Não recursivamente enumerável
(Portanto, não recursiva)
56
Teorema:
A linguagem )}(:{ iii MLaaL
não é recursiva
57
Prova:
Suponha por contradição que seja recursiva
Então é recursiva:
L
L
Tome a Máquina de Turing que aceita M L
pára para qualquer entrada:M
Se aceita então rejeitaSe rejeita então aceita
MM
58
Portanto:
L seria recursiva
Mas sabemos que:
Lnão é recursivamente enumerável
e, portanto, não é recursiva
CONTRADIÇÃO!!!!
59
Portanto, não é recursivaL
Fim da Prova
60
L
Recursiva
Recursivamente Enumerável
Não Recursivamente Enumerável
L
Recommended