Expressão → AFN
AFN → AFD
Minimizar
CYK
Autómato → expressão
Enunciado
Símbolos de uma letra ou algarismo; | união, * fecho, + um ou mais, ? opcional, parênteses e ε.
Cada pedaço numera o seu estado inicial antes dos filhos e o seu estado final depois; ao concatenar, o final do primeiro é o inicial do segundo (sem ε).Aho et al. §3.7.4 · Pisa PLP-05
Testar palavras
Uma palavra por linha; a vazia escreve-se ε. Testa-se no AFN, no AFD e no AFD mínimo: os três têm de dizer o mesmo, porque reconhecem a mesma linguagem. Clica numa para ver o seu percurso.
As mais curtas que aceita:
As mais curtas que rejeita:
Clica num para o adicionar à lista.
Traço
N(a): dois estados, 2 e 3, unidos por «a».
Passo 1 de 7 N(a): dois estados, 2 e 3, unidos por «a».
A concatenação não é um passo: não cria estados, apenas junta o final de um pedaço ao início do seguinte.
AFN com 11 estados; inicial 0, final 10.