En la teoría computacional, el problema de separar palabras es el problema de encontrar el autómata finito determinista más pequeño que se comporta de manera diferente en dos cadenas dadas, lo que significa que acepta una de las dos cadenas y rechaza la otra. El tamaño que debe tener un autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada es un problema abierto.