โปรแกรม C จำลองออโตมาต้าสิ้นสุดแบบไม่เชิง xác định (NFA)

ในปัญหานี้ เราจะสร้างโปรแกรม C เพื่อจำลองออโตมาต้าสิ้นสุดแบบไม่เชิง xác định (NFA)

NFA (Non-deterministic Finite Automata) คือเครื่องจักรสถานะจำกัดที่สามารถเคลื่อนย้ายไปยังการรวมกันใดๆ ของสถานะสำหรับสัญลักษณ์อินพุต นั่นคือ ไม่มีสถานะที่แน่นอนว่าจะเคลื่อนย้ายไป

นิยามทางการของ NDFA —

NFA / NDFA สามารถแสดงด้วย 5-tuple (Q, Σ, δ, q0, F) โดยที่ —

• Q เป็นเซตจำกัดของสถานะ
• Σ เป็นเซตจำกัดของสัญลักษณ์ที่เรียกว่าอักขระ
• δ คือฟังก์ชันการเปลี่ยนสถานะ โดยที่ δ: Q × Σ → 2^Q (ที่นี่ใช้ชุดกำลังของ Q (2^Q) เพราะในกรณีของ NDFA จากสถานะหนึ่ง การเปลี่ยนสถานะอาจเกิดขึ้นไปยังการรวมกันใดๆ ของสถานะ Q)
• q0 คือสถานะเริ่มต้นที่ประมวลผลอินพุตใดๆ (q0 ∈ Q)
• F เป็นเซตของสถานะสุดท้าย/สถานะยอมรับของ Q (F ⊆ Q)

ในการเขียนโปรแกรม NFA ถูกสร้างโดยใช้กราฟมีทิศทาง แต่ละโหนดของกราฟแสดงสถานะของ NDA เส้นขอบของกราฟสามารถมีค่าเป็น 0 หรือ 1 เส้นขอบที่ติดฉลาก 0 แสดงการเปลี่ยนสถานะที่ไม่ยอมรับ ในขณะที่เส้นขอบที่ติดฉลาก 1 แสดงการเปลี่ยนสถานะที่ยอมรับ

มีจุดเข้าของกราฟโดยทั่วไปเป็นโหนด 1 ที่รับสตริงอินพุตซึ่งเป็นอาร์เรย์ไบนารีความยาวจำกัด

ลองดูรูปแบบกราฟของ NFA แล้วแก้ไวยากรณ์โดยใช้มัน

สถานะเริ่มต้น -> 1

สถานะสุดท้าย (สถานะยอมรับ) -> 4

ลองตรวจสอบว่าสตริง 01001 ถูกยอมรับหรือไม่

สถานะเริ่มต้น 1, อินพุต 0, ด้วย 0 เราสามารถไปสถานะ 4 หรือวนกลับสถานะ 1 เอง

เราพิจารณาทั้งสองกรณี —

{1->1} 1001 {1->4} 1001

สถานะ 1/4, อินพุต 1 —

จากสถานะ 1 สามารถไป 2 หรือวนกลับ, จากสถานะ 4 ไม่สามารถไปต่อได้ จึงตัดกรณีนี้ทิ้ง

พิจารณากรณีจาก 1 —

{1->1->1} 001 {1->1->2} 001

สถานะ 1/2, อินพุต 0 —

จากสถานะ 1 ไป 4 หรือวนกลับ, จากสถานะ 2 ไป 4 หรือวนกลับ

พิจารณาทุกกรณี —

{1->1->1->1} 01 {1->1->1->4} 01 {1->1->2->1} 01 {1->1->2->4} 01

สถานะ 1/2/4, อินพุต 0 —

จากสถานะ 1 ไป 4 หรือวนกลับ, จากสถานะ 2 ไป 4 หรือวนกลับ, จากสถานะ 4 ไป 3 หรือวนกลับ

พิจารณาทุกกรณี —

{1->1->1->1->1} 1 {1->1->1->1->4} 1 {1->1->1->4->3} 1 {1->1->1->4->4} 1 {1->1->2->1->1} 1 {1->1->2->1->4} 1 {1->1->2->4->3} 1 {1->1->2->4->4} 1

สถานะ 1/2/3/4, อินพุต 1 —

จากสถานะ 1 ไป 2 หรือวนกลับ, จากสถานะ 2 ไป 3, จากสถานะ 3 ไป 4, จากสถานะ 4 ไม่สามารถไปต่อได้

พิจารณาทุกกรณี —

{1->1->1->1->1->1/2} ไม่ถึงสถานะสุดท้าย
{1->1->1->1->4} 1 ไม่รับอินพุต
{1->1->1->4->3->4} ยอมรับอินพุต
{1->1->1->4->4} ไม่รับอินพุต
{1->1->2->1->1->1/2} ไม่ถึงสถานะสุดท้าย
{1->1->2->1->4} ไม่รับอินพุต
{1->1->2->4->3->4} ยอมรับอินพุต
{1->1->2->4->4} ไม่รับอินพุต

ดังนั้น มีทางไปถึงสถานะสุดท้ายด้วยสตริงอินพุตที่กำหนด

ตอนนี้ มาดูโปรแกรม C จำลอง NFA —

อินพุตของโปรแกรมจะเป็นรายการติดกันของ NFA —

จำนวนเส้นขอบ (n)

การเชื่อมต่อเส้นขอบ (n บรรทัด)

สตริงที่ต้องตรวจสอบ

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

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

int row = 0;

struct node {
    int data;
    struct node* next;
    char edgetype;
} typedef node;

// เพิ่มเส้นขอบในรายการติดกัน
node* push(node* first, char edgetype, int data) {
    node* new_node = (node*)malloc(sizeof(node));
    new_node->edgetype = edgetype;
    new_node->data = data;
    new_node->next = NULL;
    if (first == NULL) {
        first = new_node;
        return new_node;
    }
    first->next = push(first->next, edgetype, data);
    return first;
}

// ฟังก์ชันเรียกซ้ำตรวจสอบการยอมรับอินพุต
int nfa(node** graph, int current, char* input, int* accept, int start) {
    if (start == (int)strlen(input))
        return accept[current];
    node* temp = graph[current];
    while (temp != NULL) {
        if (input[start] == temp->edgetype) {
            if (nfa(graph, temp->data, input, accept, start + 1) == 1) {
                return 1;
            }
        }
        temp = temp->next;
    }
    return 0;
}

// ฟังก์ชันสร้างสตริงไบนารีขนาด n
void generate(char** arr, int size, char* a) {
    if (size == 0) {
        strcpy(arr[row], a);
        row++;
        return;
    }
    char b0[20] = {'\0'};
    char b1[20] = {'\0'};
    b0[0] = '0';
    b1[0] = '1';
    generate((char**)arr, size - 1, strcat(b0, a)); // เพิ่ม 0 หน้า
    generate((char**)arr, size - 1, strcat(b1, a)); // เพิ่ม 1 หน้า
    return;
}

int main() {
    int n;
    int i, j;
    scanf("%d", &n); // จำนวนโหนด
    node* graph[n + 1]; // สร้างกราฟ
    for (i = 0; i < n + 1; i++)
        graph[i] = NULL;
    int accept[n + 1]; // อาร์เรย์เก็บสถานะของโหนด
    for (i = 0; i < n; i++) {
        // ดัชนีโหนด, สถานะยอมรับ, จำนวนเส้นขอบ
        int index, acc, number_nodes;
        scanf("%d%d%d", &index, &acc, &number_nodes);
        accept[index] = acc; // เก็บสถานะยอมรับ
        for (j = 0; j < number_nodes; j++) { // เพิ่มเส้นขอบทั้งหมด
            int node_add;
            int edge;
            scanf("%d%d", &edge, &node_add);
            graph[index] = push(graph[index], '0' + edge, node_add);
        }
    }
    int size = 1; // ขนาดอินพุต
    int count = 0; // นับสตริงเอาต์พุต
    if (accept[1] == 1) { // ตรวจสอบสตริงว่าง
        printf("e\n");
        count++;
    }
    while (count < 11) {
        char** arr;
        int power = pow(2, size);
        arr = (char**)malloc(power * sizeof(char*));
        for (i = 0; i < power; i++)
            arr[i] = (char*)malloc(size * sizeof(char));
        char a[20] = {'\0'};
        generate((char**)arr, size, a); // สร้างอินพุต
        for (i = 0; i < power; i++) {
            char input[20] = {'\0'};
            for (j = 0; j < size; j++) {
                char foo[2];
                foo[0] = arr[i][size - 1 - j];
                foo[1] = '\0';
                strcat(input, foo);
            }
            int result = nfa(graph, 1, input, accept, 0);
            // เก็บผลลัพธ์ของ NFA
            if (result == 1) {
                printf("%s\n", input);
                count++;
            }
            if (count == 10)
                return 0;
        }
        size++; // เพิ่มขนาดสตริงไบนารีอินพุต
        row = 0;
    }
    return 0;
}

อินพุต

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

เอาต์พุต

00 11 000 001 011 100 110 111 0000 0001