Converta as seguintes expressões regulares em AFNs.
Passo 1
O enunciado pede: converter a expressão regular
em um autômato finito não determinístico (AFN).\n
Informações dadas:
Informações dadas:
- A expressão regular é
.\n - O alfabeto implícito é
.\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
, é dois estados com uma transição . Aqui é o início do fragmento e é o fim do fragmento.\n - Para concatenação
: conectamos o estado final do AFN de por uma transição ao estado inicial do AFN de .\n - Para união
: criamos um novo estado inicial com para os inícios de e , e um novo estado final com vindo dos finais de e .\n - Para o operador de Kleene
: padrão com novo início e novo fim , de para o início de , do fim de de volta ao início de (loop), e também de para e do fim de para (permite zero ocorrências).\n - Para
(um ou mais): uma forma prática é construir — ou construir similar ao mas sem a direta de para , 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
e para
.
- AFN para
: dois estados e com
- AFN para
: dois estados e (vou usar esses índices mais adiante) com
Esses são blocos básicos; agora vamos usar esses blocos para formar
e
.
Passo 4
Construção de
(primeira ocorrência, que aparece dentro da união
).
Usamos a construção direta para
Aqui
é o início do bloco
,
é o fim do bloco. A transição
permite repetir mais um
, e
permite aceitar após pelo menos um
.
Passo 5
Construção de
(o bloco do meio da concatenação).
Analogamente ao
Aqui
é o início de
e
é o fim de
. Garante pelo menos um
e repetições possíveis.
Passo 6
Construção da união
.
Para a união criamos um novo início
Explicação: de
posso escolher seguir o ramo que gera um único
(via
) ou seguir o ramo que gera
(via
). Em ambos os casos levo
para o estado intermediário
, que vai ser conectado à próxima parte da concatenação.
Passo 7
Concatenação total:
.
Agora concatenamos o bloco da união (termina em
Depois do bloco
(que termina em
) concatenamos com um novo bloco
(a ocorrência final de
no regex). Como esse
é uma nova instância, crio um novo conjunto de estados
com o padrão:
E conecto
ao
final por
O estado
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
:
- Estado inicial:
.\n - Estado final:
.\n - Conjunto de símbolos (alfabeto):
.\n - Conjunto de estados (lista explícita):
.\n - Transições (lista completa):\n
Essas transições formam um AFN com
-transições que reconhece todas as cadeias da expressão original: primeiro escolhe entre produzir um
isolado ou um ou mais
(o primeiro parêntese), depois exige um ou mais
(
), e por fim exige um ou mais
(
).
Resposta
Estados:
\n
Alfabeto: \n
Transições:\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
Estado inicial: \n
Estado final:
Alfabeto:
Transições:\n
Estado inicial:
Estado final: