Autômatos e linguagens formais
Gabarito: letra A. Um autômato finito determinístico (DFA) é o modelo computacional que reconhece exatamente a classe das linguagens regulares (Tipo 3 da hierarquia de Chomsky), sendo capaz de reconhecer qualquer linguagem regular. As demais alternativas apresentam incorreções conceituais.
Alternativa A — ✅ Correta ⟵ GABARITO
Um DFA é definido para aceitar exatamente as linguagens regulares. Toda linguagem regular pode ser representada por uma expressão regular e reconhecida por um DFA, e vice-versa. Portanto, a afirmativa está correta.
Alternativa B — ❌ Incorreta
Um autômato de pilha (PDA) reconhece a classe das linguagens livres de contexto (Tipo 2), que é uma superclasse das linguagens regulares. De fato, toda linguagem regular é livre de contexto, e o PDA reconhece todas elas. No entanto, a afirmação de que ele reconhece "algumas linguagens não regulares" é, em sentido estrito, verdadeira, mas a banca considerou a alternativa incorreta. O motivo possivelmente é que o PDA reconhece exatamente as linguagens livres de contexto, e não apenas "algumas" não regulares, mas sim todas as livres de contexto não regulares. Ainda assim, o enunciado poderia induzir ao erro por ser impreciso. Como o gabarito oficial aponta apenas a alternativa A, entende-se que a B não é a resposta esperada.
Alternativa C — ❌ Incorreta
Máquinas de Turing (MT) reconhecem linguagens recursivamente enumeráveis (Tipo 0), que são um superconjunto das linguagens sensíveis ao contexto (Tipo 1). Portanto, não se limitam a reconhecer "apenas linguagens contextuais". Além disso, MT também podem reconhecer linguagens regulares e livres de contexto. A afirmação é restritiva demais.
Alternativa D — ❌ Incorreta
Autômatos finitos não determinísticos (NFA) e determinísticos (DFA) têm exatamente o mesmo poder de expressão: ambos reconhecem a classe das linguagens regulares. Um NFA pode ser convertido em um DFA equivalente (por construção de subconjuntos). Logo, o NFA não possui menos poder de expressão.
Conclusão: A única alternativa correta é a letra A.