資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告