Suponha que o DNA de um organismo é formado pelas 4 letras A, T, C, G.
Sabe-se que um certo gene possui a seguinte característica:
Começa com A A seguido de qualquer sequencia das letras T, C, G com pelo menos uma ocorrência da letra T e termina com A A
Apresente um diagrama de estados finitos que reconhece esse gene.
Suponha que uma letra é lida por ciclo do autômato finito, e que as entradas são A, T, C, G, FIM:
e a saída X deve valer 1 quando o gene é reconhecido.
Para facilitar, pode supor que a cadeia dada de fato representa o tal gene. Isto é, não é preciso prever casos de erro (cadeia não representa o gene).