इस समस्या में, हम गैर-नियतात्मक परिमित ऑटोमेटा (NFA) का अनुकरण करने के लिए एक C प्रोग्राम बनाएंगे।
एनएफए (गैर-नियतात्मक परिमित ऑटोमेटा) परिमित राज्य मशीन जो एक इनपुट प्रतीक के लिए राज्यों के किसी भी संयोजन में जा सकती है यानी कोई सटीक स्थिति नहीं है जिसमें मशीन चलती है।
NDFA की औपचारिक परिभाषा -
NFA / NDFA (गैर-नियतात्मक परिमित ऑटोमेटा) को 5-टुपल (Q, ∑, δ, q0, F) द्वारा दर्शाया जा सकता है जहाँ -
-
क्यू राज्यों का एक सीमित सेट है।
-
∑ प्रतीकों का एक सीमित सेट है जिसे अक्षर कहा जाता है।
-
δ संक्रमण फलन है जहां d:Q × → 2Q (यहाँ Q (2Q) का पावर सेट लिया गया है क्योंकि NDFA के मामले में, एक राज्य से, संक्रमण Q राज्यों के किसी भी संयोजन में हो सकता है)
-
q0 प्रारंभिक अवस्था है जहाँ से कोई इनपुट संसाधित किया जाता है (q0 Q)।
-
F, Q (F ⊆ Q) की अंतिम अवस्था/राज्यों का समुच्चय है।
प्रोग्रामिंग में, एनएफए एक निर्देशित ग्राफ का उपयोग करके बनाया गया है। ग्राफ का प्रत्येक शीर्ष एनडीए के राज्यों को दर्शाता है। ग्राफ़ के किनारों में 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 प्रोग्राम पर आते हैं -
कार्यक्रम का इनपुट एनएफए की एक आसन्न सूची होगी -
किनारों की संख्या (एन)
एज कनेक्टिविटी (एन लाइन्स)
जाँच की जाने वाली स्ट्रिंग्स
उदाहरण
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