Dada una string S , la tarea es diseñar un autómata finito determinista (DFA) para aceptar el lenguaje L = C (A + B)+ . Si DFA acepta la string proporcionada, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = “CABABABAB”
Salida: Sí
Explicación: La string dada tiene la forma C(A + B)+ ya que el primer carácter es C y es seguido por A o B.Entrada: S = “ABAB”
Salida: No
Enfoque: La idea es interpretar el lenguaje dado L = C (A + B)+ y para la expresión regular de la forma C(A + B)+, el siguiente es el Diagrama de Transición de Estado DFA :
Siga los pasos a continuación para resolver el problema:
- Si la string dada tiene una longitud menor que igual a 1 , imprima «No» .
- Si el primer carácter siempre es C , recorra la string restante y verifique si alguno de los caracteres es A o B .
- Si existe algún carácter que no sea A o B mientras se desplaza en el paso anterior, imprima «No» .
- De lo contrario, escriba «Sí» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find whether the given // string is Accepted by the DFA void DFA(string str, int N) { // If n <= 1, then print No if (N <= 1) { cout << "No"; return; } // To count the matched characters int count = 0; // Check if the first character is C if (str[0] == 'C') { count++; // Traverse the rest of string for (int i = 1; i < N; i++) { // If character is A or B, // increment count by 1 if (str[i] == 'A' || str[i] == 'B') count++; else break; } } else { // If the first character // is not C, print -1 cout << "No"; return; } // If all characters matches if (count == N) cout << "Yes"; else cout << "No"; } // Driver Code int main() { string str = "CAABBAAB"; int N = str.size(); DFA(str, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find whether the given // String is Accepted by the DFA static void DFA(String str, int N) { // If n <= 1, then print No if (N <= 1) { System.out.print("No"); return; } // To count the matched characters int count = 0; // Check if the first character is C if (str.charAt(0) == 'C') { count++; // Traverse the rest of String for (int i = 1; i < N; i++) { // If character is A or B, // increment count by 1 if (str.charAt(i) == 'A' || str.charAt(i) == 'B') count++; else break; } } else { // If the first character // is not C, print -1 System.out.print("No"); return; } // If all characters matches if (count == N) System.out.print("Yes"); else System.out.print("No"); } // Driver Code public static void main(String[] args) { String str = "CAABBAAB"; int N = str.length(); DFA(str, N); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find whether the given # is Accepted by the DFA def DFA(str, N): # If n <= 1, then print No if (N <= 1): print("No") return # To count the matched characters count = 0 # Check if the first character is C if (str[0] == 'C'): count += 1 # Traverse the rest of string for i in range(1, N): # If character is A or B, # increment count by 1 if (str[i] == 'A' or str[i] == 'B'): count += 1 else: break else: # If the first character # is not C, print -1 print("No") return # If all characters matches if (count == N): print("Yes") else: print("No") # Driver Code if __name__ == '__main__': str = "CAABBAAB" N = len(str) DFA(str, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; class GFG { // Function to find whether the given // String is Accepted by the DFA static void DFA(string str, int N) { // If n <= 1, then print No if (N <= 1) { Console.Write("No"); return; } // To count the matched characters int count = 0; // Check if the first character is C if (str[0] == 'C') { count++; // Traverse the rest of String for (int i = 1; i < N; i++) { // If character is A or B, // increment count by 1 if (str[i] == 'A' || str[i] == 'B') count++; else break; } } else { // If the first character // is not C, print -1 Console.Write("No"); return; } // If all characters matches if (count == N) Console.Write("Yes"); else Console.Write("No"); } // Driver Code static public void Main() { string str = "CAABBAAB"; int N = str.Length; DFA(str, N); } } // This code is contributed by Dharanendra L V
Javascript
<script> // Javascript program for the above approach // Function to find whether the given // String is Accepted by the DFA function DFA(str,N) { // If n <= 1, then print No if (N <= 1) { document.write("No"); return; } // To count the matched characters let count = 0; // Check if the first character is C if (str[0] == 'C') { count++; // Traverse the rest of String for (let i = 1; i < N; i++) { // If character is A or B, // increment count by 1 if (str[i] == 'A' || str[i] == 'B') count++; else break; } } else { // If the first character // is not C, print -1 document.write("No"); return; } // If all characters matches if (count == N) document.write("Yes"); else document.write("No"); } // Driver Code let str = "CAABBAAB"; let N = str.length; DFA(str, N); // This code is contributed by patel2127 </script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kushwahp1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA