NFA — ফরমাল ডেফিনিশন

১ · NFA-এর ফরমাল সংজ্ঞা

NFANondeterministic Finite Automatonএকটি ৫-টাপল অটোমাটা যেখানে ট্রানজিশন ফাংশন প্রতিটি স্টেট/সিম্বলের জন্য একটি সেট অফ স্টেট রিটার্ন করে। ও DFA-এর গঠন হুবহু একই: একটি ৫-টাপল $M = (Q, \Sigma, \delta, q_0, F)$, যেখানে Q ফাইনাইট স্টেটের সেট, Σ ইনপুট আলফাবেট, $q_0 \in Q$ স্টার্ট স্টেট, এবং $F \subseteq Q$ অ্যাকসেপ্ট স্টেটের সেট — L06-এর সাথে হুবহু মিলে যায়। একমাত্র পার্থক্য, কিন্তু একটি গুরুত্বপূর্ণ পার্থক্য, ট্রানজিশন ফাংশনে:

$$\delta: Q \times \Sigma \to \mathcal{P}(Q)$$

অর্থাৎ $\delta(q, a)$ একটি একক স্টেট রিটার্ন করে না — এটি Q-এর একটি সাবসেট রিটার্ন করে (Q-এর পাওয়ার সেট $\mathcal{P}(Q)$-এর একটি সদস্য) — এই সাবসেটটি খালিও হতে পারে (কোনো বৈধ পরবর্তী স্টেট নেই), অথবা একাধিক স্টেট থাকতে পারে (একাধিক সম্ভাব্য পরবর্তী স্টেট)। DFA-তে $\delta$ ছিল একটি টোটাল ফাংশন যা প্রতিটি জোড়ার জন্য ঠিক একটি স্টেট দেয় — এখানে সেই কড়াকড়ি নেই।

২ · অ্যাকসেপ্টেন্স রুল — "exists" কোয়ান্টিফায়ার

একটি NFA স্ট্রিং w অ্যাকসেপ্ট করে যদি অন্তত একটি সম্ভাব্য চয়েস-সিকোয়েন্স (নন্ডিটারমিনিস্টিক পাথ) থাকে যা $q_0$ থেকে শুরু করে w পড়ে শেষে F-এর কোনো স্টেটে পৌঁছায় — এমনকি যদি অন্যান্য সম্ভাব্য পাথ ব্যর্থ হয় (কোনো অ্যাকসেপ্ট স্টেটে না পৌঁছায়, বা কোনো ডেড-এন্ডে থেমে যায়), তাও w অ্যাকসেপ্টেড বলে গণ্য হয় — যতক্ষণ কোনো একটি পাথ সফল হয়। এটি সব সম্ভাব্য গণনা-পাথের উপর একটি "exists" (∃) কোয়ান্টিফায়ার — DFA-এর একক, নির্ধারিত পাথের সরাসরি বিপরীত।

৩ · কেন NFA ডিজাইন করা প্রায়ই সহজ

একটি concrete উদাহরণ: ভাষা $L = \{w \in \{0,1\}^* : w\text{-এর কোথাও "01" সাবস্ট্রিং আছে}\}$। একটি NFA দিয়ে এটি স্বাভাবিকভাবেই ডিজাইন করা যায় — মেশিন "গেস" করে কখন সাবস্ট্রিংটি শুরু হতে পারে (নন্ডিটারমিনিস্টিকভাবে হয় বর্তমান স্টেটেই থেকে যায়, অথবা সাবস্ট্রিং-খোঁজার শাখায় চলে যায়) — একটি DFA দিয়ে সমতুল্য ভাষা রিকগনাইজ করা সম্ভব (L08 প্রমাণ করবে সব NFA-এর সমতুল্য DFA থাকে), কিন্তু DFA-কে প্রতিটি স্টেটে "সর্বশেষ কী দেখেছি" এক্সপ্লিসিটভাবে মনে রাখতে হয় — NFA-তে এই বুককিপিং নন্ডিটারমিনিজমের মধ্যেই "লুকানো" থাকে, ফলে ডিজাইন প্রায়ই ছোট ও সহজ হয়। এটি সরাসরি L11-এর regex→NFA কনস্ট্রাকশনের পূর্বাভাস — সেই কনস্ট্রাকশনও স্বাভাবিকভাবে নন্ডিটারমিনিস্টিক।

৪ · একটি সত্যিকারের NFA সিমুলেটর

নন্ডিটারমিনিজম সিমুলেট করার স্ট্যান্ডার্ড, সঠিক কৌশল হলো আক্ষরিক অর্থে "ব্যাকট্র্যাক" করা নয় — বরং প্রতিটি মুহূর্তে সব সম্ভাব্য বর্তমান স্টেটের একটি সেট একসাথে ট্র্যাক করা। প্রতিটি ইনপুট সিম্বলে, নতুন সেট হলো বর্তমান সেটের প্রতিটি স্টেট থেকে সেই সিম্বলে পৌঁছানো সব স্টেটের ইউনিয়ন — শেষে যদি এই সেট F-এর সাথে ইন্টারসেক্ট করে (কোনো কমন স্টেট থাকে), তাহলে অ্যাকসেপ্ট।

class NFA:
    def __init__(self, states, alphabet, transition, start, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transition = transition   # dict: (state, symbol) -> set(states)
        self.start = start
        self.accept_states = accept_states

    def accepts(self, string):
        current = {self.start}
        for ch in string:
            nxt = set()
            for q in current:
                nxt |= self.transition.get((q, ch), set())
            current = nxt
            if not current:
                break
        return bool(current & self.accept_states)


states = {"q0", "q1", "q2"}
alphabet = {"0", "1"}
transition = {
    ("q0", "0"): {"q0", "q1"},
    ("q0", "1"): {"q0"},
    ("q1", "0"): {"q1"},
    ("q1", "1"): {"q2"},
    ("q2", "0"): {"q2"},
    ("q2", "1"): {"q2"},
}
nfa = NFA(states, alphabet, transition, "q0", {"q2"})

test_strings = ["", "0", "1", "01", "10", "110", "1010", "000", "0011", "101"]
for s in test_strings:
    contains01 = "01" in s
    result = nfa.accepts(s)
    status = "OK" if result == contains01 else "MISMATCH"
    print(f"{s!r:8s} contains01={contains01!s:5s} nfa={result!s:5s} {status}")