Write a program to simulate non-deterministic finite automaton (NFA) in C language

在这个问题中，我们将创建一个 C 程序来模拟非确定性有限自动机 (NFA)。

NFA（非确定性有限自动机）有限状态机可以移动到输入符号的任意状态组合，即没有机器将移动到的确切状态。

NDFA 的正式定义 -

NFA / NDFA（非确定性有限自动机）可以用 5 元组（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 图形形式，然后使用它求解语法。

起始状态 -> 1

最终状态state (接受状态) -> 4

让我们检查字符串 01001 是否被接受。

开始状态 1，输入 0，输入 0 可以进入状态 4 或自检循环到状态 1。

我们将考虑这两种情况 -

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

状态1/4，输入1 -

从状态1，我们可以进入状态2或自循环，从状态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 程序来模拟非确定性有限自动机 (NFA) -

程序的输入将是NFA的邻接表 -

边数（n）

边连通性（n行）

要检查的字符串< /p>

示例

4
1031204
21104
301041204
4120114
101101

输出

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] = {&#39;\0&#39;};
   char b1[20] = {&#39;\0&#39;};
   b0[0] = &#39;0&#39;;
   b1[0] = &#39;1&#39;;
   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],&#39;0&#39;+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</p><p>");
      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] = {&#39;\0&#39;};
      generate((char**)arr,size,a); //Generate inputs
      for (i=0; i<power; i++){
         char input[20] = {&#39;\0&#39;};
         for (j=0; j<size; j++){
            char foo[2];
            foo[0] = arr[i][size-1-j];
            foo[1] = &#39;\0&#39;;
            strcat(input,foo);
            //Copy generated string input
         }
         int result = nfa(graph,1,input,accept,0);
         // Store result of nfa
         if (result==1){
            printf("%s</p><p>",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

输出

00
11
000
001
011
100
110
111
0000
0001

The above is the detailed content of Write a program to simulate non-deterministic finite automaton (NFA) in C language. For more information, please follow other related articles on the PHP Chinese website!