AFNDs con Trancisiones Lambda:

Propiedades

Operaciones Importantes sobre AFD y AFND

• Infertir los estados finales del autómata $F' = F - Q$ | | Clausura de Kleene ($L^*$) | - Trancisión $\lambda$ de todos los estados finales al inicial.
• El estado inicial se transforma en final. | | Reversa ($L^r$) | - Crear estado nuevo estado inicial.
• Unir los finales con el nuevo estado inicial con trancisiones $\lambda$.
• Dar vuelta las trancisiones.
• Terminar en el estado inicial original. | | Prefijos ($\text{Ini}(L)$) | - Todos los estados que estan camino a un estado final se convierten en estados fonales. | | Sufijos ($\text{Fin}(L)$) | - Nuevo estado inicial del cual salen $\lambda$ a todos los estados del autómata. No preserva determinismo. | | Subcadena ($\text{Sub}(L)$) | - Aplicar prefijos y sufijos. | | Cadenas maximales ($\text{Max}(L)$) | - En caso de que haya ciclos, la respuesta es el autómata vacío.
• En caso de que algún estado final esté en camino a otro estado final, entonces ese nodo no será estado final del nuevo autómata. | | Cadenas Minimales ($\text{Min}(L)$). Ningún prefijo propio pertenece al lenguaje. | - Para los estados finales que contienen algún estado final en el camino, eliminarlos.
• Para los estados finales que quedan, eliminar trancisiones que salen de estos. | | $L.\Sigma^* = L_t$ | - Agregar autoaristas con todos los caracteres a los estados finales. Eliminar las trancisiones salientes. |

Operaciones Más Complejas