∈-NFA del Lenguaje Regular L = bc(ab+c)*a+

Los autómatas finitos se pueden clasificar en tres tipos: 

1. DFA
2. NFA
3. ∈-NFA.

La única diferencia entre ∈-NFA y NFA es que ∈-NFA tiene una función de transición diferente a la NFA normal. ∈ representa entradas vacías. ∈-NFA muestra que un autómata puede cambiar su estado sin una entrada, es decir, incluso si la entrada es nula, el autómata puede cambiar su estado. Aquí está la definición formal 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.

Hay algunas reglas especiales para la construcción de ∈-NFA.

Reglas simples para la construcción de ∈-NFA –

1. ∈-NFA para a+ :

La primera regla establece que al menos una ‘a’ debe estar en la expresión para que sea aceptable cuando tiene ‘a+’. ∈ muestra la falta de otros símbolos en la expresión que no la invalidarán. Sin embargo, hay retroalimentación del estado q2 al q1 que muestra que puede haber más de un ‘a’.

2. ∈-NFA para a* :

La segunda regla establece que ‘a*’ significa que puede haber 0 o n número de ‘a’ en la expresión. La estructura de a+ se modificó un poco agregando un ciclo que va directamente de q0 al estado final, lo que significa que la expresión puede no tener nada y seguir siendo aceptable.

3. ∈-NFA para a+b :

La tercera regla a+b funciona como la lógica OR. Significa que la expresión puede tener a o b, y será aceptable. Así que hay dos caminos, los cuales conducen al estado final.

4. ∈-NFA para ab :

La cuarta regla es la regla de concatenación que establece que a debe ir seguido 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.

5. ∈-NFA para L = bc(ab+c)*a+ :
Siguiendo las reglas antes mencionadas, se construirá ∈-NFA del Lenguaje Regular L = bc(ab+c)*a+ .
L = bc(ab+c)*a+ se puede dividir en 3 partes-

• La primera parte es ‘bc’, que se puede dibujar usando la regla de concatenación, es decir, la cuarta regla intercambiando a y b con b y c en la regla original, y aquí consideramos el ∈ adicional ya que es un NFA épsilon.
• La segunda parte es ‘(ab+c)*’, que es una combinación de tres reglas en sí misma. Si consideramos ab+c como una unidad, entonces (ab+c)* se puede dibujar con la ayuda de la segunda regla, a*. Ahora, ab+c está conectado por ‘+’, así que podemos dibujarlo con la ayuda de la tercera regla. Dado que es una conexión OR, habrá dos caminos, uno que tiene ab y otro que tiene c. ‘ab’ se puede dibujar con la ayuda de la regla de concatenación. A continuación se muestra su ∈-NFA.
• La tercera parte es ‘a+’, que es la primera regla en sí. Ahora, las tres partes están conectadas entre sí mediante la regla de concatenación.

El ∈-NFA final será: