Converta as seguintes expressões regulares em AFNs.
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 é
Informação fornecida (interpretação que vou usar): a expressão é
Observação sobre a notação: no enunciado original havia e o símbolo
.
\(\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
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:
- Símbolo simples
(por exemplo ou ): cria-se um pequeno AFN com dois estados e uma transição rotulada por :
- Concatenação
: conecta-se o estado de aceitação de ao estado inicial de com uma transição (pode-se também “colar” os estados, mas usar é padrão). - União
: cria-se um novo estado inicial com -transições para os inícios de e , e um novo estado de aceitação com -transições das aceitações de e para ele. - Fecho de Kleene
: cria-se um novo início e um novo fim; do novo início vai para o antigo início e para o novo fim; da antiga aceitação vai 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
. Em cada passo explico o porquê e mostro claramente as transições.
Passo 3
Construção do AFN para o símbolo
.
Crio dois estados:
Aqui
é o início do trecho e
é o estado de aceitação desse trecho.
Passo 4
Construção do AFN para a palavra
(concatenação de três símbolos).
Faço em três pedaços e concateno:
Aqui
é o início do bloco
e
é sua aceitação.
Passo 5
Aplicar o fecho de Kleene ao bloco
usando a construção de Thompson.
Para
com início
e aceitação
, criamos um novo início
e um novo aceitação
e as
-transições padrão:
-
(entrar no bloco), -
(permitir zero cópias), -
(repetir o bloco), -
(sair do fecho para o estado final).
Assim o trecho
fica com os estados e transições:
e também as
-transições
e
.
Explicação rápida do porquê: essas
-transições permitem executar zero cópias (ir direto
) ou executar uma cópia e voltar para repetir (via
).
Passo 6
Concatenar o símbolo
com o fecho
para obter
.
Pelo passo 3 temos
. Pelo passo 5 o fecho tem início
. Para concatenar, faço uma
-transição do estado de aceitação do primeiro pedaço
para o início do segundo
:
Assim o trecho
tem início
e aceitação
(o
criado no fecho é o aceitação final desse trecho).
Passo 7
Construção do AFN para o símbolo à direita da união:
.
Crio dois estados:
Aqui
é o início do pedaço que reconhece só
, e
é sua aceitação.
Passo 8
Aplicar a operação de união entre os dois pedaços:
(início
, aceitação
) e
(início
, aceitação
).
Pelo esquema de Thompson, crio um novo estado inicial global
e um novo estado de aceitação global
. Coloco
-transições:
- Do novo início para cada início dos sub-autômatos:
- Das aceitações de cada sub-autômato para o novo estado de aceitação:
Agora temos um AFN completo cujo início é
e aceitação é
.
Passo 9
Listagem final do AFN obtido — vou apresentar como a 5-tupla
e também como tabela de transições para ficar prático na prova.
Conjunto de estados:
Alfabeto:
Estado inicial:
Conjunto de estados de aceitação:
Função de transição
(mostrada como lista de transições;
indica transição vazia):
Observação sobre a interpretação prática: desse AFN, quaisquer caminhos que levam de
a
reconhecem cadeias da linguagem. Por exemplo:
- Para reconhecer a palavra
: . - Para reconhecer
: (note que pode gerar zero cópias, então pertence à linguagem). - Para reconhecer
: .]
Resposta
e
dada por