Programme pour construire un DFA de l'expression régulière C( A + B)

Dans cet article, nous verrons comment construire un automate fini déterministe (DFA) pour l'expression régulière C(A + B)+ en utilisant C++. Nous commencerons par comprendre le problème et la théorie qui le sous-tend, puis nous plongerons dans la mise en œuvre et enfin démontrerons son utilisation avec des exemples pertinents.

Comprendre l'énoncé du problème

Deterministic Finite Automata (DFA) est un modèle théorique de calcul utilisé dans la théorie des automates, une branche de l'informatique théorique. C’est l’un des types d’automates les plus simples et un concept fondamental dans l’étude des compilateurs et des analyseurs.

La tâche ici est d'écrire un DFA pour l'expression régulière C(A + B)+. Cette expression peut être interprétée comme « C » suivi d'une ou plusieurs occurrences de « A » ou « B ». Notre objectif est de créer un programme C++ qui vérifie si une chaîne d'entrée donnée correspond à cette expression régulière.

Contexte théorique

Un DFA se compose d'un ensemble d'états et de transitions entre ces états sur les symboles d'entrée. Il part de l'état initial et lit les symboles d'entrée. Pour chaque symbole d'entrée, il passe à un nouvel état jusqu'à ce que tous les symboles d'entrée aient été lus. Un DFA accepte une entrée si et seulement si l'entrée se termine dans un état final (ou accepté).

Dans ce cas, le DFA de l'expression régulière C(A + B)+ peut être visualisé comme suit -

• Statut de démarrage : q0

• Accepter le statut : q2

• Convertir -

• Entrez q0 sur "C" pour accéder à q1

• Q1 passe à q2 lors de la saisie de "A" ou "B"

• Entrez q2 sur "A" ou "B" pour rester en q2

Exemple

Implémentons maintenant ce DFA en C++. Veuillez noter que ce programme ne fonctionne qu'avec les majuscules "A", "B" et "C".

#include <iostream>
#include <string>
using namespace std;

enum State { q0, q1, q2, q3 };

State getNextState(State currentState, char input) {
   switch (currentState) {
      case q0: return (input == 'C') ? q1 : q3;
      case q1: return (input == 'A' || input == 'B') ? q2 : q3;
      case q2: return (input == 'A' || input == 'B') ? q2 : q3;
      default: return q3;
   }
}

bool matchesRE(string s) {
   State currentState = q0;
   for (char c : s) {
      currentState = getNextState(currentState, c);
   }
   return currentState == q2;
}

int main() {
   string test = "CABAB";
   cout << (matchesRE(test) ? "Matches Regular Expression" : "Does not match Regular Expression") << endl;
   return 0;
}

Sortie

Matches Regular Expression

Cas de test

Prenons la chaîne « CABAB » comme exemple. La chaîne commence par « C », suivi d'une série de « A » et de « B ». Par conséquent, il correspond à l'expression régulière C(A + B)+ et le résultat du programme sera : "correspond à l'expression régulière".

Conclusion

Dans cet article, nous examinons de plus près le modèle théorique informatique DFA et son application dans la validation des expressions régulières. Nous nous sommes concentrés sur l'expression régulière C(A + B)+ et avons créé un programme C++ pour vérifier si une chaîne d'entrée correspond à cette expression régulière. Nous espérons que cette discussion vous a été instructive et vous a aidé à mieux comprendre DFA et sa mise en œuvre en C++.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!