Verificar se uma linguagem é regular é fundamental, pois, em caso positivo, será possível solucionar determinado problema de forma simples e com tempo de execução ótimo. Existem algumas maneiras de verificar se uma linguagem é regular. Um exemplo é por meio do uso de AFDs. Por outro lado, há a possibilidade de verificar se dada linguagem é não regular. Para isso, uma das formas mais utilizadas é o lema do bombeamento. Com base Σ = {a, b}, analise as linguagens a seguir e marque a opção referente a uma linguagem não regular.

Queremos identificar uma linguagem não regular (Σ = {a,b}).

Ideia-chave: linguagens que exigem “contagem e comparação exata” entre quantidades de símbolos (como ter o mesmo número de $a$’s e $b$’s) tipicamente não são regulares, pois um AFD tem memória finita e não consegue armazenar uma diferença arbitrariamente grande entre contagens.

Analisando as opções:

a) $L_1 = \{w \mid w$ inicia com $b$ e termina com $a\}$

• Regular: basta um AFD que verifica o primeiro símbolo ($b$) e mantém informação sobre o último símbolo lido para aceitar se terminar em $a$.

b) $L_2 = \{w \mid w$ possui número par de $a$ e número par de $b\}$

• Regular: AFD com 4 estados representando as paridades (par/ímpar) de $a$ e de $b$ (produto cartesiano de duas máquinas de paridade).

c) $L_3 = \{w \mid w$ possui $aa$ ou $bb$ como subcadeia}$

• Regular: AFD que “lembra” o último símbolo e aceita ao ver repetição ($aa$ ou $bb$).

d) $L_4 = \{w \mid w$ possui $aaa$ como sufixo}$

• Regular: AFD com estados que acompanham quantos $a$’s consecutivos no final foram vistos (0,1,2,3), aceitando quando termina exatamente com 3 $a$’s.

e) $L_5 = \{w \mid \#a(w) = \#b(w)\}$

• Não regular: exige comparar duas contagens potencialmente arbitrárias.
• Esboço via lema do bombeamento: escolha a palavra $s=a^p b^p$ (com $p$ o comprimento de bombeamento). Para qualquer decomposição $s=xyz$ com $|xy|\le p$ e $|y|\ge 1$, o trecho $y$ fica só em $a$’s. Ao bombear ($i=2$), obtemos mais $a$’s que $b$’s, logo $xy^2z \notin L_5$, contradizendo o lema. Portanto, $L_5$ não é regular.

Alternativa correta: (e).