Questões de Concurso Público IFN-MG 2018 para Ciências da Computação: Teoria da Computação

o número de estados de A não pode ser maior do que o número de estados de 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.

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.

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.

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.

a demonstração da tese de Church-Turing permitiu compreender o que pode ser computado com diversos modelos de computação, como a máquina de Turing.

uma Máquina de Turing Universal não determinística pode resolver o Problema da Parada.

uma Máquina de Turing com duas fitas pode resolver o Problema da Parada em tempo polinomial.

o Teorema do Bombeamento pode ser utilizado para mostrar que uma Máquina de Turing não pode reconhecer uma determinada linguagem.

o Teorema de Rice mostra que toda propriedade não trivial é indecidível.