Écrire un programme pour simuler un automate fini non déterministe (NFA) en langage C

在这个问题中，我们将创建一个 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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!