Qual operação NÃO é fechada para linguagens recursivas?
a) União.
b) Interseção.
c) Complemento.
d) Concatenação.
e) Nenhuma das anteriores (todas são fechadas).
a) União.
b) Interseção.
c) Complemento.
d) Concatenação.
e) Nenhuma das anteriores (todas são fechadas).
Passo 1
O enunciado pergunta qual das operações dadas não é fechada no conjunto das linguagens recursivas (decidíveis). Vamos usar o fato de que uma linguagem é recursiva se existe uma máquina de Turing que sempre pára (decisor). Para provar fechamento, mostramos como construir decisores para cada operação a partir de decisores das linguagens originais.
Passo 2
Fechamento em união e interseção: sejam
e
recursivas, com decisores
e
.
Para : no input
, execute
; se aceitar, aceite; senão execute
e aceite ou rejeite conforme
. Como ambos sempre param, o procedimento pára.
Para : no input
, execute
; se rejeitar, rejeite; senão execute
e aceite só se
aceita. Novamente há parada garantida.
Para
Para
Passo 3
Fechamento em complemento: seja
recursiva com decisor
. Basta construir
que, em cada entrada
, roda
e inverte o resultado (aceita vira rejeita e vice-versa). Como
sempre pára,
também pára.
Passo 4
Fechamento em concatenação: sejam
e
recursivas com decisores
e
. Para decidir se
, faça: para cada
de
até
, separe
em
e
; rode
no primeiro pedaço e
no segundo. Se em alguma divisão ambos aceitarem, aceite; caso contrário, rejeite. Há só
testes e cada decisor pára, logo este procedimento também pára.
Passo 5
Como mostramos fechamento em união, interseção, complemento e concatenação, todas as operações listadas são fechadas para linguagens recursivas.
Resposta
e) Nenhuma das anteriores (todas são fechadas).