Hola.
Se puede construir directamente el AFD, en realidad es bastante inmediato. Si no te sale de primeras puedes construir un AFN que reconozca el lenguaje concatenando dos AFD y a partir de él construir el AFD equivalente. ¿Conoces el método para pasar de un AFN a un AFD? ¿Y el de concatenar dos AFD?
Intenta concretar al máximo tus dudas. Será más sencillo ayudarte y obtendrás respuestas más adaptadas a tus necesidades.
Un saludo.