Converta as seguintes expressões regulares em AFNs.
Passo 1
O enunciado pede: converter a expressão regular
em um AFN (autômato finito não-determinístico).\n
Informações dadas e aquilo que precisamos entregar:
Informações dadas e aquilo que precisamos entregar:
- A expressão regular é
.\n - Devemos construir um AFN que reconheça exatamente a linguagem descrita por essa expressão.\n
- Vou assumir o alfabeto
(porque aparecem os símbolos e na expressão).\n
Passo 2
Entendendo as partes da expressão (sem resolver ainda, só identificar os blocos):
- A expressão é uma união (o símbolo
) de duas partes: e . - Cada parte usa o operador
(um ou mais ocorrências) aplicado a um bloco: bloco no primeiro caso e bloco no segundo.\n
Observação didática rápida sobre
:
significa "uma ou mais repetições de
". Uma maneira prática de ver
é como
(ou seja, pelo menos uma ocorrência seguida de zero ou mais ocorrências). Em termos de AFN isso costuma ser implementado como o automato de
com uma transição
de seu(s) estado(s) de aceitação de volta ao(s)(s) estado(s) inicial(is) de
— assim garantimos repetição mas exigimos pelo menos uma ocorrência.\n
Passo 3
Construindo NFAs básicos (pequenas peças) que usaremos na montagem final.
- AFN para o símbolo
.
- Estados:
. - Transição:
. - Esse AFN aceita exatamente a palavra
.
- AFN para a concatenação
.
- Podemos concatenar dois blocos: um AFN para
seguido por um AFN para . - Estados (nomes sugestivos):
--(a)–> --(b)–> . - Transições:
e . - Esse AFN aceita exatamente a palavra
.\n
Passo 4
Construindo
usando Thompson (passo a passo e explicando a ideia).
- Ideia: para
com , nós pegamos o AFN de (do Passo 3) e permitimos repetições adicionando uma transição do estado final de volta ao estado inicial. Para organizar a união depois, é conveniente que cada ramo tenha sua própria “saída” que vai para um estado de aceitação comum.
Vou designar estados concretos para a parte
:
-
(início do ramo ), -
(após consumir um ; estado que permite repetir).
Transições: -
. -
(loop que permite repetir quantas vezes quiser). - Também precisaremos que, ao terminar, esse ramo possa alcançar o estado final global (que construiremos na união). Então reservamos uma transição
de para o estado final comum (essa ligação será feita mais adiante no autômato final). Essa estrutura garante pelo menos uma ocorrência de (porque precisa passar por → uma vez) e permite repetições.\n
Passo 5
Construindo
com a mesma ideia (explicando tudo devagar).
- Para
, já temos o esquema do Passo 3 para : estados --(a)–> --(b)–> . - Para
adicionamos uma transição de (estado após consumir um ) de volta ao início , permitindo repetições. - Também faremos uma transição
de para o estado final global (tal como fizemos no ramo ), para que possamos aceitar após um ou mais blocos .
Esquematicamente:
-
. -
. -
(loop para repetir). - E
também terá a opção de ir para o estado final global (essa transição será listada explicitamente no AFN final).\n
Passo 6
Fazendo a união
:
- Para representar a união em Thompson, criamos um novo estado inicial global
que faz transições para os inícios dos dois ramos e . Assim, o autômato pode “escolher” qual ramo explorar sem ler símbolo (não-determinismo via ). - Também criamos um único estado final global
. Cada ramo, ao atingir seu estado de aceitação local (no nosso desenho: para e para ), tem uma transição para . Isso centraliza a aceitação. - Mantemos as transições de repetição internas (
de para e de para ) para garantir o operador (uma ou mais repetições).
Resumo da topologia (já com nomes concretos que vou usar para listar formalmente):
- Estado inicial global:
. - Ramo
: --(a)–> , com (volta para repetir e opção de aceitar indo para ). - Ramo
: --(a)–> --(b)–> , com . - Ligações da união:
. - Estado final global:
, que é o único estado de aceitação.\n
Passo 7
Vou escrever agora o AFN final de forma formal e explícita (mostrando o conjunto de estados, o alfabeto, a função de transição
, o estado inicial e o(s) estado(s) de aceitação). Também explico o significado de cada componente para você decorar para a prova.
Definição formal de um AFN:
, onde
-
é o conjunto de estados, -
é o alfabeto (aqui ), -
é a função de transição que pode devolver conjuntos de estados (porque é não-determinística e permite -transições), -
é o estado inicial, -
é o conjunto de estados de aceitação.
Agora o AFN concreto (vou listar
como um conjunto de pares ordenados com as imagens):
- Conjunto de estados:
- Alfabeto:
- Função de transição
(lista completa das transições não-vazias):
- Estado inicial:
- Conjunto de estados de aceitação:
Breve verificação intuitiva (faça isso na prova mentalmente): do estado inicial
o autômato pode ir por
para
e então consumir pelo menos um
(porque precisa fazer
); ao chegar em
pode escolher
voltar a
para mais
s ou
ir para
e aceitar. Do outro lado,
pode ir para
e consumir um
(fazendo
e
); em
pode voltar a
por
para repetir mais
s ou ir para
e aceitar. Isso corresponde exatamente a aceitar
ou
.\n