Turmas - 2º Semestre de 2026Na Teoria da Computação, um autômato finito não-determinístico é uma máquina de estados finita, em que, para cada par de estado e símbolo de entrada podem haver vários próximos estados possíveis. Essa característica o distingue do autômato finito determinístico, em que 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. abb+a+
b. ab*a*
c. abb*a+
d. ab+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 ab*bb*ba*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 símbolo a isolado, por sua vez, denota a ocorrência unitária do próprio símbolo.
2. O termo b*b denota a concatenação de um símbolo b seguido de zero ou mais b's, o que equivale à linguagem de uma ou mais ocorrências de b's, classicamente representada por b+.
3. Analogamente, a ocorrência de a*a representam uma ou mais ocorrências de a's, denotadas por a+.
Dessa forma, a expressão original pode ser reescrita, em notação simplificada, como ab+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 é abb+a+.
Conforme exposto, a análise permite concluir que:
a. abb+a+
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 