Questão de Programação — Assembly — CESPE / CEBRASPE 2024

Máquina de estados finitos: Moore × Mealy

Gabarito: letra B. O diagrama descreve uma máquina de estados finitos em que as saídas (True/False) estão associadas aos estados (É_Positivo e Início), e não às transições — essa é a característica definidora de uma máquina de Moore. A distinção central entre Moore e Mealy está em onde a saída é gerada: na Moore, a saída depende apenas do estado atual; na Mealy, depende do estado e da entrada que dispara a transição.

Uma máquina de estados finitos (FSM) é um modelo computacional composto por um conjunto finito de estados, um conjunto de transições entre eles e regras de saída. Ela é amplamente usada para representar processos sequenciais, como o fluxo de verificação de um número descrito no enunciado. A pergunta explora exatamente a classificação da máquina quanto ao local de produção da saída — se nos estados ou nas transições.

Na máquina de Moore, cada estado possui uma saída fixa associada a ele. Ou seja, ao entrar em um estado, a saída é determinada imediatamente, independentemente da entrada que causou a transição. No diagrama da questão, os estados são "Início" e "É_Positivo", e as saídas "False" e "True" estão rotuladas dentro desses estados — o que confirma o modelo de Moore. Já na máquina de Mealy, a saída é produzida durante a transição, ou seja, depende tanto do estado atual quanto do símbolo de entrada que aciona a mudança de estado.

Para fixar a diferença, considere um exemplo prático: imagine uma máquina que detecta se um número é positivo. Em uma máquina de Moore, o estado "É_Positivo" teria a saída "True" fixa, e o estado "Início" teria a saída "False" fixa. Ao ler o número, a máquina transita para o estado correspondente e a saída é lida do estado. Em uma máquina de Mealy, a saída "True" ou "False" seria gerada no momento da transição, dependendo do valor lido — por exemplo, ao ler um número maior que zero, a transição de "Início" para "É_Positivo" produziria "True" como saída.

A pegadinha da banca está em inverter os conceitos: as alternativas A e D tentam classificar a máquina como Mealy, quando na verdade ela é Moore. A alternativa C sugere um estado não alcançável, o que não se aplica ao diagrama, pois todos os estados são alcançáveis a partir do estado inicial. A alternativa E afirma que o diagrama é acíclico, mas o diagrama apresenta um ciclo (de É_Positivo de volta a Início), o que o torna cíclico.

Guarde a fronteira decisiva: saída no estado = Moore; saída na transição = Mealy. É exatamente nesse critério que as alternativas se dividem.

Alternativa A — ❌ Incorreta

Afirma que os estados Início e É_Positivo são de uma máquina de Mealy. O erro está na classificação: na máquina de Mealy, a saída é associada às transições, não aos estados. No diagrama, as saídas "False" e "True" estão associadas aos estados, o que caracteriza uma máquina de Moore. A banca troca o conceito de Moore por Mealy para confundir o candidato.

Alternativa B — ✅ Correta ⟵ GABARITO

Correta porque os estados Início e É_Positivo possuem saídas associadas a eles (False e True, respectivamente), o que é a definição de máquina de Moore. Na máquina de Moore, a saída depende apenas do estado atual, e é exatamente isso que o diagrama representa.

Alternativa C — ❌ Incorreta

Afirma que o diagrama possui um estado não alcançável. No diagrama, todos os estados são alcançáveis a partir do estado inicial "Início". O estado "É_Positivo" é alcançável por uma transição a partir de "Início", e o estado "Início" é o estado inicial, portanto, alcançável por definição. Não há estado inacessível no diagrama.

Alternativa D — ❌ Incorreta

Afirma que os estados False e True representam uma máquina de Mealy. O erro é duplo: primeiro, False e True são saídas, não estados — os estados são Início e É_Positivo. Segundo, a máquina é de Moore, não de Mealy, pois as saídas estão associadas aos estados. A alternativa confunde o papel de estados e saídas no diagrama.

Alternativa E — ❌ Incorreta

Afirma que o diagrama é acíclico. O diagrama apresenta um ciclo: do estado É_Positivo há uma transição de volta ao estado Início. Um grafo acíclico não possui ciclos, mas o diagrama claramente possui um, o que torna a afirmação falsa. A presença do ciclo é essencial para o processo de verificação, que pode ser repetido para diferentes números.

Gabarito: letra B