DFA — ফরমাল ডেফিনিশন ও ল্যাঙ্গুয়েজ অ্যাকসেপ্টেন্স

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

L01-এ আমরা একটি অ্যাডহক DFA প্রিভিউ দেখেছিলাম (dict দিয়ে transitions)। এখন M2-এর প্রথম পাঠে সেটিকে ফরমালাইজ করছি। DFADeterministic Finite Automatonএকটি ৫-টাপল (Q, Σ, δ, q0, F) যেখানে δ প্রতিটি (state, symbol) জোড়ার জন্য ঠিক একটি (সবসময় সংজ্ঞায়িত) পরবর্তী স্টেট দেয়। (Deterministic Finite Automaton) ফরমালি একটি ৫-টাপল —

$$M = (Q, \Sigma, \delta, q_0, F)$$

• $Q$ — স্টেটের একটি ফাইনাইট সেট
• $\Sigma$ — ইনপুট আলফাবেট (L02)
• $\delta: Q \times \Sigma \to Q$ — ট্রানজিশন ফাংশন, একটি টোটাল ফাংশন — প্রতিটি $(q, a) \in Q \times \Sigma$ জোড়ার জন্য সংজ্ঞায়িত ("ডিটারমিনিস্টিক" মানে ঠিক একটি, সবসময়-সংজ্ঞায়িত পরবর্তী স্টেট)
• $q_0 \in Q$ — স্টার্ট স্টেট
• $F \subseteq Q$ — accepting/final স্টেটের সেট

২ · Extended Transition Function $\hat\delta$

$\delta$ শুধু একটি সিম্বল প্রসেস করে। পুরো একটি স্ট্রিং প্রসেস করতে দরকার extended transition function $\hat\delta$Extended Transition Functionδ-কে পুরো স্ট্রিং প্রসেস করার জন্য সম্প্রসারিত রূপ, স্ট্রিং length-এর উপর স্ট্রাকচারাল ইনডাকশনে সংজ্ঞায়িত। — L03-এর স্ট্রাকচারাল ইনডাকশন কাঠামো অনুযায়ী ঠিক সংজ্ঞায়িত —

$$\hat\delta(q, \varepsilon) = q \qquad \text{(base case)}$$ $$\hat\delta(q, wa) = \delta(\hat\delta(q, w), a) \qquad \text{(inductive case)}$$

অর্থাৎ — স্ট্রিং $w$-এর শেষ সিম্বল $a$ বাদে বাকিটুকু ($w$) প্রসেস করে যে স্টেটে পৌঁছানো যায়, সেখান থেকে $a$ পড়ে এক ধাপ আরও এগোনো। বারবার এই সংজ্ঞা প্রয়োগ করলে পুরো স্ট্রিং, সিম্বল-বাই-সিম্বল, প্রসেস হয়ে যায়।

৩ · DFA-এর ল্যাঙ্গুয়েজ ও Regular ভাষা

একটি DFA $M$-এর ল্যাঙ্গুয়েজ —

$$L(M) = \{w \in \Sigma^* : \hat\delta(q_0, w) \in F\}$$

অর্থাৎ, $q_0$ থেকে শুরু করে $w$ প্রসেস করলে যে স্ট্রিংগুলো একটি accept স্টেটে গিয়ে শেষ হয়, তাদের সবার সেট। এখন L05-এর "সমস্যা = ল্যাঙ্গুয়েজ" রিফ্রেমিং মনে করুন — $L(M)$ হলো ঠিক সেই ডিসিশন প্রবলেম যা $M$ "সমাধান করে।" একটি ভাষা $L$-কে regular বলা হয় যদি কোনো DFA $M$-এর জন্য $L(M) = L$ হয় — এটিই M2-M3-এর কেন্দ্রীয় সংজ্ঞা, যার উপর বাকি সব প্রপার্টি (M3), সমতুল্যতা (M2/L08, L11) ও সীমাবদ্ধতা (M3/L13-L14) প্রমাণিত হবে।

৪ · Python-এ একটি ফরমাল DFA ক্লাস

নিচের কোড সেলে ৫-টাপল সংজ্ঞা হুবহু মিলিয়ে একটি DFA ক্লাস — টোটালিটি কনস্ট্রাক্টরেই যাচাই করা হচ্ছে (কনস্ট্রাকশনের সময় assert করা হয় প্রতিটি (state, symbol) জোড়ার জন্য একটি ট্রানজিশন সংজ্ঞায়িত আছে)। L01-এর "জোড়-সংখ্যক 1" ভাষাটি এখন ফরমালি এই ক্লাস দিয়ে বানানো হচ্ছে, এবং একটি সম্পূর্ণ ভিন্ন দ্বিতীয় ভাষা — "01 দিয়ে শেষ হওয়া স্ট্রিং।"

class DFA:
    """(Q, Sigma, delta, q0, F) -- purno formal DFA definition"""
    def __init__(self, states, alphabet, transitions, start_state, accept_states):
        self.states = set(states)
        self.alphabet = set(alphabet)
        self.transitions = transitions          # dict: (state, symbol) -> state
        self.start_state = start_state
        self.accept_states = set(accept_states)
        # totality jachai -- delta protita (state, symbol) jorar jonno songjayito thakte hobe
        for q in self.states:
            for a in self.alphabet:
                if (q, a) not in self.transitions:
                    raise ValueError(f"osomponno DFA -- delta({q!r},{a!r}) songjayito nei (totality longhito)")

    def extended_delta(self, string):
        """delta-hat(q0, w) gonona kore -- base case: delta-hat(q,e)=q,
        inductive case: delta-hat(q,wa)=delta(delta-hat(q,w),a)"""
        state = self.start_state
        for symbol in string:
            if symbol not in self.alphabet:
                raise ValueError(f"'{symbol}' ei DFA-r alphabet-e nei")
            state = self.transitions[(state, symbol)]
        return state

    def accepts(self, string):
        return self.extended_delta(string) in self.accept_states


# L01-er 'jor-shonkhok 1' bhasha, ekhon formal DFA class diye
even_ones_dfa = DFA(
    states={'q0', 'q1'},
    alphabet={'0', '1'},
    transitions={
        ('q0', '0'): 'q0', ('q0', '1'): 'q1',
        ('q1', '0'): 'q1', ('q1', '1'): 'q0',
    },
    start_state='q0',
    accept_states={'q0'},
)

# ekti notun, alada bhasha -- '01' die shesh hoya string
ends_in_01_dfa = DFA(
    states={'r0', 'r1', 'r2'},
    alphabet={'0', '1'},
    transitions={
        ('r0', '0'): 'r1', ('r0', '1'): 'r0',
        ('r1', '0'): 'r1', ('r1', '1'): 'r2',
        ('r2', '0'): 'r1', ('r2', '1'): 'r0',
    },
    start_state='r0',
    accept_states={'r2'},
)

test_strings = ["", "0", "1", "01", "10", "0101", "1100", "111", "010101"]

print(f"{'w':10s} | even-1s DFA | ends-in-01 DFA")
print("-" * 45)
for w in test_strings:
    r1 = even_ones_dfa.accepts(w)
    r2 = ends_in_01_dfa.accepts(w)
    print(f"{w!r:10s} | {str(r1):11s} | {r2}")