NFA (Non-deterministic Finite Automata) হলো একটি ফিনাইট স্টেট মেশিন যেখানে একটি ইনপুট সিম্বল জন্য একাধিক স্টেটে যাওয়া সম্ভব। ৫-টাপল (Q, Σ, δ, q0, F) দিয়ে প্রতিনিধিত্ব করা হয়। প্রোগ্রামটি এডজেসেন্সি লিস্ট দিয়ে NFA তৈরি করে এবং ইনপুট স্ট্রিং অ্যাকসেপ্ট হয় কিনা চেক করে।
NFA উদাহরণ
স্টেট ১ (স্টার্ট), স্টেট ৪ (ফাইনাল)। ইনপুট "01001" অ্যাকসেপ্ট হয় কিনা চেক করা হয়েছে। একাধিক পাথ এক্সপ্লোর করে ফাইনাল স্টেটে পৌঁছানো সম্ভব কিনা দেখা হয়।
প্রোগ্রাম ইনপুট ফরম্যাট
- নোড সংখ্যা (n)
- প্রতিটি নোডের জন্য: ইনডেক্স, অ্যাকসেপ্ট স্টেট (০/১), এজ সংখ্যা
- প্রতিটি এজ: এজ টাইপ (০/১), ডেস্টিনেশন নোড
- চেক করার স্ট্রিংস
C প্রোগ্রাম উদাহরণ (সংক্ষিপ্ত)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
struct node { int data; struct node* next; char edgetype; };
typedef struct node node;
node* push(node* first, char edgetype, int data) { /* এজ যোগ */ }
int nfa(node** graph, int current, char* input, int* accept, int start) {
if (start == strlen(input)) return accept[current];
node* temp = graph[current];
while (temp) {
if (input[start] == temp->edgetype)
if (nfa(graph, temp->data, input, accept, start+1)) return 1;
temp = temp->next;
}
return 0;
}
/* main()-এ গ্রাফ বিল্ড, ইনপুট জেনারেট, NFA কল করা হয়েছে */
নমুনা ইনপুট/আউটপুট
Input: 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 Output: 00 11 000 001 011 100 110 111 0000 0001
