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).

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 L_{1} e L_{2} recursivas, com decisores M_{1} e M_{2}.
Para L_{1}\cup L_{2}: no input w, execute M_{1}(w); se aceitar, aceite; senão execute M_{2}(w) e aceite ou rejeite conforme M_{2}. Como ambos sempre param, o procedimento pára.
Para L_{1}\cap L_{2}: no input w, execute M_{1}(w); se rejeitar, rejeite; senão execute M_{2}(w) e aceite só se M_{2} aceita. Novamente há parada garantida.

Passo 3

Fechamento em complemento: seja L recursiva com decisor M. Basta construir M' que, em cada entrada w, roda M(w) e inverte o resultado (aceita vira rejeita e vice-versa). Como M sempre pára, M' também pára.

Passo 4

Fechamento em concatenação: sejam L_{1} e L_{2} recursivas com decisores M_{1} e M_{2}. Para decidir se w\in L_{1}\cdot L_{2}, faça: para cada i de 0 até \lvert w\rvert, separe w em w[1..i] e w[i+1..\lvert w\rvert]; rode M_{1} no primeiro pedaço e M_{2} no segundo. Se em alguma divisão ambos aceitarem, aceite; caso contrário, rejeite. Há só \lvert w\rvert+1 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).

Exercícios relacionados