Um problema de decisão também pode ser formalizado como o problema de verificar se uma determinada cadeia de caracteres pertence ou não a um conjunto de cadeias de caracteres, também chamado de linguagem formal. O conjunto contém exatamente as cadeias para as quais a resposta à pergunta é 'sim'. Voltando ao exemplo dos números primos proposto anteriormente, pode-se vê-lo também como a linguagem de todas as cadeias no alfabeto {0, 1, 2, ..., 9} tal que o inteiro correspondente à cadeia é um número primo.

Problemas de decisão estão intimamente ligados com problemas de função, que podem ter respostas mais complexas do que um simples 'sim' ou 'não'. Um típico problema de função é "dado dois números x e y, para qual x temos que y é divisível por x?". Esses tipos de problema estão relacionados também com os problemas de otimização, os quais se preocupam em achar a melhor solução para um problema particular.