Thực hiện một mã số để mô phỏng một automaton hữu hạn không xác định trong C++

Question

tôi đang làm một bài tập cho lý thuyết automata, mà tôi phải xác định xem một từ được chấp nhận hay không bằng một chức năng chuyển tiếp cho một automaton hữu hạn xác định

tôi có tập tin đầu vào này:

6 8 0 2 
2 
5 
0 0 a 
0 1 a 
1 1 b 
1 2 c 
1 3 c 
3 4 d 
4 4 d 
4 5 d 
3 
aaabcccc 
aabbbbcdc 
acdddddd 

các đầu vào bắt đầu với 4 số nguyên, là người đầu tiên là số của nhà nước cho các automaton, bên cạnh là số hiệu ứng chuyển tiếp của automaton, số thứ ba là tình trạng ban đầu, và sau đó số trạng thái cuối cùng. sau đó đến các trạng thái cuối cùng (trong ví dụ các trạng thái cuối cùng là 2 và 5). Sau đó đến N dòng (N là số lần chuyển tiếp), mỗi dòng có 2 số nguyên và một ký tự, I, J và C, đại diện cho các trạng thái mà quá trình chuyển đổi, tức là chuyển tiếp đi từ trạng thái i sang trạng thái J với ký tự C. Theo sau dòng này đi kèm với một số nguyên S, sẽ chứa số chuỗi để kiểm tra, sau đó S dòng với các chuỗi tương ứng.

Kết quả của chương trình này sẽ là:

Case #2: 
aaabcccc Rejected 
aabbbbcdc Rejected 
acdddddd Accepted 

Nó nên nói nếu String được chấp nhận hay từ chối. Cho đến nay, tôi đã chỉ mã hóa công việc với đầu vào.

Tôi không biết cách thuận tiện nhất để đại diện cho ô tô. Tôi có nên sử dụng mảng đơn giản không? Tôi sẽ áp dụng logic nào cho các mảng ?. Có cách nào để làm điều đó mà không biết trước bảng chữ cái automaton? Tôi có cần cấu trúc dữ liệu để đại diện cho automata không ?. Tôi là một chút khó khăn với nhiệm vụ này, và muốn một số ý tưởng, một số giả hoặc ý tưởng để làm điều đó. Mã có phải là ngôn ngữ khác không? Tôi không muốn các giải pháp, bởi vì tôi muốn làm nhiệm vụ của tôi, nhưng nếu tôi có thể sử dụng một số giúp đỡ

Answer 1

Tôi nghĩ rằng bạn có thể có một bản đồ tr cho chuyển nơi tr[(i, c)] = j nếu có chuyển đổi từ i nhà nước để j nhà nước qua c, một mảng cho các trạng thái cuối cùng là fs[m] trong đó m là số trạng thái cuối cùng và số nguyên cho trạng thái ban đầu s0.

Bellow là một khung của một lớp với các thuộc tính như:

class Automata 
{ 
public: 
    Automata(int start) : s0(start) 
    {} 

    void add_transition(int i, int j, char c) { 
     //... 
    } 

    void add_final_state(int i) { 
     //... 
    } 

    bool validate_string(const std::string& str) { 
     //... 
    } 
private: 
    std::map<std::pair<int, char>, int> tr; // transitions 
    std::vector<int> fs; // final states 
    int s0; // initial state 
};