NFA que acepta un conjunto de strings sobre un alfabeto {0, 1, 2} tal que el dígito final ha aparecido antes

Requisito previo: introducción del 
programa Finite Automata C++ para construir un NFA que acepte el conjunto de strings sobre un alfabeto {0, 1, 2} tal que el dígito final haya aparecido antes.

Ejemplos: 

Input : 01101 
Output : Accepted

Input : 012
Output : Not Accepted

Input : 2
Output : Not Accepted

Input : 0122
Output : Accepted 

Explicación: 
En el primer ejemplo, 01101, el último dígito ‘1’ se encontraba en las letras número 2 y 3 de la string. Por lo tanto, se acepta. En el segundo ejemplo, 012, la ocurrencia de ‘2’ está solo en el último lugar. Por lo tanto, se rechaza. De manera similar, con el tercer ejemplo, se rechaza 2. En el último ejemplo, el último dígito ‘2’ ocurrió antes del final de la string, por lo que se acepta. 

Acercarse: 

  1. Construya un estado inicial.
  2. Construya 3 estados para la entrada de 0, 1 y 2.
  3. Repita los bucles en todos los estados para todas las entradas.
  4. Conectar todo el estado con un estado final.

Diagrama de transacción de estado NFA: 

Implementación:

C++

#include <bits/stdc++.h>
using namespace std;
 
// function of state one or starting state
void q1(string s, int pos, int len);
 
// function of state two
void q2(string s, int pos, int len);
 
// function of state three
void q3(string s, int pos, int len);
 
// function of state four
void q4(string s, int pos, int len);
 
// function of state five
void q5(string s, int pos, int len);
 
// See diagram for help
 
vector<string> states;
int accepted = 0;
 
// Uncomment this function and the function calls to see
// the path of string from the start state to end state
/*
void printVector()
{
    for (auto i = states.begin(); i != states.end(); i++)
        cout << *i << " ";
    cout << endl;
}
*/
void q5(string s, int pos, int len)
{
    states.push_back("Q5->");
    if (pos == len) {
        // printVector();
        accepted = 1;
    }
    else {
        states.push_back("Dead");
        // printVector();
        states.pop_back();
    }
    states.pop_back();
    return;
}
 
void q4(string s, int pos, int len)
{
    states.push_back("Q4->");
    if (pos == len) {
        // printVector();
        states.pop_back();
        return;
    }
    if (s[pos] == '2')
        q5(s, pos + 1, len);
    q4(s, pos + 1, len);
    states.pop_back();
    return;
}
 
void q3(string s, int pos, int len)
{
    states.push_back("Q3->");
    if (pos == len) {
        // printVector();
        states.pop_back();
        return;
    }
    if (s[pos] == '1')
        q5(s, pos + 1, len);
    q3(s, pos + 1, len);
    states.pop_back();
    return;
}
 
void q2(string s, int pos, int len)
{
    states.push_back("Q2->");
    if (pos == len) {
        // printVector();
        states.pop_back();
        return;
    }
    if (s[pos] == '0')
        q5(s, pos + 1, len);
    q2(s, pos + 1, len);
    states.pop_back();
    return;
}
 
void q1(string s, int pos, int len)
{
    states.push_back("Q1->");
    if (pos == len) {
        // printVector();
        states.pop_back();
        return;
    }
    if (s[pos] == '0')
        q2(s, pos + 1, len);
    else if (s[pos] == '1')
        q3(s, pos + 1, len);
    else if (s[pos] == '2')
        q4(s, pos + 1, len);
 
    q1(s, pos + 1, len);
    states.pop_back();
    return;
}
 
int main()
{
    string s;
    // cin >> s;
    s = "01101";
 
    int pos = 0;
    q1(s, pos, s.length());
 
    if (accepted)
        cout << "Accepted" << endl;
    else
        cout << "Not Accepted" << endl;
    return 0;
}

Publicación traducida automáticamente

Artículo escrito por ayushsaxena77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *