इस समस्या में, हम नॉन-डिटरमिनिस्टिक फाइनाइट ऑटोमेटा (NFA) का अनुकरण करने के लिए एक C प्रोग्राम बनाएंगे।
NFA (नॉन-डिटरमिनिस्टिक फाइनाइट ऑटोमेटा) एक फाइनाइट स्टेट मशीन है जो एक इनपुट प्रतीक के लिए राज्यों के किसी भी संयोजन में जा सकती है यानी कोई सटीक राज्य नहीं है जिस पर मशीन जाएगी।
NDFA की औपचारिक परिभाषा:
NFA / NDFA (नॉन-डिटरमिनिस्टिक फाइनाइट ऑटोमेटा) को 5-टपल (Q, Σ, δ, q0, F) द्वारा दर्शाया जा सकता है जहां:
Q राज्यों का एक परिमित समूह है।
Σ प्रतीकों का एक परिमित समूह है जिसे वर्णमाला कहा जाता है।
δ संक्रमण फ़ंक्शन है जहां δ: Q × Σ → 2^Q (यहां Q के पावर सेट (2^Q) को लिया गया है क्योंकि 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 -
राज्य 1 से, हम 4 या स्वयं-लूप पर जा सकते हैं, राज्य 2 से, हम 4 या स्वयं-लूप पर जा सकते हैं
हम सभी मामलों पर विचार करेंगे:
{1->1->1->1} 01 {1->1->1->4} 01 {1->1->2->1} 01 {1->1->2->4} 01 राज्य 1/2/4, इनपुट 0 -
राज्य 1 से, हम 4 या स्वयं-लूप पर जा सकते हैं, राज्य 2 से, हम 4 या स्वयं-लूप पर जा सकते हैं, राज्य 4 से, हम 3 या स्वयं-लूप पर जा सकते हैं।
हम सभी मामलों पर विचार करेंगे:
{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 -
राज्य 1 से, हम 2 या स्वयं-लूप पर जा सकते हैं, राज्य 2 से, हम 3 पर जा सकते हैं, राज्य 3 से, हम 4 पर जा सकते हैं, राज्य 4 से, हम आगे नहीं जा सकते।
हम सभी मामलों पर विचार करेंगे:
{1->1->1->1->1->1/2} अंतिम चरण तक नहीं पहुंचता {1->1->1->1->4} 1 इनपुट स्वीकार नहीं कर सकता {1->1->1->4->3->4} इनपुट स्वीकार करता है {1->1->1->4->4} इनपुट स्वीकार नहीं कर सकता {1->1->2->1->1->1/2} अंतिम चरण तक नहीं पहुंचता {1->1->2->1->4} इनपुट स्वीकार नहीं कर सकता {1->1->2->4->3->4} इनपुट स्वीकार करता है {1->1->2->4->4} इनपुट स्वीकार नहीं कर सकता अतः दिए गए इनपुट स्ट्रिंग के साथ अंतिम राज्य तक पहुंचने के तरीके हैं।
अब, आइए C प्रोग्राम पर चलते हैं जो नॉनडिटरमिनिस्टिक फाइनाइट ऑटोमेटा (NFA) का अनुकरण करता है:
प्रोग्राम का इनपुट NFA की आसन्न सूची होगी:
किनारों की संख्या (n)
किनारा कनेक्टिविटी (n पंक्तियां)
जांच की जाने वाली स्ट्रिंग्स
उदाहरण
4 1031204 21104 301041204 4120114 101101
आउटपुट
हां/नहीं
उदाहरण
#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; // आसन्न सूची में एक किनारा जोड़ें 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; } // इनपुट की स्वीकृति जांचने के लिए पुनरावर्ती फ़ंक्शन 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; } // आकार 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)); // सामने 0 जोड़ें generate((char**)arr, size - 1, strcat(b1, a)); // सामने 1 जोड़ें return; } int main(){ int n; int i, j; scanf("%d", &n); // नोड्स की संख्या node* graph[n + 1]; // एक ग्राफ बनाएं for (i = 0; i < n + 1; i++) graph[i] = NULL; int accept[n + 1]; // शीर्ष की स्थिति संग्रहीत करने के लिए सरणी for (i = 0; i < n; i++){ // शीर्ष का सूचकांक, स्वीकृति स्थिति, किनारों की संख्या int index, acc, number_nodes; scanf("%d%d%d", &index, &acc, &number_nodes); accept[index] = acc; // स्वीकृति संग्रहीत करें for (j = 0; j < number_nodes; j++) // सभी किनारे जोड़ें{ int node_add; int edge; scanf("%d%d", &edge, &node_add); graph[index] = push(graph[index], '0' + edge, node_add); } } int size = 1; // इनपुट का आकार int count = 0; // आउटपुट स्ट्रिंग की गिनती रखें if (accept[1] == 1) // खाली स्ट्रिंग के लिए जांचें{ 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); // इनपुट उत्पन्न करें 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); // उत्पन्न स्ट्रिंग इनपुट कॉपी करें } int result = nfa(graph, 1, input, accept, 0); // nfa का परिणाम संग्रहीत करें if (result == 1){ printf("%s\n", input); count++; } if (count == 10) return 0; } size++; // बाइनरी स्ट्रिंग इनपुट का आकार बढ़ाएं 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
