O autômato finito determinístico
- A)corresponde à função de transição que recebe um estado ou um símbolo de entrada que sempre retorna um conjunto de estados como resultado.
Errada, porque descreve uma transição que retorna um conjunto de estados, o que é característica de autômato não determinístico, não determinístico.
- B)tem a capacidade de adivinhar algo sobre sua entrada ao testar valores.
Errada, porque autômato finito determinístico não “adivinha” nada; ele segue uma transição única definida pela entrada lida.
- C)pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.
Certa, pois no AFD cada símbolo lido a partir do estado atual leva a um único próximo estado.
- D)permite zero, uma ou n transições para os estados de entrada.
Errada, porque permitir zero, uma ou várias transições é traço de não determinismo, não de determinismo.
- E)consegue estar em vários estados ao mesmo tempo.
Errada, porque estar em vários estados ao mesmo tempo é característica de autômato não determinístico.
Gabarito: C
O autômato finito determinístico, ou AFD, é o modelo mais “certinho” da turma: para cada estado e para cada símbolo de entrada, existe uma única transição possível. Nada de dúvida, nada de lote de caminhos, nada de adivinhação. Ele lê a entrada passo a passo e vai mudando de estado de forma bem previsível. A ideia central do determinismo é justamente essa: dado o estado atual e o próximo símbolo lido, o próximo estado é único. Em termos formais, a função de transição de um AFD leva um estado e um símbolo de entrada para um único estado. Isso aparece na teoria dos autômatos como uma função do tipo delta(q, a) = q'. Por isso, o gabarito é a letra C. Ela descreve exatamente o comportamento determinístico: para cada entrada, o autômato transita do estado atual para um e somente um estado. Se houvesse várias possibilidades de transição, já estaríamos falando de não determinismo. Vale lembrar a diferença clássica: no autômato finito não determinístico, pode haver mais de uma transição possível para o mesmo símbolo, inclusive nenhuma. No determinístico, a regra é a unicidade. É uma distinção muito cobrada em prova, porque a banca adora trocar um por vários e ver quem escorrega.