Converta as seguintes expressões regulares em AFNs.
\left(a \bigcup b^{+}\right) a^{+} b^{+}

Passo 1

O enunciado pede: converter a expressão regular \left(a \bigcup b^{+}\right) a^{+} b^{+} em um autômato finito não determinístico (AFN).\n
Informações dadas:
  • A expressão regular é \left(a \bigcup b^{+}\right) a^{+} b^{+}.\n
  • O alfabeto implícito é \{a,b\}.\n
  • Queremos um AFN que reconheça exatamente as cadeias descritas por essa expressão.\n

Passo 2

Vou usar uma construção passo a passo (padrão) que monta AFNs para operações básicas e depois combina esses AFNs por união, concatenação e o operador + (um ou mais). Antes de aplicar, explico as peças básicas:
  • Um AFN para um símbolo simples, por exemplo para \,a\,, é dois estados com uma transição q_{i}\xrightarrow{a}q_{j}. Aqui q_{i} é o início do fragmento e q_{j} é o fim do fragmento.\n
  • Para concatenação R\cdot S: conectamos o estado final do AFN de R por uma transição \varepsilon ao estado inicial do AFN de S.\n
  • Para união R\cup S: criamos um novo estado inicial com \varepsilon para os inícios de R e S, e um novo estado final com \varepsilon vindo dos finais de R e S.\n
  • Para o operador de Kleene R^{*}: padrão com novo início s e novo fim f, \varepsilon de s para o início de R, \varepsilon do fim de R de volta ao início de R (loop), e também \varepsilon de s para f e do fim de R para f (permite zero ocorrências).\n
  • Para R^{+} (um ou mais): uma forma prática é construir R\cdot R^{*} — ou construir similar ao R^{*} mas sem a \varepsilon direta de s para f, garantindo ao menos uma ocorrência.\n
Vou aplicar essas regras concretamente ao seu caso, detalhando cada construção e numerando os estados para termos um AFN final claro.

Passo 3

Construção dos blocos elementares: AFNs para \,a\, e para \,b\,.
  • AFN para \,a\,: dois estados q_{1} e q_{2} com
q_{1}\xrightarrow{a}q_{2}.
  • AFN para \,b\,: dois estados q_{5} e q_{6} (vou usar esses índices mais adiante) com
q_{5}\xrightarrow{b}q_{6}.
Esses são blocos básicos; agora vamos usar esses blocos para formar a^{+} e b^{+}.

Passo 4

Construção de b^{+} (primeira ocorrência, que aparece dentro da união \,a\cup b^{+}\,).

Usamos a construção direta para R^{+}: a sequência mínima é uma cópia de b seguida por um laço que permite repetições. Vou criar três estados para esse bloco:
q_{5}\xrightarrow{b}q_{6},\quad q_{6}\xrightarrow{\varepsilon}q_{5},\quad q_{6}\xrightarrow{\varepsilon}q_{7}.
Aqui q_{5} é o início do bloco b^{+}, q_{7} é o fim do bloco. A transição q_{6}\xrightarrow{\varepsilon}q_{5} permite repetir mais um b, e q_{6}\xrightarrow{\varepsilon}q_{7} permite aceitar após pelo menos um b.

Passo 5

Construção de a^{+} (o bloco do meio da concatenação).

Analogamente ao b^{+}, para a^{+} uso três estados:
q_{9}\xrightarrow{a}q_{10},\quad q_{10}\xrightarrow{\varepsilon}q_{9},\quad q_{10}\xrightarrow{\varepsilon}q_{11}.
Aqui q_{9} é o início de a^{+} e q_{11} é o fim de a^{+}. Garante pelo menos um a e repetições possíveis.

Passo 6

Construção da união \,a\cup b^{+}\,.

Para a união criamos um novo início q_{0} e um novo fim intermediário q_{4}. O bloco da letra a (do Passo 3) usou q_{1}\xrightarrow{a}q_{2}. O bloco b^{+} já tem início em q_{5} e fim em q_{7}. Agora a união tem essas transições principais:
q_{0}\xrightarrow{\varepsilon}q_{1},\quad q_{0}\xrightarrow{\varepsilon}q_{5},
q_{2}\xrightarrow{\varepsilon}q_{4},\quad q_{7}\xrightarrow{\varepsilon}q_{4}.
Explicação: de q_{0} posso escolher seguir o ramo que gera um único a (via q_{1}\to q_{2}) ou seguir o ramo que gera b^{+} (via q_{5}\dots q_{7}). Em ambos os casos levo \varepsilon para o estado intermediário q_{4}, que vai ser conectado à próxima parte da concatenação.

Passo 7

Concatenação total: \left(a \cup b^{+}\right) \, a^{+} \, b^{+}.

Agora concatenamos o bloco da união (termina em q_{4}) com o bloco a^{+} (inicia em q_{9}) usando uma transição \varepsilon:
q_{4}\xrightarrow{\varepsilon}q_{9}.
Depois do bloco a^{+} (que termina em q_{11}) concatenamos com um novo bloco b^{+} (a ocorrência final de b^{+} no regex). Como esse b^{+} é uma nova instância, crio um novo conjunto de estados q_{12},q_{13},q_{14} com o padrão:
q_{12}\xrightarrow{b}q_{13},\quad q_{13}\xrightarrow{\varepsilon}q_{12},\quad q_{13}\xrightarrow{\varepsilon}q_{14}.
E conecto a^{+} ao b^{+} final por
q_{11}\xrightarrow{\varepsilon}q_{12}.
O estado q_{14} será o estado final do AFN inteiro.

Passo 8

Resumo formal do AFN construído (lista completa de estados e transições). Este é o AFN resultante que reconhece exatamente \left(a \cup b^{+}\right) a^{+} b^{+}:
  • Estado inicial: q_{0}.\n
  • Estado final: q_{14}.\n
  • Conjunto de símbolos (alfabeto): \{a,b\}.\n
  • Conjunto de estados (lista explícita): \{q_{0},q_{1},q_{2},q_{4},q_{5},q_{6},q_{7},q_{9},q_{10},q_{11},q_{12},q_{13},q_{14}\}.\n
  • Transições (lista completa):\n
\begin{aligned} & q_{0}\xrightarrow{\varepsilon}q_{1},\quad q_{0}\xrightarrow{\varepsilon}q_{5},\\\ & q_{1}\xrightarrow{a}q_{2},\\\ & q_{5}\xrightarrow{b}q_{6},\quad q_{6}\xrightarrow{\varepsilon}q_{5},\quad q_{6}\xrightarrow{\varepsilon}q_{7},\\\ & q_{2}\xrightarrow{\varepsilon}q_{4},\quad q_{7}\xrightarrow{\varepsilon}q_{4},\\\ & q_{4}\xrightarrow{\varepsilon}q_{9},\\\ & q_{9}\xrightarrow{a}q_{10},\quad q_{10}\xrightarrow{\varepsilon}q_{9},\quad q_{10}\xrightarrow{\varepsilon}q_{11},\\\ & q_{11}\xrightarrow{\varepsilon}q_{12},\\\ & q_{12}\xrightarrow{b}q_{13},\quad q_{13}\xrightarrow{\varepsilon}q_{12},\quad q_{13}\xrightarrow{\varepsilon}q_{14}. \end{aligned}
Essas transições formam um AFN com \varepsilon-transições que reconhece todas as cadeias da expressão original: primeiro escolhe entre produzir um a isolado ou um ou mais b (o primeiro parêntese), depois exige um ou mais a ( a^{+}), e por fim exige um ou mais b ( b^{+}).

Resposta

Estados: \{q_{0},q_{1},q_{2},q_{4},q_{5},q_{6},q_{7},q_{9},q_{10},q_{11},q_{12},q_{13},q_{14}\}\n
Alfabeto: \{a,b\}\n
Transições:\n
\displaystyle q_{0}\xrightarrow{\varepsilon}q_{1}\n
\displaystyle q_{0}\xrightarrow{\varepsilon}q_{5}\n
\displaystyle q_{1}\xrightarrow{a}q_{2}\n
\displaystyle q_{5}\xrightarrow{b}q_{6}\n
\displaystyle q_{6}\xrightarrow{\varepsilon}q_{5}\n
\displaystyle q_{6}\xrightarrow{\varepsilon}q_{7}\n
\displaystyle q_{2}\xrightarrow{\varepsilon}q_{4}\n
\displaystyle q_{7}\xrightarrow{\varepsilon}q_{4}\n
\displaystyle q_{4}\xrightarrow{\varepsilon}q_{9}\n
\displaystyle q_{9}\xrightarrow{a}q_{10}\n
\displaystyle q_{10}\xrightarrow{\varepsilon}q_{9}\n
\displaystyle q_{10}\xrightarrow{\varepsilon}q_{11}\n
\displaystyle q_{11}\xrightarrow{\varepsilon}q_{12}\n
\displaystyle q_{12}\xrightarrow{b}q_{13}\n
\displaystyle q_{13}\xrightarrow{\varepsilon}q_{12}\n
\displaystyle q_{13}\xrightarrow{\varepsilon}q_{14}\n
Estado inicial: q_{0}\n
Estado final: q_{14}

Exercícios relacionados