ননডেটারমিনিস্টিক ফিনিট অটোমেটা (এনএফএ) অনুকরণ করতে সি প্রোগ্রাম

এই সমস্যায়, আমরা নন-ডিটারমিনিস্টিক ফিনিট অটোমেটা (এনএফএ) অনুকরণ করার জন্য একটি সি প্রোগ্রাম তৈরি করব।

NFA (নন-ডিটারমিনিস্টিক ফিনিট অটোমেটা) সসীম স্টেট মেশিন যা একটি ইনপুট চিহ্নের জন্য যেকোনও স্টেটের সংমিশ্রণে যেতে পারে, অর্থাৎ মেশিনটি সরে যাবে এমন কোনো সঠিক অবস্থা নেই।

NDFA -

NFA / NDFA (Non-deterministic Finite automata) 5-tuple (Q, ∑, δ, q0, F) দ্বারা উপস্থাপন করা যেতে পারে যেখানে −

• Q হল রাজ্যের একটি সীমিত সেট।

• ∑ হল একটি সীমিত চিহ্নের সেট যাকে বর্ণমালা বলা হয়।

• δ হল ট্রানজিশন ফাংশন যেখানে d:Q × ∑ → 2Q (এখানে Q (2Q) এর পাওয়ার সেট নেওয়া হয়েছে কারণ NDFA-এর ক্ষেত্রে, একটি রাজ্য থেকে, Q রাজ্যের যেকোনো সংমিশ্রণে রূপান্তর ঘটতে পারে)

• q0 হল প্রাথমিক অবস্থা যেখান থেকে যেকোনো ইনপুট প্রক্রিয়া করা হয় (q0 ∈ Q)।

• F হল Q (F ⊆ Q) এর চূড়ান্ত অবস্থা/স্থিতির একটি সেট।

প্রোগ্রামিংয়ে, এনএফএ একটি নির্দেশিত গ্রাফ ব্যবহার করে তৈরি করা হয়। গ্রাফের প্রতিটি শীর্ষবিন্দু 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/2/4, ইনপুট 0 −

স্টেট 1 থেকে, আমরা 4 বা সেলফ-লুপে যেতে পারি, স্টেট 2 থেকে, আমরা 4 বা সেলফ-লুপে যেতে পারি, স্টেট 4 থেকে, আমরা 3 বা সেলফ-লুপে যেতে পারি।

আমরা সমস্ত ক্ষেত্রে বিবেচনা করব -

রাজ্য 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} ইনপুট গ্রহণ করতে পারে না

তাই প্রদত্ত ইনপুট স্ট্রিং দিয়ে চূড়ান্ত অবস্থায় পৌঁছানোর উপায় রয়েছে।

এখন, ননডেটারমিনিস্টিক ফিনিট অটোমেটা (NFA) -

প্রোগ্রামের ইনপুট হবে NFA -

প্রান্তের সংখ্যা (n)

প্রান্ত সংযোগ (n লাইন)

স্ট্রিং চেক করতে হবে

উদাহরণ

41031204211043010412044120114101101

আউটপুট

হ্যাঁ/না

উদাহরণ

#include #include #include #include #include int row =0;struct node{int data; struct নোড* পরবর্তী; char edgetype;}typedef node;// একটি সংলগ্ন লিস্টনোডে একটি প্রান্ত যোগ করে* push(node* first , char edgetype , int data){ node* new_node =(node*)malloc(sizeof(node)); new_node->edgetype =edgetype; নতুন_নোড->ডেটা =ডেটা; new_node->পরবর্তী =NULL; if (first==NULL){ first =new_node; নতুন_নোড ফেরত দিন; } প্রথম->পরবর্তী =ধাক্কা (প্রথম->পরবর্তী, প্রান্তের ধরন, ডেটা); রিটার্ন ফার্স্ট;}//রিকারসিভ ফাংশন ইনপুটেন্ট এনএফএ (নোড** গ্রাফ, int কারেন্ট, char* ইনপুট, int* স্বীকার, int স্টার্ট){ if (start==(int)strlen(input)) রিটার্ন অ্যাকসেপ্ট করার জন্য [বর্তমান]; নোড* টেম্প =গ্রাফ [বর্তমান]; যখন (temp !=NULL){ if (input[start]==temp->edgetype) { if (nfa(graph,temp->data,input,accept,start+1==1)){ রিটার্ন 1; } } temp=temp->পরবর্তী; } রিটার্ন 0;}// আকারের এনভয়েড জেনারেট (char** arr, int size, char *a){ if (size==0){ strcpy(arr[row], a); সারি ++; প্রত্যাবর্তন } char b0[20] ={'\0'}; char b1[20] ={'\0'}; b0[0] ='0'; b1[0] ='1'; জেনারেট((char**)arr, size-1, strcat(b0,a)); //সামনে 0 যুক্ত করুন জেনারেট((char**)arr, size-1, strcat(b1,a)); //সামনের রিটার্নে 1 যোগ করুন;}int main(){ int n; int i, j; scanf("%d", &n); //নোডের সংখ্যা নোড* গ্রাফ[n+1]; //এর জন্য একটি গ্রাফ তৈরি করুন (i=0;i 
ইনপুট
 
41 0 4 0 1 0 2 1 1 32 0 1 0 43 0 1 1 44 1 2 0 4 1 4
 
আউটপুট
 
001100000101110011011100000001