Pergunta 1 1. O que caracteriza uma linguagem como "decidível" na teoria da computação? a. A linguagem pode ser escrita em vários idiomas diferen...
Pergunta 1
1. O que caracteriza uma linguagem como "decidível" na teoria da computação?
a. A linguagem pode ser escrita em vários idiomas diferentes.
b. A linguagem pode ser lida por seres humanos sem esforço.
c. Existe um algoritmo que, quando aplicado a uma cadeia de entrada, sempre para e decide se a cadeia pertence à linguagem ou não.
d. A linguagem é usada para comunicação internacional.
e. A linguagem é reconhecida, exclusivamente, por uma máquina de Turing não determinística.
1. O que caracteriza uma linguagem como "decidível" na teoria da computação?
a. A linguagem pode ser escrita em vários idiomas diferentes.
b. A linguagem pode ser lida por seres humanos sem esforço.
c. Existe um algoritmo que, quando aplicado a uma cadeia de entrada, sempre para e decide se a cadeia pertence à linguagem ou não.
d. A linguagem é usada para comunicação internacional.
e. A linguagem é reconhecida, exclusivamente, por uma máquina de Turing não determinística.
💡 1 Resposta
Ed 
A alternativa correta é a letra c: "Existe um algoritmo que, quando aplicado a uma cadeia de entrada, sempre para e decide se a cadeia pertence à linguagem ou não." Uma linguagem é decidível se existe um algoritmo que pode determinar se uma cadeia de entrada pertence ou não à linguagem. Isso significa que o algoritmo sempre para e dá uma resposta definitiva, seja ela "sim" ou "não". As outras alternativas não caracterizam uma linguagem como decidível na teoria da computação.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
Compartilhar