Nondeterministic Finite Automaton
নন-ডিটারমিনিস্টিক ফাইনাইট অটোমাটন
DFA-র মতোই ৫-টুপল, কিন্তু একটা (state, symbol) থেকে একাধিক (বা শূন্য) পরবর্তী state এবং ε-transition অনুমোদিত — কোনো একটা বৈধ path accept করলেই string গৃহীত। DFA-র সমান ক্ষমতার (subset construction প্রমাণিত), কিন্তু লিখতে সহজ।
also: NFA
আনুষ্ঠানিক সংজ্ঞা: δ: Q × (Σ∪{ε}) → 𝒫(Q) — DFA-র δ: Q×Σ→Q-এর
তুলনায় output একটা state-এর বদলে state-সেট, আর input ঐচ্ছিকভাবে
ε-ও হতে পারে।
Subset construction (NFA→DFA): DFA-র প্রতিটা state = NFA
state-এর একটা সেট (ε-closure-সহ)। Worklist algorithm — start
state = ECLOSE(q0), প্রতিটা নতুন সেট থেকে প্রতিটা symbol-এ নতুন
সেট বানিয়ে যান যতক্ষণ না নতুন কিছু আসে। Worst-case 2^|Q| DFA
state (exponential blow-up), বাস্তবে সাধারণত অনেক কম।
Nondeterminism ≠ randomness। এটা একটা গাণিতিক সংজ্ঞা (“কোনো একটা বৈধ path আছে”) — সিমুলেশনে সব সম্ভাব্য state একসাথে একটা সেট হিসেবে deterministically track করা হয়, true parallel execution না।
যেখানে ব্যবহৃত: Thompson’s construction দিয়ে regex থেকে সরাসরি
NFA বানানো (compositional, সহজ) তারপর subset construction দিয়ে
DFA-তে কম্পাইল — flex/re2c-এর মতো lexer generator-এর ঠিক এই
pipeline; compilers/lexical-analysis-এর lexer এই দুই ধাপেরই
ফলাফল।