Programm zum Erstellen eines DFA des regulären Ausdrucks C( A + B)

In diesem Artikel besprechen wir, wie man mit C++ einen deterministischen endlichen Automaten (DFA) für den regulären Ausdruck C(A + B)+ konstruiert. Wir beginnen damit, das Problem und die Theorie dahinter zu verstehen, gehen dann auf die Umsetzung ein und demonstrieren schließlich die Verwendung anhand relevanter Beispiele.

Die Problemstellung verstehen

Deterministische endliche Automaten (DFA) sind ein theoretisches Berechnungsmodell, das in der Automatentheorie, einem Zweig der theoretischen Informatik, verwendet wird. Es ist einer der einfachsten Automatentypen und ein grundlegendes Konzept beim Studium von Compilern und Parsern.

Die Aufgabe besteht hier darin, einen DFA für den regulären Ausdruck C(A + B)+ zu schreiben. Dieser Ausdruck kann als „C“ gefolgt von einem oder mehreren Vorkommen von „A“ oder „B“ interpretiert werden. Unser Ziel ist es, ein C++-Programm zu erstellen, das prüft, ob eine bestimmte Eingabezeichenfolge mit diesem regulären Ausdruck übereinstimmt.

Theoretischer Hintergrund

Ein DFA besteht aus einer Reihe von Zuständen und Übergängen zwischen diesen Zuständen auf Eingabesymbolen. Es beginnt im Ausgangszustand und liest die Eingabesymbole. Für jedes Eingabesymbol wechselt es in einen neuen Zustand, bis alle Eingabesymbole gelesen wurden. Ein DFA akzeptiert eine Eingabe genau dann, wenn die Eingabe in einem endgültigen (oder akzeptierten) Zustand endet.

In diesem Fall kann der DFA des regulären Ausdrucks C(A + B)+ wie folgt visualisiert werden -

• Startstatus: q0

• Akzeptanzstatus: q2

• Konvertieren -

• Geben Sie q0 auf „C“ ein, um zu q1 zu gelangen

• Q1 geht zu q2, wenn „A“ oder „B“ eingegeben wird

• Geben Sie q2 auf „A“ oder „B“ ein, um bei q2 zu bleiben

Beispiel

Jetzt implementieren wir diesen DFA in C++. Bitte beachten Sie, dass dieses Programm nur mit den Großbuchstaben „A“, „B“ und „C“ funktioniert.

#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;
}

Ausgabe

Matches Regular Expression

Testfälle

Nehmen wir als Beispiel die Zeichenfolge „CABAB“. Die Zeichenfolge beginnt mit „C“, gefolgt von einer Reihe von „A“ und „B“. Daher stimmt es mit dem regulären Ausdruck C(A + B)+ überein und die Ausgabe des Programms lautet: „entspricht regulärem Ausdruck“.

Fazit

In diesem Artikel werfen wir einen genaueren Blick auf das rechnerische theoretische Modell DFA und seine Anwendung bei der Validierung regulärer Ausdrücke. Wir haben uns auf den regulären Ausdruck C(A + B)+ konzentriert und ein C++-Programm erstellt, um zu prüfen, ob eine Eingabezeichenfolge mit diesem regulären Ausdruck übereinstimmt. Wir hoffen, dass diese Diskussion informativ war und Ihnen geholfen hat, DFA und seine Implementierung in C++ besser zu verstehen.

Das obige ist der detaillierte Inhalt vonProgramm zum Erstellen eines DFA des regulären Ausdrucks C( A + B). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!