Converta as seguintes expressões regulares em AFNs.
\mathrm{a}^{+} \bigcup(\mathrm{ab})^{+}

Passo 1

O enunciado pede: converter a expressão regular \mathrm{a}^{+} \cup (\mathrm{ab})^{+} em um AFN (autômato finito não-determinístico).\n
Informações dadas e aquilo que precisamos entregar:
  • A expressão regular é \mathrm{a}^{+} \cup (\mathrm{ab})^{+}.\n
  • Devemos construir um AFN que reconheça exatamente a linguagem descrita por essa expressão.\n
  • Vou assumir o alfabeto \Sigma=\{a,b\} (porque aparecem os símbolos a e b na expressão).\n

Passo 2

Entendendo as partes da expressão (sem resolver ainda, só identificar os blocos):
  • A expressão é uma união (o símbolo \cup) de duas partes: \mathrm{a}^{+} e (\mathrm{ab})^{+}.
  • Cada parte usa o operador + (um ou mais ocorrências) aplicado a um bloco: bloco a no primeiro caso e bloco ab no segundo.\n
Observação didática rápida sobre +: R^{+} significa "uma ou mais repetições de R". Uma maneira prática de ver R^{+} é como R R^{*} (ou seja, pelo menos uma ocorrência seguida de zero ou mais ocorrências). Em termos de AFN isso costuma ser implementado como o automato de R com uma transição \varepsilon de seu(s) estado(s) de aceitação de volta ao(s)(s) estado(s) inicial(is) de R — assim garantimos repetição mas exigimos pelo menos uma ocorrência.\n

Passo 3

Construindo NFAs básicos (pequenas peças) que usaremos na montagem final.
  1. AFN para o símbolo a.
  • Estados: q_a^{start}, q_a^{end}.
  • Transição: \delta(q_a^{start},a)=\{q_a^{end}\}.
  • Esse AFN aceita exatamente a palavra a.
  1. AFN para a concatenação ab.
  • Podemos concatenar dois blocos: um AFN para a seguido por um AFN para b.
  • Estados (nomes sugestivos): q_{ab}^{1} --(a)–> q_{ab}^{2} --(b)–> q_{ab}^{3}.
  • Transições: \delta(q_{ab}^{1},a)=\{q_{ab}^{2}\} e \delta(q_{ab}^{2},b)=\{q_{ab}^{3}\}.
  • Esse AFN aceita exatamente a palavra ab.\n

Passo 4

Construindo \mathrm{a}^{+} usando Thompson (passo a passo e explicando a ideia).
  • Ideia: para R^{+} com R=a, nós pegamos o AFN de a (do Passo 3) e permitimos repetições adicionando uma transição \varepsilon do estado final de volta ao estado inicial. Para organizar a união depois, é conveniente que cada ramo tenha sua própria “saída” que vai para um estado de aceitação comum.
Vou designar estados concretos para a parte a^{+}:
  • q_1 (início do ramo a^{+}),
  • q_2 (após consumir um a; estado que permite repetir).
    Transições:
  • \delta(q_1,a)=\{q_2\}.
  • \delta(q_2,\varepsilon)=\{q_1\} (loop que permite repetir a quantas vezes quiser).
  • Também precisaremos que, ao terminar, esse ramo possa alcançar o estado final global (que construiremos na união). Então reservamos uma transição \varepsilon de q_2 para o estado final comum (essa ligação será feita mais adiante no autômato final). Essa estrutura garante pelo menos uma ocorrência de a (porque precisa passar por q_1 q_2 uma vez) e permite repetições.\n

Passo 5

Construindo (ab)^{+} com a mesma ideia (explicando tudo devagar).
  • Para R=(ab), já temos o esquema do Passo 3 para ab: estados q_{3} --(a)–> q_{4} --(b)–> q_{5}.
  • Para (ab)^{+} adicionamos uma transição \varepsilon de q_{5} (estado após consumir um ab) de volta ao início q_{3}, permitindo repetições.
  • Também faremos uma transição \varepsilon de q_{5} para o estado final global (tal como fizemos no ramo a^{+}), para que possamos aceitar após um ou mais blocos ab.
Esquematicamente:
  • \delta(q_{3},a)=\{q_{4}\}.
  • \delta(q_{4},b)=\{q_{5}\}.
  • \delta(q_{5},\varepsilon)=\{q_{3}\} (loop para repetir).
  • E \delta(q_{5},\varepsilon) também terá a opção de ir para o estado final global (essa transição será listada explicitamente no AFN final).\n

Passo 6

Fazendo a união \mathrm{a}^{+} \cup (\mathrm{ab})^{+}:
  • Para representar a união em Thompson, criamos um novo estado inicial global q_0 que faz transições \varepsilon para os inícios dos dois ramos a^{+} e (ab)^{+}. Assim, o autômato pode “escolher” qual ramo explorar sem ler símbolo (não-determinismo via \varepsilon).
  • Também criamos um único estado final global q_f. Cada ramo, ao atingir seu estado de aceitação local (no nosso desenho: q_2 para a^{+} e q_5 para (ab)^{+}), tem uma transição \varepsilon para q_f. Isso centraliza a aceitação.
  • Mantemos as transições de repetição internas ( \varepsilon de q_2 para q_1 e de q_5 para q_3) para garantir o operador + (uma ou mais repetições).
Resumo da topologia (já com nomes concretos que vou usar para listar formalmente):
  • Estado inicial global: q_0.
  • Ramo a^{+}: q_1 --(a)–> q_2, com \delta(q_2,\varepsilon)=\{q_1,q_f\} (volta para repetir e opção de aceitar indo para q_f).
  • Ramo (ab)^{+}: q_3 --(a)–> q_4 --(b)–> q_5, com \delta(q_5,\varepsilon)=\{q_3,q_f\}.
  • Ligações da união: \delta(q_0,\varepsilon)=\{q_1,q_3\}.
  • Estado final global: q_f, que é o único estado de aceitação.\n

Passo 7

Vou escrever agora o AFN final de forma formal e explícita (mostrando o conjunto de estados, o alfabeto, a função de transição \delta, o estado inicial e o(s) estado(s) de aceitação). Também explico o significado de cada componente para você decorar para a prova.
Definição formal de um AFN: (Q,\Sigma,\delta,q_0,F), onde
  • Q é o conjunto de estados,
  • \Sigma é o alfabeto (aqui \{a,b\}),
  • \delta: Q\times(\Sigma\cup\{\varepsilon\}) \to \mathcal{P}(Q) é a função de transição que pode devolver conjuntos de estados (porque é não-determinística e permite \varepsilon-transições),
  • q_0 é o estado inicial,
  • F\subseteq Q é o conjunto de estados de aceitação.
Agora o AFN concreto (vou listar \delta como um conjunto de pares ordenados com as imagens):
  • Conjunto de estados:
Q=\{q_0,q_1,q_2,q_3,q_4,q_5,q_f\}.
  • Alfabeto:
\Sigma=\{a,b\}.
  • Função de transição \delta (lista completa das transições não-vazias):
\begin{aligned} &\delta(q_0,\varepsilon)=\{q_1,q_3\},\\\ &\delta(q_1,a)=\{q_2\},\\\ &\delta(q_2,\varepsilon)=\{q_1,q_f\},\\\ &\delta(q_3,a)=\{q_4\},\\\ &\delta(q_4,b)=\{q_5\},\\\ &\delta(q_5,\varepsilon)=\{q_3,q_f\}. \end{aligned}
  • Estado inicial:
q_0.
  • Conjunto de estados de aceitação:
F=\{q_f\}.
Breve verificação intuitiva (faça isso na prova mentalmente): do estado inicial q_0 o autômato pode ir por \varepsilon para q_1 e então consumir pelo menos um a (porque precisa fazer q_1\overset{a}{\to}q_2); ao chegar em q_2 pode escolher \varepsilon voltar a q_1 para mais as ou \varepsilon ir para q_f e aceitar. Do outro lado, q_0 pode ir para q_3 e consumir um ab (fazendo q_3\overset{a}{\to}q_4 e q_4\overset{b}{\to}q_5); em q_5 pode voltar a q_3 por \varepsilon para repetir mais abs ou ir para q_f e aceitar. Isso corresponde exatamente a aceitar a^{+} ou (ab)^{+}.\n

Resposta

(Q,\Sigma,\delta,q_0,F)=\Big(\{q_0,q_1,q_2,q_3,q_4,q_5,q_f\},\{a,b\},\delta,q_0,\{q_f\}\Big)
\begin{aligned} \delta(q_0,\varepsilon)&=\{q_1,q_3\},\\\ \delta(q_1,a)&=\{q_2\},\\\ \delta(q_2,\varepsilon)&=\{q_1,q_f\},\\\ \delta(q_3,a)&=\{q_4\},\\\ \delta(q_4,b)&=\{q_5\},\\\ \delta(q_5,\varepsilon)&=\{q_3,q_f\}. \end{aligned}

Exercícios relacionados