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

โจทย์

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

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

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

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

ตัวอย่าง

Input: a b b a Output: yes Explanation: สตริงอินพุตเริ่มและจบด้วย 'a'
Input: a a a b a b Output: no

แนวทางแก้ปัญหา

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

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ใน main()
  เรียกฟังก์ชัน srand(time(0)) เพื่อสร้างตัวเลขสุ่ม
  ประกาศตัวแปร int max = 1 + rand() % 15
  ประกาศและตั้งค่า int i = 0
  เมื่อ (i < max)
    ประกาศ char data = 'a' + rand() % 2
    พิมพ์ data
    เพิ่ม i
    ถ้า data = 'a'
      ถ้า (i == max)
        พิมพ์ "YES"
      จบถ้า
      วนลูป While (i < max)
        ตั้งค่า data = 'a' + rand() % 2
        พิมพ์ data
        เพิ่ม i
        ถ้า (data = 'a' และ i = max)
          พิมพ์ YES
        จบถ้า
        มิฉะนั้น ถ้า (i = max)
          พิมพ์ NO
        จบมิฉะนั้น
      จบวน
    จบถ้า
    มิฉะนั้น
      วนลูป While (i < max)
        ตั้งค่า data = 'a' + rand() % 2
        พิมพ์ data
        เพิ่ม i
      จบวน
      พิมพ์ NO
    จบมิฉะนั้น
  จบเมื่อ
หยุด

ตัวอย่างโค้ด C++

#include <iostream>
#include <time.h>
using namespace std;
int main() {
  // สำหรับสร้างตัวเลขสุ่ม
  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