Considere os seguintes problemas de decisão: P1: Uma determinada máquina de estado �nito aceita uma determinada cadeia. P2: Uma determinada gramáti...

A alternativa correta é: "Apenas P1 é decidível". O problema de decisão P1 é decidível, pois é possível construir uma máquina de Turing que simula a máquina de estado finito e decide se a cadeia é aceita ou não. Já o problema de decisão P2 não é decidível, pois não há um algoritmo que possa determinar se uma gramática livre de contexto gera um número infinito de cadeias. Isso se deve ao fato de que a propriedade de uma gramática gerar um número infinito de cadeias é uma propriedade semidecidível, ou seja, é possível construir um algoritmo que reconheça essa propriedade, mas não é possível construir um algoritmo que rejeite essa propriedade.