Requisito previo: introducción de autómatas finitos
Los autómatas finitos no deterministas y los autómatas finitos no deterministas ∈ son casi lo mismo excepto por su función de transición y existen algunas reglas especiales para la construcción de ∈-NFA.
En ∈-NFA, los siguientes son los estados de la siguiente manera.
∈-NFA is defined in 5 tuple representation {Q, q0, Σ, δ, F} where
Q is the set of all states,
q0 is the initial state,
Σ is the set of input symbols,
δ is the transition function which is δ:Q × (Σ∪∈)->2Q and
F is the set of final states.
Reglas para construir ∈-NFA:
Reglas simples para la construcción de ∈-NFA de la siguiente manera.
∈-NFA for a+ :
Esta estructura es para a+, lo que significa que debe haber al menos una ‘a’ en la expresión. Está precedido por epsilon y también sucedido por uno. Hay una retroalimentación épsilon del estado q2 al q1, por lo que puede haber más de una ‘a’ en la expresión.
∈-NFA for a* :
Esta estructura es para a*, lo que significa que puede haber cualquier número de ‘a’ en la expresión, incluso 0. La estructura anterior solo se modifica un poco para validar el símbolo de entrada nulo, por lo que esa expresión también es válida.
∈-NFA for a+b :
Esta estructura acepta a o b como entrada. Así que hay dos caminos, los cuales conducen al estado final.
∈-NFA for ab :
Para la concatenación, a debe ir seguida de b. Sólo entonces puede llegar al estado final. Ambas estructuras están permitidas aquí, pero como es ∈-NFA, se recomienda la segunda estructura.
∈-NFA for L = (a* + b*) :
Siguiendo las reglas antes mencionadas, se construirá el ∈-NFA del Lenguaje Regular L =a* + b*. El lenguaje anterior se puede dividir en dos partes. La primera parte es a* y la segunda parte es b*, que se pueden construir exactamente como la primera parte. Como hay un signo ‘+’ que conecta las dos partes, habrá dos caminos, los cuales conducirán al estado final.
La primera parte es a*, por lo que se dibujará exactamente como la segunda regla. Nuevamente, usando la segunda regla y reemplazando a con b, obtenemos la segunda parte, b*.
∈-NFA final:
El ∈-NFA final será:
Publicación traducida automáticamente
Artículo escrito por srishtiganguly1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA