数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学模拟非确定有限自动机 (NFA) 的 C 程序
在这个问题中，我们将创建一个 C 程序来模拟非确定性有限自动机 (NFA)。
NFA (非确定性有限自动机) 是一种有限状态机，对于一个输入符号，它可以移动到任何状态组合，即没有确切的状态机器将移动到。
NDFA 的形式化定义：
NFA/NDFA（非确定性有限自动机）可以用 5 元组 (Q, ∑, δ, q0, F) 表示，其中：
Q 是一个有限的状态集。
∑ 是一个有限的符号集，称为字母表。
δ 是转移函数，其中 δ: Q × ∑ → 2Q（这里取 Q 的幂集 (2Q)，因为在 NDFA 的情况下，从一个状态可以转移到 Q 状态的任何组合）
q0 是处理任何输入的初始状态 (q0 ∈ Q)。
F 是 Q 的最终状态集 (F ⊆ Q)。
在编程中，NFA 是使用有向图创建的。图的每个顶点表示 NDA 的状态。图的边可以具有 0 或 1 之一的两个值之一。标记为 0 的边表示非接受转移，而标记为 1 的边表示接受转移。
图通常有一个入口点（顶点 1），它从那里获取输入字符串，这是一个有限长度的二进制数组。
让我们看看 NFA 的图形形式，然后使用它来解决语法。
起始状态 -> 1
最终状态（接受状态）-> 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因此，有多种方法可以使用给定的输入字符串到达最终状态。
现在，让我们来看一下模拟非确定性有限自动机 (NFA) 的 C 程序：
程序的输入将是 NFA 的邻接表：
边的数量 (n)
边连接性 (n 行)
要检查的字符串
示例
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] = {'\0'};
char b1[20] = {'\0'};
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] = {'\0'};
generate((char**)arr,size,a); //Generate inputs
for (i=0; i<power; i++){
char input[20] = {'\0'};
for (j=0; j<size; j++){
char foo[2];
foo[0] = arr[i][size-1-j];
foo[1] = '\0';
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;
}输入
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
更新于：2020年7月18日
3K+ 次浏览
广告