Converta as seguintes expressões regulares em AFNs.
a(b a) * b

Passo 1

O que o enunciado pede: converter a expressão regular a(ba)^*b em um AFN (autômato finito não determinístico).
Informações dadas: a única expressão é a(ba)^*b. Não há figura nem restrição adicional. O objetivo é entregar um AFN que reconheça exatamente a linguagem descrita por a(ba)^*b.

Passo 2

Ideia geral e ferramenta que vou usar (explicação didática): vou aplicar a construção de Thompson, que é uma maneira sistemática de transformar expressões regulares em AFNs usando estados e transições \epsilon (transições vazias). Regras básicas da construção de Thompson (explicadas de forma simples):
  • Para um símbolo único, por exemplo \,a, o AFN é dois estados com uma transição por \,a entre eles.
  • Para concatenação R S, você liga o estado final de R ao estado inicial de S por uma transição \epsilon.
  • Para união R+S, cria-se um novo início com \epsilon para os inícios de R e S, e os finais de R e S apontam por \epsilon para um novo estado final.
  • Para estrela de Kleene R^*, cria-se um novo início e um novo fim; do novo início há \epsilon para o início de R e para o novo fim (permitindo zero repetições); do fim de R \epsilon para o início de R (loop) e para o novo fim.
    Exemplo simples: para (ba)^* vamos aplicar a regra da concatenação para formar b seguido de a, e então aplicar a regra da estrela.

Passo 3

Construção dos blocos atômicos:
  • AFN para \,a: criaremos dois estados q_0 e q_1 com a transição
q_0 \xrightarrow{a} q_1.
Esse será o bloco correspondente ao primeiro \,a da expressão a(ba)^*b.
  • AFN para \,b (usado dentro de ba e também no final): criaremos um par de estados para cada ocorrência quando necessário (vou numerar globalmente abaixo).

Passo 4

Construção do bloco ba (concatenação de \,b e \,a):
  • Crio estados q_2 e q_3 com
q_2 \xrightarrow{b} q_3.
  • Crio estados q_4 e q_5 com
q_4 \xrightarrow{a} q_5.
  • Para concatenar b seguido de a faço uma transição \epsilon do final do bloco b para o início do bloco a:
q_3 \xrightarrow{\epsilon} q_4.
Assim o bloco ba vai de q_2 (início) a q_5 (fim).

Passo 5

Aplicar a estrela de Kleene em ba para obter (ba)^* (usando a regra da estrela de Thompson):
  • Crio um novo estado inicial do bloco da estrela q_6 e um novo estado final do bloco da estrela q_7.
  • Adiciono as transições \epsilon clássicas:
q_6 \xrightarrow{\epsilon} q_2,\quad q_6 \xrightarrow{\epsilon} q_7,
q_5 \xrightarrow{\epsilon} q_2,\quad q_5 \xrightarrow{\epsilon} q_7.
Explicação didática: isso permite escolher zero repetições (via q_6 \xrightarrow{\epsilon} q_7) ou entrar no bloco ba (via q_6 \xrightarrow{\epsilon} q_2); ao terminar um ba em q_5 podemos voltar a começar outro ba (loop q_5 \xrightarrow{\epsilon} q_2) ou sair para o fim da estrela (via q_5 \xrightarrow{\epsilon} q_7).

Passo 6

Concatenar tudo: temos a expressão a \; (ba)^* \; b. Já temos o bloco inicial \,a com q_0 \xrightarrow{a} q_1, o bloco da estrela com início q_6 e fim q_7, e precisamos do \,b final.
  • Crio o bloco do \,b final com q_8 \xrightarrow{b} q_9.
  • Faço a concatenação ligando o final do primeiro a ao início da estrela:
q_1 \xrightarrow{\epsilon} q_6.
  • Faço a concatenação ligando o final da estrela ao início do \,b final:
q_7 \xrightarrow{\epsilon} q_8.
Portanto o autômato começa em q_0 e aceita em q_9.

Passo 7

Resumo final das transições (lista completa, passo a passo — cada linha é uma transição do AFN):
q_0 \xrightarrow{a} q_1
q_1 \xrightarrow{\epsilon} q_6
q_6 \xrightarrow{\epsilon} q_2
q_6 \xrightarrow{\epsilon} q_7
q_2 \xrightarrow{b} q_3
q_3 \xrightarrow{\epsilon} q_4
q_4 \xrightarrow{a} q_5
q_5 \xrightarrow{\epsilon} q_2
q_5 \xrightarrow{\epsilon} q_7
q_7 \xrightarrow{\epsilon} q_8
q_8 \xrightarrow{b} q_9
Explicação curta: esse conjunto de transições implementa exatamente a sequência a, seguida de zero ou mais repetições de b a, seguida de b. O estado inicial é q_0 e o único estado de aceitação é q_9.

Passo 8

Como checar mentalmente se funciona (pequeno exemplo): a palavra \,ab deve ser aceita (escolhe-se zero repetições de (ba)): caminho
q_0 \xrightarrow{a} q_1 \xrightarrow{\epsilon} q_6 \xrightarrow{\epsilon} q_7 \xrightarrow{\epsilon} q_8 \xrightarrow{b} q_9.
A palavra \,abba b (por exemplo a\, b a\, b) também é aceita via uma repetição de ba.

Resposta

M=(Q,\Sigma,\delta,q_0,F)
Q=\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9\}
\Sigma=\{a,b\}
\begin{aligned} \delta(q_0,a)&=\{q_1\}\\\ \delta(q_1,\epsilon)&=\{q_6\}\\\ \delta(q_6,\epsilon)&=\{q_2,q_7\}\\\ \delta(q_2,b)&=\{q_3\}\\\ \delta(q_3,\epsilon)&=\{q_4\}\\\ \delta(q_4,a)&=\{q_5\}\\\ \delta(q_5,\epsilon)&=\{q_2,q_7\}\\\ \delta(q_7,\epsilon)&=\{q_8\}\\\ \delta(q_8,b)&=\{q_9\} \end{aligned}
q_0\\ \text{é o estado inicial}é
F=\{q_9\}

Exercícios relacionados