非決定性有限オートマトン（NFA）をシミュレートするCプログラム

この問題では、非決定性有限オートマトン（NFA）をシミュレートするCプログラムを作成します。

NFA （非決定性有限オートマトン）入力シンボルの状態の任意の組み合わせに移動できる有限状態マシン。つまり、マシンが移動する正確な状態はありません。

NDFAの正式な定義-

NFA / NDFA（非決定性有限オートマトン）は、5タプル（Q、∑、δ、q0、F）で表すことができます。ここで-

• Qは有限の状態のセットです。

• ∑はアルファベットと呼ばれる有限の記号のセットです。

• δは、d：Q×∑→2Qの遷移関数です（NDFAの場合、状態からQ状態の任意の組み合わせに遷移する可能性があるため、ここではQ（2Q）のべき集合が採用されています）

• q0は、入力が処理される初期状態です（q0∈Q）。

• Fは、Qの最終状態/状態のセットです（F⊆Q）。

プログラミングでは、NFAは有向グラフを使用して作成されます。グラフの各頂点は、NDAの状態を示しています。グラフのエッジは、0または1の2つの値のいずれかを持つことができます。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->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\n");
      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\n",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