∈-NFA del Lenguaje Regular L = {ab,ba}

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 hay 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 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 q ₂ a q _{1 de} modo 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 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 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 para L = {ab, ba} :
Siguiendo las reglas antes mencionadas, se construirá ∈-NFA de Lenguaje Regular L ={ab, ba}.

El idioma consta de ab o ba, que también se puede escribir como (ab + ba). Siguiendo la regla de construir una adición o (a+b), tenemos que construir la estructura principal. Sin embargo, aquí, ‘a’ en a+b es en realidad la expresión ‘ab’ y ‘b’ en a+b es en realidad la expresión ‘ba’. Entonces, simplemente reemplazamos sus estructuras en lugar de a y b respectivamente. Entonces, el ∈-NFA final tendrá dos caminos, uno para ab y otro para ba, los cuales conducen al estado final.

Siguiendo la regla de construcción de concatenación o ab, podemos construir individualmente las estructuras para ab y ba. Para la concatenación, se puede elegir cualquiera de las dos estructuras mencionadas anteriormente, es decir, con épsilon o sin épsilon, pero elegimos la que tiene épsilon porque es un ∈-NFA.

El ∈-NFA final será: