Converta as seguintes expressões regulares em AFNs.
Passo 1
O que o enunciado pede: converter a expressão regular
em um AFN (autômato finito não determinístico).
Informações dadas: a única expressão é . Não há figura nem restrição adicional. O objetivo é entregar um AFN que reconheça exatamente a linguagem descrita por
.
Informações dadas: a única expressão é
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
(transições vazias). Regras básicas da construção de Thompson (explicadas de forma simples):
- Para um símbolo único, por exemplo
, o AFN é dois estados com uma transição por entre eles. - Para concatenação
, você liga o estado final de ao estado inicial de por uma transição . - Para união
, cria-se um novo início com para os inícios de e , e os finais de e apontam por para um novo estado final. - Para estrela de Kleene
, cria-se um novo início e um novo fim; do novo início há para o início de e para o novo fim (permitindo zero repetições); do fim de há para o início de (loop) e para o novo fim.
Exemplo simples: paravamos aplicar a regra da concatenação para formar seguido de , e então aplicar a regra da estrela.
Passo 3
Construção dos blocos atômicos:
- AFN para
: criaremos dois estados e com a transição
Esse será o bloco correspondente ao primeiro
da expressão
.
- AFN para
(usado dentro de 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
(concatenação de
e
):
- Crio estados
e com
- Crio estados
e com
- Para concatenar
seguido de faço uma transição do final do bloco para o início do bloco :
Assim o bloco
vai de
(início) a
(fim).
Passo 5
Aplicar a estrela de Kleene em
para obter
(usando a regra da estrela de Thompson):
- Crio um novo estado inicial do bloco da estrela
e um novo estado final do bloco da estrela . - Adiciono as transições
clássicas:
Explicação didática: isso permite escolher zero repetições (via
) ou entrar no bloco
(via
); ao terminar um
em
podemos voltar a começar outro
(loop
) ou sair para o fim da estrela (via
).
Passo 6
Concatenar tudo: temos a expressão
. Já temos o bloco inicial
com
, o bloco da estrela com início
e fim
, e precisamos do
final.
- Crio o bloco do
final com . - Faço a concatenação ligando o final do primeiro
ao início da estrela:
- Faço a concatenação ligando o final da estrela ao início do
final:
Portanto o autômato começa em
e aceita em
.
Passo 7
Resumo final das transições (lista completa, passo a passo — cada linha é uma transição do AFN):
Explicação curta: esse conjunto de transições implementa exatamente a sequência
, seguida de zero ou mais repetições de
, seguida de
. O estado inicial é
e o único estado de aceitação é
.
Passo 8
Como checar mentalmente se funciona (pequeno exemplo): a palavra
deve ser aceita (escolhe-se zero repetições de
): caminho
A palavra
(por exemplo
) também é aceita via uma repetição de
.