Turmas - 2º Semestre de 2026Na Teoria da Computação, um autômato finito não-determinístico é uma máquina de estados finita, onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Essa característica o distingue do autômato finito determinístico, onde o próximo estado possível é univocamente determinado. Autômatos finitos não-determinísticos reconhecem exatamente o conjunto de linguagens regulares que são, dentre outras coisas, úteis para a realização da análise léxica e reconhecimento de padrões. Qual expressão regular é equivalente ao autômato finito não-determinístico apresentado a seguir?
M = ({a, b}, {q0, q1, q2, q3, q4}, δ, q0, {q4})
a. a*b*a
b. a+bb+a
c. a+bb*a
d. a+b+a
e. a*(bb)*a
Inicialmente, determina-se a expressão regular derivada diretamente do Autômato Finito Não-Determinístico fornecido, a qual corresponde a aa*bb*bb*a. Visto que nenhuma das alternativas apresenta equivalência sintática imediata à expressão obtida, procede-se à sua simplificação por meio da análise algébrica de seus componentes:
1. O termo aa* denota a concatenação de um símbolo a seguido de zero ou mais a's, o que equivale à linguagem de uma ou mais ocorrências de a's, classicamente representada por a+.
2. Analogamente, as ocorrências de bb* representam uma ou mais ocorrências de b's, denotadas por b+.
3. O símbolo a isolado, por sua vez, denota a ocorrência unitária do próprio símbolo.
Dessa forma, a expressão original pode ser reescrita, em notação simplificada, como a+b+b+a.
Observa-se que a justaposição b+b+ é redundante, uma vez que a concatenação de duas sequências de um ou mais b's resulta em uma linguagem já estritamente contida em bb+ ou b+b. Portanto, o bloco b+b+ pode ser reduzido a bb+. Consequentemente, a expressão regular simplificada final é a+bb+a.
Conforme exposto, a análise permite concluir que:
b. a+bb+a
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 