Converta as seguintes expressões regulares em AFNs.
\mathrm{a}(\mathrm{abb}) * \bigcup \mathrm{~b}

Passo 1

O que o enunciado pede: converter a expressão regular dada em um AFN (autômato finito não-determinístico).
Informação fornecida (interpretação que vou usar): a expressão é
a(abb)^* \;\cup\; b.
Observação sobre a notação: no enunciado original havia \(\mathrm{~b}\) — interpreto isso como apenas o símbolo \(\mathrm{b}\) (provavelmente foi usado ~ só para espaçamento). Assim trabalharei com a união entre a expressão a(abb)^* e o símbolo b.

Passo 2

Breve aula prática: método que usarei — construção de Thompson (regra-padrão para converter expressões regulares em AFN). Regras básicas e o que cada operador faz:
  1. Símbolo simples \mathrm{x} (por exemplo a ou b): cria-se um pequeno AFN com dois estados e uma transição rotulada por \mathrm{x}:
q_{start} \xrightarrow{\mathrm{x}} q_{accept}.
  1. Concatenação R_1 R_2: conecta-se o estado de aceitação de R_1 ao estado inicial de R_2 com uma transição \varepsilon (pode-se também “colar” os estados, mas usar \varepsilon é padrão).
  2. União R_1 \cup R_2: cria-se um novo estado inicial com \varepsilon-transições para os inícios de R_1 e R_2, e um novo estado de aceitação com \varepsilon-transições das aceitações de R_1 e R_2 para ele.
  3. Fecho de Kleene R^*: cria-se um novo início e um novo fim; do novo início vai \varepsilon para o antigo início e para o novo fim; da antiga aceitação vai \varepsilon para o antigo início (para repetir) e para o novo fim; isso permite repetir zero ou mais vezes.
Vou aplicar essas regras passo a passo à expressão a(abb)^* \cup b. Em cada passo explico o porquê e mostro claramente as transições.

Passo 3

Construção do AFN para o símbolo \;a\;.
Crio dois estados:
q_1 \xrightarrow{a} q_2.
Aqui q_1 é o início do trecho e q_2 é o estado de aceitação desse trecho.

Passo 4

Construção do AFN para a palavra \;abb\; (concatenação de três símbolos).
Faço em três pedaços e concateno:
q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6 \xrightarrow{b} q_7.
Aqui q_4 é o início do bloco \;abb\; e q_7 é sua aceitação.

Passo 5

Aplicar o fecho de Kleene ao bloco \;(abb)^*\; usando a construção de Thompson.
Para R=abb com início q_4 e aceitação q_7, criamos um novo início q_3 e um novo aceitação q_8 e as \varepsilon-transições padrão:
  • \;q_3 \xrightarrow{\varepsilon} q_4\; (entrar no bloco),
  • \;q_3 \xrightarrow{\varepsilon} q_8\; (permitir zero cópias),
  • \;q_7 \xrightarrow{\varepsilon} q_4\; (repetir o bloco),
  • \;q_7 \xrightarrow{\varepsilon} q_8\; (sair do fecho para o estado final).
Assim o trecho (abb)^* fica com os estados e transições:
q_3 \xrightarrow{\varepsilon} q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6 \xrightarrow{b} q_7 \xrightarrow{\varepsilon} q_8,
e também as \varepsilon-transições q_3 \xrightarrow{\varepsilon} q_8 e q_7 \xrightarrow{\varepsilon} q_4.
Explicação rápida do porquê: essas \varepsilon-transições permitem executar zero cópias (ir direto q_3\to q_8) ou executar uma cópia e voltar para repetir (via q_7\to q_4).

Passo 6

Concatenar o símbolo a com o fecho (abb)^* para obter a(abb)^*.
Pelo passo 3 temos q_1 \xrightarrow{a} q_2. Pelo passo 5 o fecho tem início q_3. Para concatenar, faço uma \varepsilon-transição do estado de aceitação do primeiro pedaço q_2 para o início do segundo q_3:
q_2 \xrightarrow{\varepsilon} q_3.
Assim o trecho a(abb)^* tem início q_1 e aceitação q_8 (o q_8 criado no fecho é o aceitação final desse trecho).

Passo 7

Construção do AFN para o símbolo à direita da união: \;b\;.
Crio dois estados:
q_9 \xrightarrow{b} q_{10}.
Aqui q_9 é o início do pedaço que reconhece só b, e q_{10} é sua aceitação.

Passo 8

Aplicar a operação de união entre os dois pedaços: a(abb)^* (início q_1, aceitação q_8) e b (início q_9, aceitação q_{10}).
Pelo esquema de Thompson, crio um novo estado inicial global q_0 e um novo estado de aceitação global q_{11}. Coloco \varepsilon-transições:
  • Do novo início para cada início dos sub-autômatos: q_0 \xrightarrow{\varepsilon} q_1,\qquad q_0 \xrightarrow{\varepsilon} q_9.
  • Das aceitações de cada sub-autômato para o novo estado de aceitação: q_8 \xrightarrow{\varepsilon} q_{11},\qquad q_{10} \xrightarrow{\varepsilon} q_{11}.
Agora temos um AFN completo cujo início é q_0 e aceitação é q_{11}.

Passo 9

Listagem final do AFN obtido — vou apresentar como a 5-tupla (Q,\Sigma,\delta,q_0,F) e também como tabela de transições para ficar prático na prova.
Conjunto de estados:
Q=\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9,q_{10},q_{11}\}.
Alfabeto:
\Sigma=\{a,b\}.
Estado inicial:
q_0.
Conjunto de estados de aceitação:
F=\{q_{11}\}.
Função de transição \delta (mostrada como lista de transições; \varepsilon indica transição vazia):
\begin{array}{l} \delta(q_0,\varepsilon)=\{q_1,q_9\},\\[4pt] \delta(q_1,a)=\{q_2\},\\[4pt] \delta(q_2,\varepsilon)=\{q_3\},\\[4pt] \delta(q_3,\varepsilon)=\{q_4,q_8\},\\[4pt] \delta(q_4,a)=\{q_5\},\\[4pt] \delta(q_5,b)=\{q_6\},\\[4pt] \delta(q_6,b)=\{q_7\},\\[4pt] \delta(q_7,\varepsilon)=\{q_4,q_8\},\\[4pt] \delta(q_8,\varepsilon)=\{q_{11}\},\\[4pt] \delta(q_9,b)=\{q_{10}\},\\[4pt] \delta(q_{10},\varepsilon)=\{q_{11}\}. \end{array}
Observação sobre a interpretação prática: desse AFN, quaisquer caminhos que levam de q_0 a q_{11} reconhecem cadeias da linguagem. Por exemplo:
  • Para reconhecer a palavra b: q_0 \xrightarrow{\varepsilon} q_9 \xrightarrow{b} q_{10} \xrightarrow{\varepsilon} q_{11}.
  • Para reconhecer a: q_0 \xrightarrow{\varepsilon} q_1 \xrightarrow{a} q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{\varepsilon} q_8 \xrightarrow{\varepsilon} q_{11} (note que (abb)^* pode gerar zero cópias, então a pertence à linguagem).
  • Para reconhecer aabb: q_0\to q_1 \xrightarrow{a} q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{\varepsilon} q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6 \xrightarrow{b} q_7 \xrightarrow{\varepsilon} q_8 \xrightarrow{\varepsilon} q_{11}.]

Resposta

(Q,\Sigma,\delta,q_0,F) com
Q=\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9,q_{10},q_{11}\},
\Sigma=\{a,b\},
F=\{q_{11}\},
e \delta dada por
\begin{array}{l} \delta(q_0,\varepsilon)=\{q_1,q_9\},\\[4pt] \delta(q_1,a)=\{q_2\},\\[4pt] \delta(q_2,\varepsilon)=\{q_3\},\\[4pt] \delta(q_3,\varepsilon)=\{q_4,q_8\},\\[4pt] \delta(q_4,a)=\{q_5\},\\[4pt] \delta(q_5,b)=\{q_6\},\\[4pt] \delta(q_6,b)=\{q_7\},\\[4pt] \delta(q_7,\varepsilon)=\{q_4,q_8\},\\[4pt] \delta(q_8,\varepsilon)=\{q_{11}\},\\[4pt] \delta(q_9,b)=\{q_{10}\},\\[4pt] \delta(q_{10},\varepsilon)=\{q_{11}\}. \end{array}]

Exercícios relacionados