Epsilon NFA es parte de Finite Automata. ∈ es un símbolo que representa entradas vacías. ∈-NFA es la representación que permite que un autómata cambie su estado sin entrada. ∈-Los autómatas finitos no deterministas tienen una función de transición diferente a la NFA regular. 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.
Reglas simples para la construcción de ∈-NFA:
∈-NFA for a+ :
Aquí, ‘a+’ significa que debe haber al menos una ‘a’ en la expresión de entrada para que sea aceptable. Está precedido y seguido por epsilon porque la expresión puede o no contener nada más. 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* :
Aquí, ‘a*’ significa que puede haber cualquier número de ‘a’ en la expresión, incluido el 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 = (01+2*)1 :
Siguiendo las reglas antes mencionadas, se construirá ∈-NFA del Lenguaje Regular L = (01+2*)1.
L = (01+2*)1 se puede dividir en dos partes. La primera parte es (01+2*) y la segunda parte es 1. Dado que están concatenados, deben conectarse linealmente con la ayuda de la cuarta regla. Ahora, la primera parte se puede dividir en dos partes: 01 y 2*. 01 se puede dibujar con la ayuda de la cuarta regla considerando a = 0 y b = 1. 2* se puede dibujar con la ayuda de la segunda regla considerando a = 2. Ahora que 01 y 2* están conectados con un ‘+’ signo, habrá dos caminos desde el primer Node, los cuales llegarán al penúltimo Node. Esta estructura cuando va seguida de un ‘1’ nos da el ∈-NFA final del lenguaje mencionado anteriormente.
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