Converta as seguintes expressões regulares em AFNs.
a) b
Passo 1
O enunciado pede para converter a expressão regular
em um AFN (autômato finito não-determinístico).\n
Informações dadas:
Informações dadas:
- A expressão regular é
. - Os símbolos que aparecem são
, e o símbolo vazio . - O que se espera: um AFN que reconheça exatamente a mesma linguagem dessa expressão.
Passo 2
Escolha do método: vou usar duas etapas didáticas.
- Primeiro mostro a construção sistemática (tipo Thompson) passo a passo — isso te ensina um método geral que serve para qualquer expressão regular.
- Depois apresento uma versão simplificada e pequena do AFN (sem
-transições) — essa é a que você provavelmente desenha rápido na prova porque é mais enxuta.
Explico o porquê: Thompson é um procedimento mecânico e seguro; a simplificação mostra como otimizar para a hora da prova.
Passo 3
Átomos da expressão e NFAs básicos:
- Para o símbolo
(cadeia vazia) um AFN simples tem um estado inicial e um estado final com uma transição por . - Representação: estados
, início , final , transição .
- Representação: estados
- Para o símbolo
um AFN simples tem uma transição rotulada . - Representação: estados
, início , final , transição .
- Representação: estados
- Para o símbolo
um AFN simples tem uma transição rotulada . - Representação: estados
, início , final , transição .
- Representação: estados
Passo 4
Construção da união
(Thompson):
- Criamos um novo estado inicial
e um novo estado final . - Ponho
-transições de para os inícios de e de , ou seja para e . - Ponho
-transições dos finais de e de para , ou seja de e de para .
Assim eu obtenho um AFN paracom início e final .
Passo 5
Concatenação com
:
- Para concatenar, coloco uma
-transição do estado final da união para o início do AFN de , que é . - O estado inicial do AFN final será
e o estado final será . - Lista de transições (forma de conjunto de triplas) resultantes do método Thompson:
- Conjunto de estados final:
. Início: .
Passo 6
Interpretação da linguagem e execução em exemplo (para fixar):
- A expressão
gera exatamente as cadeias (quando escolhemos e depois concatenamos ) e (quando escolhemos e depois concatenamos ). Logo a linguagem é . - Simulação rápida no AFN de Thompson:
- Para a palavra
: do faço até , de via para , via para , via para e então com para (aceita). - Para a palavra
: do faço para , com vou para , para , para , com para (aceita).
- Para a palavra
Passo 7
AFN simplificado (mais prático para a prova)
- Como a linguagem é apenas
, dá para desenhar um AFN muito direto, sem -transições: - Estados:
. - Estado inicial:
. - Estado final:
. - Transições:
- Estados:
- Interpretação: de
posso consumir um e ir direto para o estado final (reconhece ), ou consumir um e depois um para chegar ao final (reconhece ). Esse AFN é pequeno, fácil de desenhar e o que você precisa levar para a prova.
Resposta
Estados:
Alfabeto:
Estado inicial:
Estado final:
Transições:
Alfabeto:
Estado inicial:
Estado final:
Transições: