Questões de Concurso Comentadas para cientista da computação
Foram encontradas 206 questões
Resolva questões gratuitamente!
Junte-se a mais de 4 milhões de concurseiros!
Seja A um autômato finito não determinístico que reconhece uma linguagem L. Seja B um autômato finito determinístico que reconhece a mesma linguagem.
Sobre o número de estados de A e de B, é correto afirmar que
Sejam A e B duas linguagens sobre o alfabeto binário, isto é, sobre o alfabeto composto apenas por 0’s e 1’s. Seja A a linguagem na qual a quantidade de 0’s e 1’s é igual. Seja B a linguagem onde nenhum 0 ocorre após um caractere 1.
Sobre essas linguagens, é correto afirmar que
Avalie as afirmações abaixo:
I. A classe P e a classe NP são disjuntas.
II. A classe P é um subconjunto da classe co-NP.
III. Problemas coNP-completos admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial.
IV. A interseção das classes NP e co-NP é vazia.
Está correto apenas o que se afirma em