Mô phỏng NFA (Automat hữu hạn không xác định) trong C

Chương trình C mô phỏng NFA (Nondeterministic Finite Automata). NFA cho phép từ 1 trạng thái với 1 ký tự đầu vào chuyển đến nhiều trạng thái khác nhau.

Định nghĩa NFA

5-tuple (Q, Σ, δ, q₀, F):

• Q: tập trạng thái hữu hạn
• Σ: bảng chữ cái (ký tự đầu vào)
• δ: hàm chuyển trạng thái Q × Σ → 2^Q (tập con của Q)
• q₀: trạng thái bắt đầu
• F: tập trạng thái chấp nhận

Đồ thị NFA mẫu

4 trạng thái, bắt đầu=1, chấp nhận=4. Cạnh nhãn 0/1.

Kiểm tra chuỗi "01001" có được chấp nhận không

Duyệt tất cả đường đi có thể (backtracking). Nếu có đường đến trạng thái 4 sau khi hết chuỗi → chấp nhận.

Chương trình mẫu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

struct Node {
    int data;
    struct Node* next;
    char edgeType;
};

struct Node* push(struct Node* first, char edgeType, int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->edgeType = edgeType;
    newNode->data = data;
    newNode->next = first;
    return newNode;
}

int nfa(struct Node** graph, int current, char* input, int* accept, int pos) {
    if (pos == strlen(input))
        return accept[current];
    
    struct Node* temp = graph[current];
    while (temp) {
        if (input[pos] == temp->edgeType) {
            if (nfa(graph, temp->data, input, accept, pos+1))
                return 1;
        }
        temp = temp->next;
    }
    return 0;
}

int main() {
    int n; scanf("%d", &n);
    struct Node* graph[n+1];
    int accept[n+1];
    for (int i=0; i<=n; i++) graph[i] = NULL;
    
    for (int i=0; i

Đầu vào/ra mẫu
Input:
4
1 0 4 0 1 0 2 1 1 1 3
2 0 1 0 4
3 0 1 1 4
4 1 2 0 4 1 4
101101

Output:
00 11 000 001 011 100 110 111 0000 0001


Chương trình in ra 10 chuỗi nhị phân đầu tiên được NFA chấp nhận.