Hierarquia de Chomsky
1
Gramáticas Irrestritas:
Produções
u v
String de variáveis
e terminais
String de variáveis
e terminais
2
Exemplo de gramática irrestrita:
S  aBc
aB  cA
Ac  d
3
Teorema:
Uma linguagem L
é recursivamente enumerável
se e somente se
existe uma gramática irrestrita que gera
L
4
Gramáticas Sensíveis ao Contexto:
Produções
u v
String de variáveis
e terminais
e:
String de variáveis
e terminais
|u|  |v|
5
A linguagem
n n n
{a b c }
é sensível ao contexto:
S  abc | aAbc
Ab  bA
Ac  Bbcc
bB  Bb
aB  aa | aaA
6
Autômato Linear Limitado (LBA)
é o mesmo que uma Máquina de Turing
mas com uma diferença:
o espaço ocupado pelo string de entrada
na fita é o único espaço da fita que pode
ser usado ao longo da computação
7
Autômato Linear Limitado (LBA)
string de entrada
[ a b c d e ]
marcador de
extremidade
esquerda
espaço de
trabalho
na fita
marcador de
extremidade
direita
Toda computação é feita entre os marcadores
8
LBA’s são definidos como Não Deterministas
Problema em aberto:
LBA’s Não Deterministas
têm o mesmo poder de computação
que LBA’s Deterministas ?
9
Exemplos de linguagens aceitas por LBAs:
L  {a b c }
n n n
L  {a }
n!
Conclusão:
LBAs têm mais poder computacional que NPDAs
10
Vamos provar mais adiante:
LBA’s têm menos poder computacional
que Máquinas de Turing
11
Teorema:
Uma linguagem L é sensível ao contexto
se e somente se
L é aceita por um Autômato Linear Limitado
Observação:
Existem linguagens recursivas
mas que não são sensíveis ao contexto
12
Hierarquia de Chomsky
Não Recursivamente Enumerável
Recursivamente Enumerável
Recursiva
Sensível ao Contexto
Livre de Contexto
Regular
13
Decidibilidade
14
Considere problemes com resposta SIM ou NÃO
Exemplos:
• Uma dada Máquina
• Um dado string
• Um dado DFA
M tem 3 estados ?
w é um número binário?
M aceita qualquer entrada?
15
Um problema é decidível se
alguma Máquina de Turing resolve (decide)
este problema
Problemas Decidíveis:
• Uma Máquina
• Um string
• Um DFA
M tem três estados ?
w é um número binário?
M aceita qualquer entrada?
16
A máquina de Turing que resolve um problema
responde SIM ou NÃO para cada instância
Entrada:
instância
do problema
Máquina deTuring
SIM
NÃO
17
A máquina que decide um problema:
• Se a resposta é SIM
pára em um estado SIM
• Se a resposta é NÃO
pára em um estado NÃO
estados SiM e NÃO não necessariamente
são estados finais
18
Máquina de Turing que decide um problema
SIM
NÃO
estados SiM e NÃO são estados de parada
19
Existem problemas não decidíveis:
Problema tal que não existe uma MT
que decida todas as instâncias do problema
20
Um problema não decidível simples:
O problema de pertinência
21
O Problema de Pertinência
Entrada: Máquina de Turing
String
Questão:
M
w
M aceita w ?
22
Teorema:
O problema de pertinência não é decidível
Prova: Suponha, por contradição, que
o problema de pertinência seja decidível
23
Existe uma Máquina de Turing H
que resolve o problema de pertinência
M
SIM
M aceita w
NÃO
M rejeita w
H
w
24
Seja L
uma linguagem recursivamente enumerável
Seja M
uma Máquina de Turing que aceita
L
Vamos provar que, se o problema de pertinência
é decidível, então L é também recursiva:
A prova consiste em descrever uma MT
que aceita L e pára para qualquer entrada
25
Máquina de Turing que aceita
e pára para qualquer entrada
M
H
M aceita w ?
w
SIM
aceita
L
w
NÃO rejeita
w
26
Portanto,
L é recursiva
Como L é escolhida arbitrariamente,
isso prova que
toda linguagem recursivamente enumerável
é também recursiva
Mas já provamos que existem linguagens que
são recursivamente enumeráveis e
não são recursivas
Contradição!!!!
27
Portanto, o problema de pertinência
não é decidível
Fim da Prova
28
Um famoso problema não decidível:
O Problema da Parada
29
O Problema da Parada
Entrada: Máquina de Turing
String
Questão:
M
w
M pára sobre w ?
30
Teorema:
O problema da parada é não decidível
Prova:
Suponha, por contradição, que
o problema da parada seja decidível
31
Existe uma Máquina de Turing H
que resolve o problema da parada
SIM
M
M pára sobre w
H
w
NÃO
M
não
w
pára sobre
32
Máquina
H
H
Entrada: conteúdo
inicial da fita
wM w
q y SIM
q0
qn NÃO
Codificação String
de M
w
33
Construa uma máquina
H'
tal que:
Se H retorna SIM então H ' loop infinito
Se H retorna NÃO então H ' pára
34
H'
Loop infinito
H
q y SIM
wM w
qa
qb
q0
qn NÃO
35
Construa a máquina :
Entrada:
Se
wM
Hˆ
(máquina
M)
M pára para a entrada wM
Então loop infinito
Senão pára
36
Hˆ
wM
copia
wM
wM wM
H
37
Execute
Hˆ com ela própria como entrada:
Entrada:
Se
wHˆ
(máquina
Hˆ )
Hˆ pára para a entrada wHˆ
Então loop infinito
Senão pára
38
Hˆ sobre a entrada wHˆ
Se
Hˆ pára então entra em loop infinito
Se
Hˆ não pára então pára
NÃO FAZ SENTIDO!!!!!
39
Portanto, temos uma contradição
O Problema da Parada é não decidível
Fim da Prova
40
Outra prova do mesmo teorema:
Se o problema da parada fosse decidível
então
toda linguagem recursivamente enumerável
seria também recursiva
41
Teorema:
O problema da parada é não decidível
Prova:
Suponha, por contradição, que
o problema da parada seja decidível
42
Existe uma Máquina deTuring H
que resolve o problema da parada
SIM
M
M pára sobre w
H
w
NÃO
M
não
w
pára sobre
43
Seja L uma linguagem recursamente enumerável
Seja
M uma Máquina de Turing que aceita L
Vamos provar que
L é também recursiva:
vamos descrever uma máquina de Turing
que aceita L e pára para qualquer entrada
44
Máquina de Turing que aceita
e pára para qualquer entrada
M
H
NÃO
M pára sobre w ?
w
L
rejeita
w
aceita
w
SIM
Execute M
sobre w
Pára em estado final
rejeita w
Pára em estado
não final
45
Portanto
L seria recursiva
Como L foi escolhida arbitrariamente,
provamos que toda linguagem recursivamente
enumerável é também recursiva
Mas já provamos que existem linguagens
recursivamente enumeráveis que
não são recursivas
Contradição!!!!
46
Portanto,
o problema da parada é não decidível
Fim da Prova
47