Converta as seguintes expressões regulares em AFNs.
(\varepsilon \cup a) b

Passo 1

O enunciado pede para converter a expressão regular (\varepsilon \cup a)\,b em um AFN (autômato finito não-determinístico).\n
Informações dadas:
  • A expressão regular é (\varepsilon \cup a)\,b.
  • Os símbolos que aparecem são a, b e o símbolo vazio \varepsilon.
  • O que se espera: um AFN que reconheça exatamente a mesma linguagem dessa expressão.

Passo 2

Escolha do método: vou usar duas etapas didáticas.
  1. Primeiro mostro a construção sistemática (tipo Thompson) passo a passo — isso te ensina um método geral que serve para qualquer expressão regular.
  2. Depois apresento uma versão simplificada e pequena do AFN (sem \varepsilon-transições) — essa é a que você provavelmente desenha rápido na prova porque é mais enxuta.
Explico o porquê: Thompson é um procedimento mecânico e seguro; a simplificação mostra como otimizar para a hora da prova.

Passo 3

Átomos da expressão e NFAs básicos:
  • Para o símbolo \varepsilon (cadeia vazia) um AFN simples tem um estado inicial e um estado final com uma transição por \varepsilon.
    • Representação: estados \{q_0,q_1\}, início q_0, final q_1, transição \delta(q_0,\varepsilon)=\{q_1\}.
  • Para o símbolo a um AFN simples tem uma transição rotulada a.
    • Representação: estados \{q_2,q_3\}, início q_2, final q_3, transição \delta(q_2,a)=\{q_3\}.
  • Para o símbolo b um AFN simples tem uma transição rotulada b.
    • Representação: estados \{q_6,q_7\}, início q_6, final q_7, transição \delta(q_6,b)=\{q_7\}.

Passo 4

Construção da união \varepsilon \cup a (Thompson):
  • Criamos um novo estado inicial q_4 e um novo estado final q_5.
  • Ponho \varepsilon-transições de q_4 para os inícios de \varepsilon e de a, ou seja para q_0 e q_2.
  • Ponho \varepsilon-transições dos finais de \varepsilon e de a para q_5, ou seja de q_1 e de q_3 para q_5.
    Assim eu obtenho um AFN para (\varepsilon \cup a) com início q_4 e final q_5.

Passo 5

Concatenação com b: (\varepsilon \cup a)\,b
  • Para concatenar, coloco uma \varepsilon-transição do estado final da união q_5 para o início do AFN de b, que é q_6.
  • O estado inicial do AFN final será q_4 e o estado final será q_7.
  • Lista de transições (forma de conjunto de triplas) resultantes do método Thompson: \begin{aligned} &\delta(q_0,\varepsilon)=\{q_1\},\\\ &\delta(q_2,a)=\{q_3\},\\\ &\delta(q_4,\varepsilon)=\{q_0,q_2\},\\\ &\delta(q_1,\varepsilon)=\{q_5\},\\\ &\delta(q_3,\varepsilon)=\{q_5\},\\\ &\delta(q_5,\varepsilon)=\{q_6\},\\\ &\delta(q_6,b)=\{q_7\}. \end{aligned}
  • Conjunto de estados final: \{q_7\}. Início: q_4.

Passo 6

Interpretação da linguagem e execução em exemplo (para fixar):
  • A expressão (\varepsilon \cup a)\,b gera exatamente as cadeias b (quando escolhemos \varepsilon e depois concatenamos b) e ab (quando escolhemos a e depois concatenamos b). Logo a linguagem é \{\,b,\;ab\,\}.
  • Simulação rápida no AFN de Thompson:
    • Para a palavra b: do q_4 faço \varepsilon até q_0, de q_0 via \varepsilon para q_1, via \varepsilon para q_5, via \varepsilon para q_6 e então com b para q_7 (aceita).
    • Para a palavra ab: do q_4 faço \varepsilon para q_2, com a vou para q_3, \varepsilon para q_5, \varepsilon para q_6, com b para q_7 (aceita).

Passo 7

AFN simplificado (mais prático para a prova)
  • Como a linguagem é apenas \{b,ab\}, dá para desenhar um AFN muito direto, sem \varepsilon-transições:
    • Estados: \{p_0,p_1,p_2\}.
    • Estado inicial: p_0.
    • Estado final: p_2.
    • Transições: \delta(p_0,b)=\{p_2\},
\delta(p_0,a)=\{p_1\},
\delta(p_1,b)=\{p_2\}.
  • Interpretação: de p_0 posso consumir um b e ir direto para o estado final (reconhece b), ou consumir um a e depois um b para chegar ao final (reconhece ab). Esse AFN é pequeno, fácil de desenhar e o que você precisa levar para a prova.

Resposta

Estados: \{p_0,p_1,p_2\}
Alfabeto: \{a,b\}
Estado inicial: \;p_0
Estado final: \{p_2\}
Transições:
\delta(p_0,b)=\{p_2\}
\delta(p_0,a)=\{p_1\}
\delta(p_1,b)=\{p_2\}

Exercícios relacionados