โปรแกรม C เพื่อจำลอง Nondeterministic Finite Automata (NFA)

ในปัญหานี้ เราจะสร้างโปรแกรม C เพื่อจำลอง Finite automata (NFA) ที่ไม่กำหนดขึ้นเอง

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

คำจำกัดความอย่างเป็นทางการของ NDFA -

NFA / NDFA (ออโตมาตาไม่กำหนดแบบกำหนด) สามารถแสดงด้วย 5-tuple (Q, ∑, δ, q0, F) โดยที่ −

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

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

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

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

โปรแกรม C เพื่อจำลอง Nondeterministic Finite Automata (NFA)

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

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

มาเช็คกันก่อนว่า string 01001 ยอมรับหรือไม่

สถานะเริ่มต้น 1 ป้อน 0 ด้วย 0 เราสามารถไปที่สถานะ 4 หรือวนรอบตัวเองเป็น 1

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

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

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

จากสถานะ 1 เราสามารถไปที่ 2 หรือ self-loop จากสถานะ 4 เราไม่สามารถดำเนินการต่อไปได้ ดังนั้นเราจะยกเลิกกรณีนี้

เราจะพิจารณาจากกรณีหนึ่ง -

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

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

From state 1, we can go to 4 or self-loop,
From state 2, we can go to 4 or self-loop

เราจะพิจารณาทุกกรณี -

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

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

From state 1, we can go to 4 or self-loop,
From state 2, we can go to 4 or self-loop,
From state 4, we can go to 3 or self-loop.

เราจะพิจารณาทุกกรณี -

{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 -

From state 1, we can go to 2 or self-loop,
From state 2, we can go to 3,
From state 3, we can go to 4,
From state 4, we cannot go further.

เราจะพิจารณาทุกกรณี -

{1->1->1->1->1->1/2} does not reach final stage
{1->1->1->1->4} 1 cannot accept input
{1->1->1->4->3 ->4} accepts the input
{1->1->1->4->4} cannot accept input
{1->1->2->1->1 -> 1/2} does not reach final stage
{1->1->2->1->4} cannot accept input
{1->1->2->4->3->4} accepts the input
{1->1->2->4->4} cannot accept input

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

ตอนนี้ ไปที่โปรแกรม C เพื่อจำลอง Nondeterministic Finite Automata (NFA) -

อินพุตของโปรแกรมจะเป็นรายการที่อยู่ติดกันของ NFA -

จำนวนขอบ (n)

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

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

ตัวอย่าง

ผลลัพธ์

Yes/No

ตัวอย่าง

#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;
// Adds an edge to an adjacency list
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;
}
//Recursive function to check acceptance of input
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;
}
//Function to generate binary strings of size 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)); //Add 0 in front
   generate((char**)arr, size-1, strcat(b1,a)); //Add 1 in front
   return;
}
int main(){
   int n;
   int i, j;
   scanf("%d", &n); //Number of nodes
   node* graph[n+1]; //Create a graph
   for (i=0;i<n+1;i++)
   graph[i]=NULL;
   int accept[n+1]; //Array to store state of vertex
   for (i=0; i<n; i++){
      //Index of vertex , Acceptance state , Number of edges
      int index,acc,number_nodes;
      scanf("%d%d%d",&index,&acc,&number_nodes);
      accept[index]=acc; //Store acceptance
      for (j=0;j<number_nodes;j++) //Add all edges{
         int node_add;
         int edge;
         scanf("%d%d",&edge,&node_add);
         graph[index] = push(graph[index],'0'+edge,node_add);
      }
   }
   int size = 1; //Size of input
   int count = 0; //Keep count of output strings
   if (accept[1]==1) //Check for empty string{
      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); //Generate inputs
      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);
            //Copy generated string input
         }
         int result = nfa(graph,1,input,accept,0);
         // Store result of nfa
         if (result==1){
            printf("%s\n",input);
            count++;
         }
         if (count==10)
         return 0;
      }
      size++; //Increment size of binary string input
      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

ผลลัพธ์