1. Determinizar e minimizar o ε-NFA de (a|b)*abb
Estudante de teoria da computaçãoContexto
Um exercício de linguagens formais usa um ε-NFA de 11 estados para representar a expressão (a|b)*abb.
Problema
Obter o DFA equivalente e verificar quantos estados permanecem após a minimização.
Como usar
Selecione o modo de autômatos, informe a definição do ε-NFA e mantenha ativadas as opções de construção por subconjuntos e minimização.
machine: states: 0 1 2 3 4 5 6 7 8 9 10; start: 0; accept: 10; alphabet: a b; 0 ε 1; 0 ε 7; 1 ε 2; 1 ε 4; 2 a 3; 3 ε 6; 4 b 5; 5 ε 6; 6 ε 1; 6 ε 7; 7 a 8; 8 b 9; 9 b 10Resultado
A construção gera um DFA de 5 estados, e o refinamento de Moore reduz o resultado ao DFA mínimo de 4 estados.