∈-NFA de Lenguaje Regular L = 0(0+1)*1 y L = (00)*1(11)*

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.

∈-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 simples para la construcción de ∈-NFA :
∈-NFA para 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 para 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 se modifica un poco para que incluso si no hay ningún símbolo de entrada, es decir, si el símbolo de entrada es nulo, entonces también la expresión es válida.

∈-NFA para a+b :

Esta estructura acepta a o b como entrada. Así que hay dos caminos, los cuales conducen al estado final.
 

∈-NFA para 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 para L = 0(0+1)*1 :

Siguiendo las reglas antes mencionadas, se va a construir ∈-NFA del Lenguaje Regular L =0(0+1)*1.

L = 0(0+1)*1 se puede dividir en tres partes: 0, (0+1)*, 1. La segunda parte, (0+1)*, se dibujará con la ayuda de la tercera regla (a +b) donde a = 0 yb = 1, seguido de la segunda regla a* donde a = (0+1). A continuación se muestra su ∈-NFA.
 

Dado que 0 y 1 solo están concatenados en la segunda parte, el ∈-NFA final se dibuja con la ayuda de la cuarta regla, ab.

El ∈-NFA final será:
 

∈-NFA para L = (00)*1(11)* :

Siguiendo las reglas antes mencionadas, se construirá ∈-NFA del Lenguaje Regular L = (00)*1(11)*.

L = (00)*.1.(11)* se puede dividir en tres partes para facilitar la construcción de ∈-NFA. La primera parte es (00)*, la segunda parte es 1 y la tercera es (11)*. Como todos están concatenados entre sí, la estructura principal se dibuja con la ayuda de la cuarta regla, ab. Ahora bien, para comprender la estructura de la primera parte (00)*, la referencia debe tomarse de la cuarta, es decir, ab y la segunda regla, es decir, a*. Primero se concatenan 00, luego se considera como una unidad y aplicando la segunda regla, se dibuja (00)*. A continuación se muestra su ∈-NFA.
 

De manera similar, (11)* se puede dibujar. La segunda parte del lenguaje es fácil. La primera parte y la tercera parte simplemente se concatenan con un ‘1’ en el medio.

El ∈-NFA final será: