C 언어로 비결정적 유한 자동 장치(NFA)를 시뮬레이션하는 프로그램 작성

{1->1} 1001 {1->4} 1001

{1->1->1} 001 {1->1->2} 001

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

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

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

4 1031204 21104 301041204 4120114 101101

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 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
"); count++; } while (count < 11){ char** arr; int power = pow(2,size); arr = (char**)malloc(power*sizeof(char*)); for (i=0;i
",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