Algoritmos de decisión de lenguages regulares

Pertenencia:

¿$w\in L$? sí, se puede contestar la pregunta (es decir, es un problema computable), porque

• construimos un AFD $M$ que acepte $L$
• simulamos su comportamiento leyendo la palabra $w$
• si acabamos en un estado final, $w$ está en $L$, sino $w$ no está en $L$

Vaciedad:

¿$L=\emptyset$? sí, se puede contestar la pregunta (es decir, es un problema computable) porque

• construimos un autómata que acepte $L$
• analizamos el grafo del autómata para averiguar si existe un camino desde el estado incial hacia un estado final (dicho proceso resulta más fácil, si se añade un estado y se conecta todos los estados finales a este estado, así basta buscar un camino entre el estado inicial y el estado añadido)
• si existe tal camino, entonces $L$ no es vacío, sino $L$ es vacío

Cardinalidad:

¿$\vert L\vert<\infty$? sí, se puede contestar la pregunta (es decir, es un problema computable) porque

• construimos un autómata que acepte $L$
• analizamos el grafo del autómata para averiguar si existe un ciclo en un camino entre el estado inicial y algún estado final
• si existe tal ciclo, entonces $L$ es infinito, sino $L$ es finito

Igualidad:

¿$L_1=L_2$? sí, se puede contestar la pregunta (es decir, es un problema computable) porque

• construimos los autómatas finitos deterministas y mínimos que acepten $L_1$ y $L_2$
• comparamos la estructura de los grafos de ambos autómatas
• si son iguales, entonces ambos lenguajes son iguales, sino son diferentes
  (Nota: comparar dos grafos generales y decidir si son iguales ,es decir, el problema de isomorfía de grafos, es un problema que se puede calcular, pero todavía no se conoce el algoritmo óptimo. Para los AFD mínimos se reduce la complejidad porque las aristas llevan atributos y se conoce ambos estados iniciales que tengan que coincidir. )