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:
- Construya un estado inicial.
- Construya 3 estados para la entrada de 0, 1 y 2.
- Repita los bucles en todos los estados para todas las entradas.
- 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