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', chuỗi này phải bắt đầu và kết thúc bằng ký tự 'a'. Nhiệm vụ là xác định xem chuỗi có bắt đầu và kết thúc bằng 'a' thông qua DFA hay không.

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

Trong lý thuyết tính toán, một nhánh của khoa học máy tính lý thuyết, Tự động 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. "Xác định" đề cập đến tính duy nhất của phép tính để chạy.

Để tìm chuỗi bằng 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à ta 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 ta có thể dễ dàng kiểm tra ký tự đầu tiên và cuối cùng của chuỗi/chuỗi ký tự cho trước.

Ví dụ

Đầu vào: a b b a 
Đầu ra: yes 
Giải thích: Chuỗi đầu vào bắt đầu và kết thúc bằng 'a'

Đầu vào: a a a b a b 
Đầu ra: no

Cách tiếp cận để giải bài toán trên –

Ta sẽ xây dựng một DFA cho bài toán nêu trên và sau đó giải quyết vấn đề theo DFA vừa tạo.

dfa.jpg

Thuật toán

Bắt đầu
Bước 1 -> Trong main()
    Gọi hàm srand(time(0)) để tạo số ngẫu nhiên
    Khai báo biến int max = 1 + rand() % 15
    Khai báo và gán int i = 0
    Khi (i < max)
        Khai báo char data = 'a' + rand() % 2
        In data
        Tăng i
        NẾU data = 'a'
            NẾU (i = max)
                In "YES"
            Kết thúc
            Vòng lặp Khi (i < max)
                Gán data = 'a' + rand() % 2
                In data
                Tăng i
                NẾU (data = 'a' VÀ i = max)
                    In YES
                Kết thúc
                NGƯỢC LẠI NẾU (i = max)
                    In NO
                Kết thúc
            Kết thúc
        Kết thúc
        NGƯỢC LẠI
            Vòng lặp Khi (i < max)
                Gán data = 'a' + rand() % 2
                In data
                Tăng i
            Kết thúc
            In NO
        Kết thúc
    Kết thúc
Kết thúc

Ví dụ mã C++

#include <iostream>
#include <time.h>
using namespace std;

int main() {
    // để tạo số ngẫu nhiên
    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