Questão 2876698

• Banca: FCM
• Órgão: IFN-MG
• Ano: 2018
• Provas: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação
• Disciplina: Sistemas de Informação
• Assuntos: Conceito de TI e SI

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

• A. o número de estados de A não pode ser maior do que o número de estados de B.
• B. se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, então ambos têm o mesmo número de estados.
• C. se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, o número de estados de A e B não pode ser igual.
• D. se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, o número de estados de B é no máximo o dobro do número de estados de A.
• E. se A tem o menor número de estados dentre todos os autômatos finitos não determinísticos que reconhecem L, e se B tem o menor número de estados dentre todos os autômatos finitos determinísticos que reconhecem L, o número de estados de B pode ser exponencial no número de estados de A.

Gabarito: E

Comentários

• GAB. E.