En la teoría de los autómatas, los autómatas finitos se pueden clasificar en tres tipos:
- DFA
- NFA
- ∈-NFA
∈ significa una entrada vacía. Eso significa que el autómata puede cambiar su estado incluso cuando obtiene un símbolo vacío, es decir, ∈. Eso es lo que lo hace diferente de NFA. 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+ :
‘a+’ representa que la expresión debe contener al menos una a para ser aceptada por el autómata. La conexión de retroalimentación del estado q2 al estado q1 es para indicar que la expresión puede contener más de una a y se denota por ∈, de modo que se pueden aceptar dos ‘a’ continuas ya que la retroalimentación no necesita ser activada por alguna otra entrada.
2. ∈-NFA para a* :
‘a*’ representa que puede haber cero o más ‘a’ en la expresión. Al igual que el anterior, hay retroalimentación del estado q2 al q1 pero también hay una transición del estado q0 al q3, es decir, directamente del estado inicial al estado final lo que demuestra que la expresión se aceptará incluso si no hay ‘a ‘ en eso.
3. ∈-NFA para a+b :
‘a+b’ representa la lógica OR. Significa que la expresión puede contener a o b o ambos y será aceptable. Así que hay dos caminos, los cuales conducen al estado final.
4. ∈-NFA para ab :
‘ab’ representa la lógica AND. También se conoce como regla de concatenación. Aquí a debe ser seguida estrictamente por b y sólo entonces se aceptará la expresión. Ambas estructuras están permitidas aquí, pero como es ∈-NFA, se recomienda la segunda estructura.
∈-NFA para L = 00(01+10)*11 :
A partir de las reglas mencionadas anteriormente, se puede extraer ∈-NFA del lenguaje regular L = 00(01+10)*11.
Se puede dividir en tres partes. La primera parte es ’00’, la segunda parte es (01+10)* y la última parte es ’11’. La primera parte y la tercera parte son similares a la regla de concatenación donde tanto a como b denotan el mismo símbolo, ya sea 0 o 1.
La segunda parte se dibuja usando la regla cuarta, tercera y segunda. Construimos 01 y 10 usando la cuarta regla. Luego los unimos usando la tercera regla donde a = 01 yb = 10. Luego aplicamos la segunda regla y consideramos 01+10 como una unidad. Aquí está la segunda parte dibujada por separado.
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