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 :
- 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.
- 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); }
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