Dada una string binaria str , la tarea es crear un DFA que acepte los idiomas que terminan en «01» sobre los caracteres {0, 1} .
Ejemplos:
Entrada: str = “00011101”
Salida: String aceptada
Explicación:
Como la string dada termina en “01”, por lo tanto, se acepta.Entrada: str = “00001111”
Salida: String rechazada
Explicación:
Como la string dada termina en “11”, por lo tanto, se rechaza.
Enfoque: para resolver el problema anterior, a continuación se muestran el estado de la clase y la función miembro necesaria:
- Par 1: trata con el primer tipo de entrada, es decir, 0, y lo vincula con un puntero de objeto al siguiente estado.
- Par 2: se ocupa del segundo tipo de entrada, es decir, 1, y lo vincula con un puntero de objeto al siguiente estado.
- m_x: Define si un determinado estado es inicial o final.
Las funciones de miembro de clase se definen a continuación:
- initialize(): esta función toma los dos pares (utilizados para dos tipos de entradas) como parámetros junto con el carácter que define el estado (i o f).
- transición(): actúa como una tabla de transición para los autómatas y con una entrada particular, pasa de un estado al siguiente estado.
- traverse(): esta función toma la string de entrada y la pasa a través de los autómatas.
- check(): esta función verifica si después de que la entrada ha finalizado, el estado final es un estado final o no. Si es final, la string se acepta; de lo contrario, se rechaza.
Para este problema se necesitan tres estados. Por lo tanto, cree objetos de tres clases e inicialícelos con los valores requeridos como:
- Estado 1: En la entrada 0 pasa al Estado 2 y en la entrada 1 pasa a sí mismo.
- Estado 2: En la entrada 0 va a sí mismo y en la entrada 1 va al Estado 3.
- Estado 3: En la entrada 0 va al Estado 2 y en la entrada 1 va al Estado 1. Además, este es nuestro estado final.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program of a DFA that accepts
// all string ending with "01"
#include <iostream>
#include <string>
using namespace std;
// Class for automata
class State {
private:
// Data members to store the input
pair<int, State*> Pair1;
pair<int, State*> Pair2;
char m_x;
public:
// Pointer to the state of automata
static State* m_ptr;
// Constructor to initialize state
State()
{
Pair1.first = 0;
Pair1.second = nullptr;
Pair2.first = 0;
Pair2.second = nullptr;
m_x = ' ';
}
// Initialise pair1 and pair2
// with state x
void initialize(
pair<int, State*> pair1,
pair<int, State*> pair2, char x)
{
Pair1 = pair1;
Pair2 = pair2;
m_x = x;
}
// Passes a string through automata
static void transition(int input);
static void traverse(string& str, int n);
// Checks if the last state
// is final or not
static void check();
};
// Pointer to the current
// state of automata
State* State::m_ptr{ nullptr };
// Function to provide state
// transition of automata
void State::transition(int input)
{
if ((*m_ptr).Pair1.first == input)
m_ptr = (*m_ptr).Pair1.second;
else
m_ptr = (*m_ptr).Pair2.second;
}
// Checks if the last state
// is final or not
void State::check()
{
if ((*m_ptr).m_x == 'f')
cout << "String Accepted\n"
<< endl;
else
cout << "String Rejected\n"
<< endl;
}
// Passes a string through automata
void State::traverse(string& str, int n)
{
for (int i = 0; i < n; i++) {
int x{ (int)str[i] - (int)'0' };
transition(x);
}
}
// Function to check if the given
// is accepted in DFA or not
void isAccepted(string str)
{
// States of the automata
State one, two, three;
// Transition table for required
// automata
one.initialize({ 0, &two },
{ 1, &one }, 'i');
two.initialize({ 0, &two },
{ 1, &three }, 'i');
three.initialize({ 0, &two },
{ 1, &one }, 'f');
int length{ static_cast<int>(str.length()) };
State::m_ptr = &one;
// Function call
State::traverse(str, length);
State::check();
}
// Driver Code
int main()
{
string str{ "00111101" };
isAccepted(str);
return 0;
}
String Accepted
Complejidad temporal: O(N)
Espacio auxiliar: O(1)