DFA acepta todas las strings sobre w ∈(a,b)* que contiene «aba» como una substring

Dada una string binaria S, la tarea es escribir un programa para DFA Machine que acepte un conjunto de todas las strings sobre w ∈ (a, b) * que contenga «aba» como una substring.
Ejemplos:
 

Input-1 : ababa
Output : Accepted
Explanation : "ababa" consists "aba"

Input-2 : abbbb
Output : Not accepted
Explanation : "abbbb" does not consist "aba"

Enfoque: a continuación se muestra la máquina DFA diseñada para el problema dado. Construya una tabla de transición para los estados de DFA y analice las transiciones entre cada estado. A continuación se muestran los pasos:
 

Idioma deseado: 
 

L = {aba, baba, abab, aababbb.....}

Explicación : 
 

  1. En primer lugar, habrá 4 estados (digamos q 0 , q 1 , q 2 , q 3 ), siendo q 0 el estado inicial y q 3 el estado final.
  2. Inicialmente estaremos en el estado q 0 , ahora comenzamos a leer la string dada.
  • Cuando leamos ‘b’, permaneceremos en el mismo estado
  • Si leemos ‘a’, entonces transita al estado q 1 .

3. Suponiendo que ahora estamos en q 1 estado. 
 

  • Cuando leamos ‘a’, permaneceremos en el mismo estado.
  • Si leemos ‘b’, transitaremos al estado q 2 .

4. Suponiendo que ahora estamos en el estado q 2
 

  • Si leemos ‘a’, pasa al estado q 3 .
  • Si leemos ‘b’, se pasa al estado q 0.

5. Suponiendo que estamos en el estado final (q 3
 

  • Permanecemos en el mismo estado, cuando leemos ‘a’ o ‘b’.

6. Todas las strings aceptadas por este DFA tendrán «aba» como su substring.
Tabla de transición: 
 

Estado actual estado final
a b
q0 q1 q0
q1 q1 q2
q2 q3 q0
q3 q3 q3

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program for the above approach
#include <cstring>
#include <iostream>
using namespace std;
 
// Function to check whether the given
// string is accepted by DFA or not
void checkValidDFA(string s)
{
    // Stores initial state of DFA
    int initial_state = 0;
    // Stores previous state of DFA
    int previous_state = initial_state;
    // Stores final state of DFA
    int final_state;
    // Iterate through the string
    for (int i = 0; i < s.length(); i++) {
        // Checking for all combinations
        if ((previous_state == 0 && s[i] == 'a') ||
        (previous_state == 1 && s[i] == 'a')) {
            final_state = 1;
        }
        if ((previous_state == 0 && s[i] == 'b') ||
        (previous_state == 2 && s[i] == 'b')) {
            final_state = 0;
        }
        if (previous_state == 1 && s[i] == 'b') {
            final_state = 2;
        }
        if ((previous_state == 2 && s[i] == 'a') ||
        (previous_state == 3)) {
            final_state = 3;
        }
        // Update the previous_state
        previous_state = final_state;
    }
    // If final state is reached
    if (final_state == 3) {
        cout << "Accepted" << endl;
    }
    // Otherwise
    else {
        cout << "Not Accepted" << endl;
    }
}
 
// Driver Code
int main()
{
    // Given string
    string s = "ababa";
    // Function Call
    checkValidDFA(s);
}

C

// C++ program for the above approach
#include <stdio.h>
#include <string.h>
   
// Function to check whether the given
// string is accepted by DFA or not
void checkValidDFA(char s[] )
{
    // Stores initial state of DFA
    int initial_state = 0;
    // Stores previous state of DFA
    int previous_state = initial_state;
    // Stores final state of DFA
    int final_state;
    // Iterate through the string
    for(int i = 0; i < strlen(s); i++)
    {
      // Checking for all combinations    
      if((previous_state == 0 && s[i] == 'a') ||
      (previous_state == 1 && s[i] == 'a'))
      {
          final_state = 1;
      }
      if((previous_state == 0 && s[i] == 'b') ||
      (previous_state == 2 && s[i] == 'b'))
      {
          final_state = 0;
      }
      if(previous_state == 1 && s[i] == 'b')
      {
          final_state = 2;
      }
      if((previous_state == 2 && s[i] == 'a') ||
      (previous_state == 3))
      {
          final_state = 3;
      }
        // Update the previous_state
        previous_state = final_state;
    }
    // If final state is reached
    if(final_state == 3)
    {
        printf("Accepted");
    }
    // Otherwise
    else
    {
        printf("Not Accepted");
    }
}
 
// Driver Code
int main()
{
    // Given string
    char s[] = "ababa";
     
    // Function Call
    checkValidDFA(s);
}
Producción : 

Accepted

Complejidad de Tiempo : O(N) 
Espacio Auxiliar : O(1)
 

Publicación traducida automáticamente

Artículo escrito por pravallika26 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 *