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

程序猿 • 2025年12月17日 21:00:09 • 好文分享 • 阅读 0

在这个问题中，我们将创建一个 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 图形形式，然后使用它求解语法。

起始状态 -> 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

c语言模拟程序非确定有限自动机（NFA）

打赏

微信扫一扫

支付宝扫一扫

0 0

关于作者

程序猿签约作者

346.9K 文章

0 评论

1 粉丝

这个人很懒，什么都没有留下～

在C语言中的命令行参数示例

上一篇 2025年12月17日 21:00:06

PHP中整型和浮点型有什么区别？

下一篇 2025年12月10日 04:31:59

好文分享

在C语言中的命令行参数示例

在执行 C 程序时，可以将一些值从命令行传递给它们。这些值称为命令行参数，很多时候它们对您的程序很重要，尤其是当您想从外部控制程序而不是在代码内对这些值进行硬编码时。命令行参数使用 main() 函数参数处理，其中 argc 指传递的参数数量，argv[] 是指向每个参数的指针数组传递给程序。以下…

程序猿
2025年12月17日
0000
好文分享

使用多线程在C++中实现归并排序

我们得到一个未排序的整数数组。任务是使用通过多线程实现的合并排序技术对数组进行排序合并排序合并排序是一种基于分而治之技术的排序技术，我们将将数组分成相等的两半，然后以排序的方式将它们组合起来。实现归并排序的算法是检查是否有一个元素否则，将数据递归地分成两半，直到无法再分为止。立即学习“C…

程序猿
2025年12月17日
0000
好文分享

在C语言中，寄存器存储类是什么？

在C编程语言中有四个存储类，分别是： autoexternstaticregister 寄存器变量关键字是register。寄存器变量的值存储在CPU的寄存器中，而不是存储在内存中，普通变量存储在内存中。寄存器是CPU中的临时存储单元。立即学习“C语言免费学习笔记（深入）”；它们允许寄存器…

程序猿
2025年12月17日
0000
好文分享

在C语言中，负数的绝对值为正数

在这里，我们将看到如果我们使用负数来获取模数会得到什么结果。让我们看一下以下程序及其输出，以了解这个概念。示例 #includeint main() { int a = 7, b = -10, c = 2; printf(“Result: %d”, a % b / c);} 输出 Result: …

程序猿
2025年12月17日
0000
好文分享

C语言中的身份矩阵程序

给定一个方阵 M[r][c]，其中“r”是一定数量的行，“c”是列，使得 r = c，我们必须检查“M”是否是单位矩阵。恒等矩阵恒等矩阵也称为大小为nxn方阵的单位矩阵，其中对角元素的整数值为1，非对角元素的整数值为0 p> 就像下面给定的示例 – $$I1=begin{bma…

程序猿
2025年12月17日
0000
好文分享

C++程序打印空心的右三角星形图案

以金字塔、正方形和菱形等不同格式显示星形图案非常有用常见于基础编程和逻辑构建。我们见过几颗星星学习编程中的循环语句时的数字模式问题。在本文中，我们将看到如何在 C++ 中打印空心直角三角形星形图案。在此程序中，我们采用行号 n，这将为 n 个数创建一个星形图案线。让我们看一下相同的示例。右空心星…

程序猿
2025年12月17日
0000
好文分享

C/C++标记？

C++ 令牌是程序的最小独立单元。 C++ 是 C 的超集，因此大多数 C 结构在 C++ 中都是合法的，其含义和用法不变。因此，标记、表达式和数据类型与 C 的标记、表达式和数据类型类似。以下是 C++ 标记：（大多数 C++ 标记基本上与 C 标记类似）关键字标识符常量变量运算符关键字关…

程序猿
2025年12月17日
0000
好文分享

使用C++编写的代码：找到使用字母表前K个字母组成的字典序最小的字符串，且相邻字符不能相同

在编程世界中，解决字符串操作问题是一个常见且有趣的挑战。面临的一个关键问题是如何仅利用字母表中的 K 个字母来获得按字典顺序排列的最小字符串，同时遵循诸如不匹配相邻字符之类的附加约束。在本文中，我们的目的是深入研究这个问题并使用 C++ 编程语言提出有效的解决方案。通过详细介绍语法中使用的不同方法并…

程序猿
2025年12月17日
0000
好文分享

Klee的算法（线段的并集长度）在C++中

在本教程中，我们将编写一个程序，用于查找线段的并集的长度。我们已经给出了线段的起点和终点，我们需要找到线段的并集的长度。我们将使用的算法称为klee’s算法。让我们来看看解决这个问题的步骤。立即学习“C++免费学习笔记（深入）”；用所有线段的坐标初始化数组。初始化一个名为poi…

程序猿
2025年12月17日
0000
好文分享

在C++中，将给定的四个数字组成的第n个数字的位数

We need to find the number of digits in the nth number made of given four digits 1, 2, 3, and 4. The series with the above four digits is as follows 1…

程序猿
2025年12月17日
0000
好文分享

在C语言中的布尔数组谜题

这是一个基于数组的谜题，需要你将包含两个元素的数组中的所有数字都更改为0。数组的一个元素是0，另一个元素可能是0也可能不是。要解决这个谜题，程序需要找到非零元素并将其更改为0。以下是解决布尔数组谜题所需的约束条件 − 允许的操作是补集，其他操作不允许。不允许使用循环和条件语句。也不允许直接赋值。…

程序猿
2025年12月17日
0000
好文分享

c语言大小写字母怎么转化

c语言大小写字母转化的方法：1、tolower()函数，使用for循环来遍历字符串中的每个字符，将每个字符传递给tolower()函数进行转换，并将转换结果赋值给原来的字符，最后打印转换后的字符串；2、toupper()函数，使用for循环来遍历字符串中的每个字符，将每个字符传递给toupper()…

程序猿
2025年12月17日
0000
好文分享

在C语言中，转义序列

许多编程语言支持一种称为转义序列的概念。当一个字符前面有一个反斜杠（）时，它被称为转义序列，并且对编译器有特殊的意义。例如，下面的语句中的是一个有效的字符，它被称为换行字符 − char ch = ”;在这里，字符n之前有一个反斜杠（），它具有特殊含义，即换行，但请记住反斜杠（）只对一些字符具有…

程序猿
2025年12月17日
0000
好文分享

在C语言中编写一个程序来打印菱形图案

程序描述钻石图案是简单金字塔图案和倒金字塔图案的组合。算法 First Row: Display 1Second Row: Display 1,2,3Third Row: Display 1,2,3,4,5Fourth Row: Display 1,2,3,4,5,6,7Fifth Row: D…

程序猿
2025年12月17日
0000
好文分享

c语言画皮卡丘代码怎么写

编写步骤：1、在C语言中安装图形库；2、使用“initgraph”函数初始化图形库，并设置绘图窗口的大小和位置；2、使用“setcolor”函数设置绘图的颜色，使用“circle”函数绘制圆形，使用`arc`函数绘制弧线，使用“ellipse”函数绘制椭圆；3、使用“getch”函数等待用户按下任意…

程序猿
2025年12月17日
0000
好文分享

使用C++移除两个零之间的元素

在本文中，我们将讨论如何从一个只包含0和1字符的给定字符串中删除两个零之间的元素。最终的字符串不应包含任何被0包围的字符’1’。例如- Input : string = “110010”Output : “11000”Expla…

程序猿
2025年12月17日
0000
好文分享

使用C++编写一个找到数字的程序，其数字的各位数之和为偶数的程序

能被2整除的整数是偶数。因此在本文中，我们给定了一个数n，我们需要找到第n个数字，其数字之和为偶数。前五个数字的数字之和为偶数的数分别是2、4、6、8和11。例如 − Input : n = 5Output : 11Explanation : First 5 numbers with even su…

程序猿
2025年12月17日
0000
好文分享

如何使用C语言以Pascal三角形的形式打印整数？

pascal的三角形是以三角形的形式表示整数的一种方法。其中一个著名的表示方法是使用二项式方程。我们可以使用组合和阶乘来实现这一点。构建Pascal三角形三角形外的所有值都被视为零（0）。第一行是0 1 0，而只有1在Pascal的三角形中占据一个空间，0是看不见的。第二行是通过添加（0+1）和…

程序猿
2025年12月17日
0000
好文分享

在C语言中编写一个程序来打印实心和空心菱形图案

程序说明打印如下所示的实心和空心菱形图案算法对于空心菱形 – Accept the Number of Rows for Hollow Rhombus from the UserCreate a Hollow Rhombus containing the same number o…

程序猿
2025年12月17日
0000
好文分享

C和C++之间的不兼容性

在这里，我们将看到C和C++之间的一些不兼容性。一些可以使用C编译器编译的C代码，在C++编译器中无法编译。并且会返回错误。我们可以使用一种语法来定义函数，该语法在参数列表之后可选择指定参数类型。示例 #includevoid my_function(x, y)int x;int y; { //…

程序猿
2025年12月17日
0000

发表回复

登录后才能评论

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

示例

输出

示例

输入

输出

关于作者

相关推荐

发表回复