在这个问题中，我们将创建一个 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"); count++; } while (count
",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）的程序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2584916.html
