投稿获客
广告
广告 广告 广告
广告 广告 广告 广告
广告 █ 推荐【菠萝云】香港16G内存99元 【CDNCloud】极速、安全可靠的加速体验 广告位联系QQ：253000106 【UStat】免费网站统计平台 SSL证书低至2折 单域名36元起 免费测试！海总一手APK免杀处理 广告位联系QQ：253000106 CDN 服务器 反炸 劫持 域名屏蔽 【UStat】专业网站统计平台 域名注册：海量域名快速注册 安卓免杀 谷歌报毒 封装 苹果签名 广告位联系QQ：253000106 【域名被劫持污染如何处理】 安卓免杀★超级签★封装★谷歌屏蔽 广告位联系QQ：253000106

*本站广告为第三方投放，如发生纠纷，请向本站索取第三方联系方式沟通

  1. 创想鸟首页
  2. 好文分享

用C语言编写模拟非确定有限自动机（NFA）的程序

程序猿 • • 好文分享 • 阅读 0

用c语言编写模拟非确定有限自动机（nfa）的程序

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

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

NDFA 的正式定义 –

NFA / NDFA（非确定性有限自动机）可以用 5 元组（Q、Σ、δ、q0、F）表示，其中 –

立即学习“C语言免费学习笔记（深入）”；

Q 是有限状态集。

Σ 是称为字母表的有限符号集。

δ 是转换函数，其中 d: Q × Σ → 2Q（这里采用了 Q 的幂集（2Q），因为在 NDFA 的情况下，从一个状态可以发生到 Q 状态的任意组合的转换）

q0是处理任何输入的初始状态 (q0 ∈ Q)。

F 是 Q 的一组最终状态 (F ⊆ Q)。

在编程中，NFA 是使用有向图创建的。图中的每个顶点表示 NDA 的状态。图的边可以具有 0 或 1 两个值之一。标记为 0 的边表示不接受转换，而标记为 1 的边表示接受转换。

图通常有一个入口点顶点 1 从那里获取输入字符串，该字符串是有限长度的二进制数组。

让我们看一下 NFA 图形形式，然后使用它求解语法。

用C语言编写模拟非确定有限自动机（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行）

要检查的字符串

示例

41031204211043010412044120114101101

输出

Yes/No

示例

#include #include #include #include #include int row = 0;struct node{   int data;   struct node* next;   char edgetype;}typedef node;// Adds an edge to an adjacency listnode* 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 inputint 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 nvoid generate(char** arr, int size, char *a){   if (size==0){      strcpy(arr[row], a);      row++;      return;   }   char b0[20] = {'�'};   char b1[20] = {'�'};   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
");      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] = {''};      generate((char**)arr,size,a); //Generate inputs      for (i=0; i<power; i++){         char input[20] = {''};         for (j=0; j<size; j++){            char foo[2];            foo[0] = arr[i][size-1-j];            foo[1] = '';            strcat(input,foo);            //Copy generated string input         }         int result = nfa(graph,1,input,accept,0);         // Store result of nfa         if (result==1){            printf("%s
",input);            count++;         }         if (count==10)         return 0;      }      size++; //Increment size of binary string input      row=0;   }   return 0;}

输入

41 0 4 0 1 0 2 1 1 1 32 0 1 0 43 0 1 1 44 1 2 0 4 1 4

输出

001100000101110011011100000001

以上就是用C语言编写模拟非确定有限自动机（NFA）的程序的详细内容，更多请关注创想鸟其它相关文章！

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444093.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
0 0

关于作者

程序猿的头像

程序猿签约作者

414.1K 文章
0 评论
2 粉丝
这个人很懒，什么都没有留下～
上一篇 2025年12月17日 21:00:06
下一篇 2025年12月17日 21:00:19

相关推荐

发表回复

登录后才能评论
关注微信