O autômato finito determinístico
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
A alternativa correta é a C. Vamos entender o motivo e analisar por que as outras alternativas estão incorretas.
Alternativa C: "Pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado."
Essa é a definição precisa de um Autômato Finito Determinístico (AFD). Em um AFD, para cada estado em que o autômato se encontra e cada símbolo de entrada, existe uma única transição para um novo estado. Ou seja, a função de transição é determinística, não existe ambiguidade sobre qual estado será atingido.
Alternativa 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."
Essa descrição está incorreta para um AFD. Na verdade, ela se refere a um Autômato Finito Não Determinístico (AFN), onde a função de transição pode retornar um conjunto de estados possíveis (ou nenhum estado) para uma dada entrada.
Alternativa B: "Tem a capacidade de adivinhar algo sobre sua entrada ao testar valores."
Essa afirmação é falsa para um AFD. A capacidade de "adivinhar" ou testar múltiplos caminhos simultaneamente é uma característica do Autômato Finito Não Determinístico (AFN) ou de conceitos mais avançados como Máquinas de Turing Não Determinísticas.
Alternativa D: "Permite zero, uma ou n transições para os estados de entrada."
Essa afirmação descreve um Autômato Finito Não Determinístico (AFN), onde uma transição pode resultar em múltiplos estados possíveis, incluindo a possibilidade de não haver transição (zero transições) para uma determinada entrada.
Alternativa E: "Consegue estar em vários estados ao mesmo tempo."
Essa é outra característica de um Autômato Finito Não Determinístico (AFN). Um AFD, por definição, está sempre em apenas um estado por vez, tornando essa alternativa incorreta.
Em resumo, a questão trata da diferença fundamental entre Autômatos Finitos Determinísticos (AFD) e Não Determinísticos (AFN), exigindo conhecimento sobre como a função de transição opera em cada tipo. Entender esses conceitos é crucial para resolver perguntas que envolvem a teoria dos autômatos e linguagens formais.
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Comentários
Veja os comentários dos nossos alunos
não levem a sério, questão muito especifica, acredito que até professores da área poderia não lembrar
Me senti ignorante e humilhado.
Um autômato finito determinístico tem três características pelo seu próprio nome:
1. É um autômato.
2. É finito: ou seja, tem um estado inicial, um conjunto de estados de aceitação, um conjunto finito de estados intermediários e de símbolos de entrada.
3. É determinístico: significa que as regras de transição executadas pela função de transição entre os estados são bem determinadas.
Por definição, gera-se um único ramo de computação para cada cadeia de entrada.Vamos analisar os itens.
- 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.
- A função de transição irá retornar apenas um estado como resultado, devido ao fato do autômato finito determinístico ser determinístico. Significa que, para cada entrada, apenas transita por um conjunto de estados determinado. Falso
- b) tem a capacidade de adivinhar algo sobre sua entrada ao testar valores.
- Um autômato finito determinístico não adivinha informações sobre a entrada. Ele, de posse das informações de entrada, decide, por meio da função de transição, por quais estados percorrerá.Falso.
- c) pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.
- Um autômato finito determinístico, pela definição de ser determinístico, somente pode transitar para um estado para cada entrada. Alternativa correta
- d) permite zero, uma ou n transições para os estados de entrada.
- Um autômato finito determinístico, pela definição de ser determinístico, somente pode transitar para um estado para cada entrada. Portanto, ele não permite nem zero e nem n transições. Falso.
- e) consegue estar em vários estados ao mesmo tempo.
- Somente um estado. Falso
GAB: C
Fonte: PROF.Raphael Henrique Lacerda
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo