Autómatas finitos no deterministas (NFA): NFA es un autómata finito en el que, en algunos casos, cuando se proporciona una sola entrada a un solo estado, la máquina pasa a más de 1 estado, es decir, algunos de los movimientos no pueden determinarse de forma única por el presente. estado y el símbolo de entrada actual.
An NFA can be represented as M = { Q, ∑, ∂, q0, F}
Q → Conjunto de estados finito no vacío. ∑ → Conjunto finito no vacío de símbolos de entrada. ∂ → Función de Transición. q0 → Estado inicial. F → Estado final
NFA con (nulo) o ∈ movimiento: si cualquier autómata finito contiene ε (nulo) movimiento o transacción, entonces ese autómata finito se llama NFA con ∈ movimientos
Ejemplo: Considere la siguiente figura de NFA con movimiento ∈: 
Tabla de estado de transición para el NFA anterior
| ESTADOS | 0 | 1 | épsilon |
|---|---|---|---|
| A | ANTES DE CRISTO | A | B |
| B | – | B | C |
| C | C | C | – |
Epsilon (∈) – cierre: el cierre de Epsilon para un estado X dado es un conjunto de estados que se pueden alcanzar desde los estados X con solo (nulo) o ε movimientos, incluido el propio estado X. En otras palabras, el cierre ε para un estado se puede obtener mediante la operación de unión del cierre ε de los estados que se pueden alcanzar desde X con un solo movimiento ε de manera recursiva. Para el ejemplo anterior, los ∈ cierres son los siguientes:
∈ closure(A) : {A, B, C}
∈ closure(B) : {B, C}
∈ closure(C) : {C}
Autómatas finitos deterministas (DFA): DFA es un autómata finito en el que, en todos los casos, cuando se proporciona una sola entrada a un solo estado, la máquina pasa a un solo estado, es decir, todos los movimientos de la máquina pueden determinarse de forma única mediante el estado actual y el símbolo de entrada actual.
Pasos para convertir NFA con ε-move a DFA:
Paso 1: Tome el cierre ∈ para el estado inicial de NFA como estado inicial de DFA. Paso 2: encuentre los estados que se pueden atravesar desde el presente para cada símbolo de entrada (unión del valor de transición y sus cierres para cada estado de NFA presente en el estado actual de DFA). Paso 3: si se encuentra algún estado nuevo, tómelo como estado actual y repita el paso 2. Paso 4: repita los pasos 2 y 3 hasta que no haya ningún estado nuevo presente en la tabla de transición de DFA. Paso 5: marque los estados de DFA que contienen el estado final de NFA como estados finales de DFA.
Tabla de estado de transición para DFA correspondiente a NFA anterior
| ESTADOS | 0 | 1 |
|---|---|---|
| A B C | ANTES DE CRISTO | A B C |
| ANTES DE CRISTO | C | ANTES DE CRISTO |
| C | C | C |
DIAGRAMA DE ESTADO DE DFA 
Ejemplos:
Input : 6
2
FC - BF
- C -
- - D
E A -
A - BF
- - -
Output :
STATES OF NFA : A, B, C, D, E, F,
GIVEN SYMBOLS FOR NFA: 0, 1, eps
NFA STATE TRANSITION TABLE
STATES |0 |1 eps
--------+------------------------------------
A |FC |- |BF
B |- |C |-
C |- |- |D
D |E |A |-
E |A |- |BF
F |- |- |-
e-Closure (A) : ABF
e-Closure (B) : B
e-Closure (C) : CD
e-Closure (D) : D
e-Closure (E) : BEF
e-Closure (F) : F
********************************************************
DFA TRANSITION STATE TABLE
STATES OF DFA : ABF, CDF, CD, BEF,
GIVEN SYMBOLS FOR DFA: 0, 1,
STATES |0 |1
--------+-----------------------
ABF |CDF |CD
CDF |BEF |ABF
CD |BEF |ABF
BEF |ABF |CD
Input :
9
2
- - BH
- - CE
D - -
- - G
- F -
- - G
- - BH
I - -
- - -
Output :
STATES OF NFA : A, B, C, D, E, F, G, H, I,
GIVEN SYMBOLS FOR NFA: 0, 1, eps
NFA STATE TRANSITION TABLE
STATES |0 |1 eps
--------+------------------------------------
A |- |- |BH
B |- |- |CE
C |D |- |-
D |- |- |G
E |- |F |-
F |- |- |G
G |- |- |BH
H |I |- |-
I |- |- |-
e-Closure (A) : ABCEH
e-Closure (B) : BCE
e-Closure (C) : C
e-Closure (D) : BCDEGH
e-Closure (E) : E
e-Closure (F) : BCEFGH
e-Closure (G) : BCEGH
e-Closure (H) : H
e-Closure (I) : I
********************************************************
DFA TRANSITION STATE TABLE
STATES OF DFA : ABCEH, BCDEGHI, BCEFGH,
GIVEN SYMBOLS FOR DFA: 0, 1,
STATES |0 |1
--------+-----------------------
ABCEH |BCDEGHI |BCEFGH
BCDEGHI |BCDEGHI |BCEFGH
BCEFGH |BCDEGHI |BCEFGH
Explicación: la primera línea de la entrada contiene el número de estados ( N ) de NFA. La segunda línea de la entrada dice el número de símbolos de entrada ( S ). En el ejemplo 1, el número de estados de NFA es 6, es decir ( A, B, C, D, E, F ) y 2 símbolos de entrada, es decir ( 0, 1 ). Dado que estamos trabajando en NFA con ∈ move, ∈ se agregará como un símbolo de entrada adicional. Las siguientes N líneas contienen los valores de transición para cada estado de NFA. El valor de la i-ésima fila, j-ésima columna indica el valor de transición para el i-ésimo estado en el j-ésimo símbolo de entrada. Aquí en la transición del ejemplo 1 (A, 0): FC. La salida contiene el NFA, ∈ cierre para cada estado del NFA y DFA correspondiente obtenido al convertir el NFA de entrada. También se especifican los estados y los símbolos de entrada del DFA. A continuación se muestra la implementación del enfoque anterior:
C
// C Program to illustrate how to convert e-nfa to DFA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
char NFA_FILE[MAX_LEN];
char buffer[MAX_LEN];
int zz = 0;
// Structure to store DFA states and their
// status ( i.e new entry or already present)
struct DFA {
char *states;
int count;
} dfa;
int last_index = 0;
FILE *fp;
int symbols;
/* reset the hash map*/
void reset(int ar[], int size) {
int i;
// reset all the values of
// the mapping array to zero
for (i = 0; i < size; i++) {
ar[i] = 0;
}
}
// Check which States are present in the e-closure
/* map the states of NFA to a hash set*/
void check(int ar[], char S[]) {
int i, j;
// To parse the individual states of NFA
int len = strlen(S);
for (i = 0; i < len; i++) {
// Set hash map for the position
// of the states which is found
j = ((int)(S[i]) - 65);
ar[j]++;
}
}
// To find new Closure States
void state(int ar[], int size, char S[]) {
int j, k = 0;
// Combine multiple states of NFA
// to create new states of DFA
for (j = 0; j < size; j++) {
if (ar[j] != 0)
S[k++] = (char)(65 + j);
}
// mark the end of the state
S[k] = '\0';
}
// To pick the next closure from closure set
int closure(int ar[], int size) {
int i;
// check new closure is present or not
for (i = 0; i < size; i++) {
if (ar[i] == 1)
return i;
}
return (100);
}
// Check new DFA states can be
// entered in DFA table or not
int indexing(struct DFA *dfa) {
int i;
for (i = 0; i < last_index; i++) {
if (dfa[i].count == 0)
return 1;
}
return -1;
}
/* To Display epsilon closure*/
void Display_closure(int states, int closure_ar[],
char *closure_table[],
char *NFA_TABLE[][symbols + 1],
char *DFA_TABLE[][symbols]) {
int i;
for (i = 0; i < states; i++) {
reset(closure_ar, states);
closure_ar[i] = 2;
// to neglect blank entry
if (strcmp(&NFA_TABLE[i][symbols], "-") != 0) {
// copy the NFA transition state to buffer
strcpy(buffer, &NFA_TABLE[i][symbols]);
check(closure_ar, buffer);
int z = closure(closure_ar, states);
// till closure get completely saturated
while (z != 100)
{
if (strcmp(&NFA_TABLE[z][symbols], "-") != 0) {
strcpy(buffer, &NFA_TABLE[z][symbols]);
// call the check function
check(closure_ar, buffer);
}
closure_ar[z]++;
z = closure(closure_ar, states);
}
}
// print the e closure for every states of NFA
printf("\n e-Closure (%c) :\t", (char)(65 + i));
bzero((void *)buffer, MAX_LEN);
state(closure_ar, states, buffer);
strcpy(&closure_table[i], buffer);
printf("%s\n", &closure_table[i]);
}
}
/* To check New States in DFA */
int new_states(struct DFA *dfa, char S[]) {
int i;
// To check the current state is already
// being used as a DFA state or not in
// DFA transition table
for (i = 0; i < last_index; i++) {
if (strcmp(&dfa[i].states, S) == 0)
return 0;
}
// push the new
strcpy(&dfa[last_index++].states, S);
// set the count for new states entered
// to zero
dfa[last_index - 1].count = 0;
return 1;
}
// Transition function from NFA to DFA
// (generally union of closure operation )
void trans(char S[], int M, char *clsr_t[], int st,
char *NFT[][symbols + 1], char TB[]) {
int len = strlen(S);
int i, j, k, g;
int arr[st];
int sz;
reset(arr, st);
char temp[MAX_LEN], temp2[MAX_LEN];
char *buff;
// Transition function from NFA to DFA
for (i = 0; i < len; i++) {
j = ((int)(S[i] - 65));
strcpy(temp, &NFT[j][M]);
if (strcmp(temp, "-") != 0) {
sz = strlen(temp);
g = 0;
while (g < sz) {
k = ((int)(temp[g] - 65));
strcpy(temp2, &clsr_t[k]);
check(arr, temp2);
g++;
}
}
}
bzero((void *)temp, MAX_LEN);
state(arr, st, temp);
if (temp[0] != '\0') {
strcpy(TB, temp);
} else
strcpy(TB, "-");
}
/* Display DFA transition state table*/
void Display_DFA(int last_index, struct DFA *dfa_states,
char *DFA_TABLE[][symbols]) {
int i, j;
printf("\n\n********************************************************\n\n");
printf("\t\t DFA TRANSITION STATE TABLE \t\t \n\n");
printf("\n STATES OF DFA :\t\t");
for (i = 1; i < last_index; i++)
printf("%s, ", &dfa_states[i].states);
printf("\n");
printf("\n GIVEN SYMBOLS FOR DFA: \t");
for (i = 0; i < symbols; i++)
printf("%d, ", i);
printf("\n\n");
printf("STATES\t");
for (i = 0; i < symbols; i++)
printf("|%d\t", i);
printf("\n");
// display the DFA transition state table
printf("--------+-----------------------\n");
for (i = 0; i < zz; i++) {
printf("%s\t", &dfa_states[i + 1].states);
for (j = 0; j < symbols; j++) {
printf("|%s \t", &DFA_TABLE[i][j]);
}
printf("\n");
}
}
// Driver Code
int main() {
int i, j, states;
char T_buf[MAX_LEN];
// creating an array dfa structures
struct DFA *dfa_states = malloc(MAX_LEN * (sizeof(dfa)));
states = 6, symbols = 2;
printf("\n STATES OF NFA :\t\t");
for (i = 0; i < states; i++)
printf("%c, ", (char)(65 + i));
printf("\n");
printf("\n GIVEN SYMBOLS FOR NFA: \t");
for (i = 0; i < symbols; i++)
printf("%d, ", i);
printf("eps");
printf("\n\n");
char *NFA_TABLE[states][symbols + 1];
// Hard coded input for NFA table
char *DFA_TABLE[MAX_LEN][symbols];
strcpy(&NFA_TABLE[0][0], "FC");
strcpy(&NFA_TABLE[0][1], "-");
strcpy(&NFA_TABLE[0][2], "BF");
strcpy(&NFA_TABLE[1][0], "-");
strcpy(&NFA_TABLE[1][1], "C");
strcpy(&NFA_TABLE[1][2], "-");
strcpy(&NFA_TABLE[2][0], "-");
strcpy(&NFA_TABLE[2][1], "-");
strcpy(&NFA_TABLE[2][2], "D");
strcpy(&NFA_TABLE[3][0], "E");
strcpy(&NFA_TABLE[3][1], "A");
strcpy(&NFA_TABLE[3][2], "-");
strcpy(&NFA_TABLE[4][0], "A");
strcpy(&NFA_TABLE[4][1], "-");
strcpy(&NFA_TABLE[4][2], "BF");
strcpy(&NFA_TABLE[5][0], "-");
strcpy(&NFA_TABLE[5][1], "-");
strcpy(&NFA_TABLE[5][2], "-");
printf("\n NFA STATE TRANSITION TABLE \n\n\n");
printf("STATES\t");
for (i = 0; i < symbols; i++)
printf("|%d\t", i);
printf("eps\n");
// Displaying the matrix of NFA transition table
printf("--------+------------------------------------\n");
for (i = 0; i < states; i++) {
printf("%c\t", (char)(65 + i));
for (j = 0; j <= symbols; j++) {
printf("|%s \t", &NFA_TABLE[i][j]);
}
printf("\n");
}
int closure_ar[states];
char *closure_table[states];
Display_closure(states, closure_ar, closure_table, NFA_TABLE, DFA_TABLE);
strcpy(&dfa_states[last_index++].states, "-");
dfa_states[last_index - 1].count = 1;
bzero((void *)buffer, MAX_LEN);
strcpy(buffer, &closure_table[0]);
strcpy(&dfa_states[last_index++].states, buffer);
int Sm = 1, ind = 1;
int start_index = 1;
// Filling up the DFA table with transition values
// Till new states can be entered in DFA table
while (ind != -1) {
dfa_states[start_index].count = 1;
Sm = 0;
for (i = 0; i < symbols; i++) {
trans(buffer, i, closure_table, states, NFA_TABLE, T_buf);
// storing the new DFA state in buffer
strcpy(&DFA_TABLE[zz][i], T_buf);
// parameter to control new states
Sm = Sm + new_states(dfa_states, T_buf);
}
ind = indexing(dfa_states);
if (ind != -1)
strcpy(buffer, &dfa_states[++start_index].states);
zz++;
}
// display the DFA TABLE
Display_DFA(last_index, dfa_states, DFA_TABLE);
return 0;
}
Uso de NFA con ∈ move: si queremos construir un FA que acepte un idioma, a veces se vuelve muy difícil o parece imposible construir un NFA o DFA directo. Pero si se usa NFA con ∈ movimientos, entonces el diagrama de transición se puede construir y describir fácilmente.
Publicación traducida automáticamente
Artículo escrito por Agnibha_Chandra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA