Un linguaggio regolare finito riconosce un insieme finito di stringhe.
Posso costruire un automa sotto forma di albero in cui il percorso più lungo corrisponde alla stringa più lunga.
Quindi è possibile costruire un automa il cui numero massimo di stati è la lunghezza della stringa più lunga per il numero di lettere.