Considere os seguintes problemas de decisão:

P1: Uma determinada máquina de estado finito aceita uma determinada cadeia.

P2: Uma determinada gramática livre de contexto gera um número infinito de cadeias.

Qual das seguintes afirmações é verdadeira?

 Apenas P1 é decidível.

Apenas P2 é decidível.

P1 e P2 não são problemas de decisão.

Nem P1 nem P2 são decidíveis.

Ambos P1 e P2 são decidíveis.