Program untuk membina DFA bagi ungkapan biasa C( A + B)

Dalam artikel ini, kita akan membincangkan cara membina automaton terhingga deterministik (DFA) untuk ungkapan biasa C(A + B)+ menggunakan C++. Kami akan bermula dengan memahami masalah dan teori di sebaliknya, kemudian menyelami pelaksanaan, dan akhirnya menunjukkan penggunaannya dengan contoh yang berkaitan.

Memahami penyataan masalah

Deterministic Finite Automata (DFA) ialah model pengiraan teori yang digunakan dalam teori automata, cabang sains komputer teori. Ia adalah salah satu jenis automata yang paling mudah dan konsep asas dalam kajian penyusun dan penghurai.

Tugas di sini ialah menulis DFA untuk ungkapan biasa C(A + B)+. Ungkapan ini boleh ditafsirkan sebagai "C" diikuti dengan satu atau lebih kejadian "A" atau "B". Matlamat kami adalah untuk mencipta program C++ yang menyemak sama ada rentetan input yang diberikan sepadan dengan ungkapan biasa ini.

Latar belakang teori

DFA terdiri daripada satu set keadaan dan peralihan antara keadaan ini pada simbol input. Ia bermula dari keadaan awal dan membaca simbol input. Untuk setiap simbol input, ia beralih kepada keadaan baharu sehingga semua simbol input telah dibaca. DFA menerima input jika dan hanya jika input berakhir dalam keadaan muktamad (atau diterima).

Dalam kes ini, DFA bagi ungkapan biasa C(A + B)+ boleh digambarkan seperti berikut -

• Status mula: q0

• Terima status: q2

• Tukar -

• Masukkan q0 pada "C" untuk pergi ke q1

• Q1 pergi ke q2 apabila memasukkan "A" atau "B"

• Masukkan q2 pada "A" atau "B" untuk kekal di q2

Contoh

Sekarang mari kita laksanakan DFA ini dalam C++. Sila ambil perhatian bahawa program ini hanya berfungsi dengan huruf besar "A", "B" dan "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;
}

Output

Matches Regular Expression

Kes Ujian

Mari kita ambil rentetan "CABAB" sebagai contoh. Rentetan bermula dengan "C", diikuti dengan siri "A" dan "B". Oleh itu, ia sepadan dengan ungkapan biasa C(A + B)+ dan output program ialah: "padanan dengan ungkapan biasa".

Kesimpulan

Dalam artikel ini, kami melihat dengan lebih dekat model teori pengiraan DFA dan aplikasinya dalam mengesahkan ungkapan biasa. Kami menumpukan pada ungkapan biasa C(A + B)+ dan mencipta program C++ untuk menyemak sama ada rentetan input sepadan dengan ungkapan biasa ini. Kami berharap perbincangan ini bermaklumat dan membantu anda lebih memahami DFA dan pelaksanaannya dalam C++.

Atas ialah kandungan terperinci Program untuk membina DFA bagi ungkapan biasa C( A + B). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!