Questão de Sistemas de Informação — Conceito de TI e SI — FCM 2018
Sistemas de InformaçãoConceito de TI e SI
- Código
- qq337480
- Banca
- FCM
- Órgão
- IFN-MG
- Ano
- 2018
- Nível
- Superior
- Cargo
- Ciências da Computação: Teoria da Computação
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
- Ao número de estados de A não pode ser maior do que o número de estados de B.
- Bse 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.
- Cse 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.
- Dse 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.
- Ese 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.