Chương trình xây dựng DFA bắt đầu và kết thúc bằng ‘a’ từ đầu vào (a, b) trong C ++

Cho một chuỗi DFA gồm các ký tự ‘a’ và ‘b’, sẽ bắt đầu và kết thúc bằng ký tự ‘a’, nhiệm vụ là tìm xem chuỗi bắt đầu và kết thúc bằng ‘a’ có thông qua một DFA hay không.

DFA (Dữ liệu tự động hữu hạn xác định) là gì?

Về lý thuyết tính toán, một nhánh của khoa học máy tính lý thuyết, Automata hữu hạn xác định là một máy trạng thái hữu hạn chấp nhận hoặc từ chối các chuỗi ký hiệu. Tính xác định đề cập đến tính duy nhất của phép tính sẽ chạy.

Để tìm chuỗi theo DFA và chuỗi phải bắt đầu và kết thúc bằng ‘a’ từ đầu vào (a, b). Vì không có khái niệm bộ nhớ và chúng tôi chỉ có thể lưu trữ ký tự hiện tại, DFA không thể lưu trữ chuỗi được cung cấp, nếu không, chúng tôi có thể dễ dàng kiểm tra ký tự đầu tiên và ký tự cuối cùng của chuỗi / chuỗi được cung cấp cho chúng tôi.

Ví dụ

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

Phương pháp tiếp cận mà chúng tôi đang theo dõi để giải quyết vấn đề trên -

Vì vậy, chúng tôi sẽ tạo một DFA cho vấn đề đã nêu ở trên và sau đó sẽ giải quyết vấn đề theo DFA mà chúng tôi tạo ra.

dfa.jpg

Thuật toán

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

Ví dụ

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

Đầu ra

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