โปรแกรมสร้าง DFA ที่ขึ้นต้นและลงท้ายด้วย 'a' จากอินพุต (a, b) ใน C++

กำหนดสตริงของอักขระ DFA คือ "a" และ "b" ซึ่งควรขึ้นต้นและลงท้ายด้วยอักขระ 'a' ภารกิจคือการค้นหาว่าสตริงนั้นขึ้นต้นและลงท้ายด้วย 'a' ผ่าน DFA หรือไม่

DFA (Deterministic Finite Automata) คืออะไร

ในทฤษฎีการคำนวณ ซึ่งเป็นสาขาหนึ่งของวิทยาการคอมพิวเตอร์เชิงทฤษฎี Deterministic Finite Automata เป็นเครื่องจักรสถานะจำกัดที่รับหรือปฏิเสธสตริงของสัญลักษณ์ Deterministic หมายถึงเอกลักษณ์ของการคำนวณที่จะรัน

สำหรับการค้นหาสตริงโดย DFA และสตริงควรเริ่มต้นและลงท้ายด้วย 'a' จากอินพุต (a, b) เนื่องจากไม่มีแนวคิดเกี่ยวกับหน่วยความจำและเราสามารถเก็บได้เฉพาะอักขระปัจจุบัน DFA จึงไม่สามารถจัดเก็บสตริงที่จัดเตรียมไว้ได้ มิฉะนั้น เราสามารถตรวจสอบอักขระตัวแรกและตัวสุดท้ายของลำดับ/สตริงที่มอบให้เราได้อย่างง่ายดาย

ตัวอย่าง

Input: a b b a
Output: yes
Explanation: The input string starts and ends with ‘a’

Input: a a a b a b
Output: no

แนวทางที่เรากำลังติดตามเพื่อแก้ปัญหาข้างต้น -

ดังนั้น เราจะสร้าง DFA สำหรับปัญหาที่ระบุไว้ข้างต้น จากนั้นจะแก้ปัญหาตาม DFA ที่เราสร้างขึ้น

dfa.jpg

อัลกอริทึม

Start
Step 1-> In main()
   Call function srand(time(0)) to generate random numbers
   Declare variable as int max = 1 + rand() % 15
   Declare and set int i = 0
   While(i < max)
      Declare char data = 'a' + rand() % 2
      Print data
      Increment i
      IF data = 'a'
         IF(i = max)
            Print "YES"
         End
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
            If (data = 'a' AND i = max)
               Print YES\n
            End
            Else IF(i = max)
               Print NO
            End
         End
      End
      Else
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
         End
         Print NO
      End
   End
Stop

ตัวอย่าง

#include <iostream>
#include <time.h>
using namespace std;
int main() {
   // for generating random numbers
   srand(time(0));
   int max = 1 + rand() % 15;
   int i = 0;
   while (i < max) {
      char data = 'a' + rand() % 2;
      cout << data << " ";
      i++;
      if (data == 'a') {
         if (i == max)
            cout << "YES\n";
         while (i < max) {
            data = 'a' + rand() % 2;
            cout << data << " ";
            i++;
            if (data == 'a' && i == max) {
               cout << "\nYES\n";
            } else if (i == max) {
               cout << "\nNO\n";
            }
         }
      } else {
         while (i < max) {
            data = 'a' + rand() % 2;
            cout << data << " ";
            i++;
         }
         cout << "\nNO\n";
      }
   }
   return 0;
}

ผลลัพธ์

b b a b a b a b b b b b
NO