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

১ · PDA কেন NFA-এর চেয়ে বেশি শক্তিশালী

M2-M3-এ দেখা DFA/NFAফিক্সড, ফাইনাইট সংখ্যক স্টেট দিয়ে গঠিত মেশিন — কোনো অতিরিক্ত মেমরি নেই-এর একটি মৌলিক সীমাবদ্ধতা আছে — এদের কাছে শুধু ফাইনাইট সংখ্যক স্টেট আছে, তাই এরা কোনো কিছু "গুনতে" পারে না যদি সেই গণনার সম্ভাব্য মান অসীম হয়। এই কারণেই L14-এ প্রমাণিত হয়েছিল $L = \{0^n1^n : n \geq 0\}$ রেগুলার নয় — কোনো DFA-ই "কতগুলো 0 পড়েছি" মনে রাখতে পারে না যখন $n$ যেকোনো মান নিতে পারে।

পুশডাউন অটোমাটাPushdown Automaton (PDA)একটি NFA যাতে একটি আনবাউন্ডেড স্ট্যাক (LIFO মেমরি) যোগ করা হয়েছে — কনটেক্সট-ফ্রি ল্যাঙ্গুয়েজ (M4) স্বীকৃতির জন্য এটিই স্ট্যান্ডার্ড মেশিন। ঠিক এই সীমাবদ্ধতা দূর করে — একটি স্ট্যাকStack — LIFO (Last-In-First-Out) ডেটা স্ট্রাকচার, ../dsa/-এর Stack ADT-এর সাথে সরাসরি সম্পর্কিত যোগ করে দিলে মেশিনটি এখন অসীম পর্যন্ত "গুনতে" পারে (প্রতিটি 0-এর জন্য একটি মার্কার push করে) — এটিই ঠিক সেই বাড়তি ক্ষমতা যা রেগুলার ল্যাঙ্গুয়েজ থেকে কনটেক্সট-ফ্রি ল্যাঙ্গুয়েজে (M4-M6) উন্নীত করে। L26-এ CFL-এর জন্যও একটি পাম্পিং লেমা দেখা যাবে, ঠিক এই কারণেই।

২ · ফরমাল সংজ্ঞা — ৬-টাপল

একটি PDA ফরমালি একটি ৬-টাপল:

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

যেখানে —

• $Q$ — ফাইনাইট সংখ্যক স্টেটের সেট (DFA/NFA-এর মতোই)।
• $\Sigma$ — ইনপুট আলফাবেট।
• $\Gamma$ — স্ট্যাক আলফাবেট (যেসব সিম্বল push/pop করা যায় — $\Sigma$ থেকে সম্পূর্ণ আলাদা হতে পারে, প্রায়ই একটি বাড়তি "বটম মার্কার" সিম্বলও থাকে)।
• $q_0 \in Q$ — শুরু স্টেট, এবং $F \subseteq Q$ — accepting স্টেটসমূহ।
• $\delta$ — ট্রানজিশন ফাংশন, DFA/NFA-এর চেয়ে বেশি জটিল:

$$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$$

অর্থাৎ প্রতিটি ট্রানজিশন একসাথে তিনটি জিনিসের উপর নির্ভর করে — বর্তমান স্টেট, একটি ইনপুট সিম্বল (অথবা ε দিয়ে কিছুই না পড়ে), এবং স্ট্যাকের বর্তমান টপ সিম্বল (যা বাধ্যতামূলকভাবে pop হয়) — এবং ফলাফল হিসেবে একটি নতুন স্টেট আর একটি স্ট্রিং $\Gamma^*$ দেয় যা push করা হবে (popped সিম্বলের জায়গায়)। শূন্য সিম্বল push করলে সেটা নিছক pop-ই থেকে যায়; একাধিক সিম্বল push করলে স্ট্যাকে একসাথে কয়েকটি সিম্বল যোগ হয়।

৩ · কনফিগারেশন — কম্পিউটেশনের একটি স্ন্যাপশট

একটি কনফিগারেশনConfigurationPDA-এর কম্পিউটেশনের একটি সম্পূর্ণ instantaneous স্ন্যাপশট — (বর্তমান স্টেট, বাকি থাকা ইনপুট, বর্তমান স্ট্যাক কনটেন্ট) হলো একটি ট্রিপল — (বর্তমান স্টেট, বাকি থাকা ইনপুট, বর্তমান স্ট্যাক কনটেন্ট)। একটি সম্পূর্ণ কম্পিউটেশন হলো এমন কনফিগারেশনের একটি সিকোয়েন্স, প্রতিটি ধাপ $\delta$-এর কোনো একটি বৈধ ট্রানজিশন অনুসরণ করে পরবর্তী কনফিগারেশনে যায়। যেহেতু নন-ডিটারমিনিজম আছে, তাই একটি ইনপুটের জন্য একাধিক সমান্তরাল কনফিগারেশন একই সাথে সম্ভব হতে পারে — একটি স্ট্রিং accept হয় যদি অন্তত একটি কম্পিউটেশন পাথ পুরো ইনপুট consume করে একটি accept স্টেটে পৌঁছায় (L07-এর NFA "সব সম্ভাব্য স্টেট একসাথে ট্র্যাক করা" কৌশলের সাথে সরাসরি সম্পর্কিত, এখন স্ট্যাক-সহ)।

৪ · Python-এ একটি সত্যিকারের PDA

নিচের কোড সেলে একটি real PDA ক্লাস — একটি genuine Python list-কে স্ট্যাক হিসেবে ব্যবহার করে (push = append, pop = pop — সরাসরি ../dsa/-এর Stack ADT অপারেশন) — এবং accepts মেথড সব সম্ভাব্য সমান্তরাল কনফিগারেশন ট্র্যাক করে (একটি সেট, L07-এর NFA কৌশলের সাধারণীকরণ, এখন স্ট্যাক-কনটেন্টসহ)। এই PDA-টি $L = \{0^n1^n : n \geq 0\}$ accept করার জন্য বানানো — প্রতিটি 0-এর জন্য একটি $X$ push করে, প্রতিটি 1-এর জন্য একটি $X$ pop করে, এবং ইনপুট শেষ হওয়ার সময় স্ট্যাকে শুধু বটম-মার্কার $Z_0$ বাকি থাকলে (অর্থাৎ সব $X$ ঠিক জোড়ায় জোড়ায় মিলে গেছে) accept করে।

# একটি সত্যিকারের PDA -- L = { 0^n 1^n : n >= 0 }, ফাইনাল-স্টেট অ্যাকসেপ্টেন্স

class PDA:
    def __init__(self, states, input_alphabet, stack_alphabet, delta, start_state, start_stack, accept_states):
        self.states = states
        self.input_alphabet = input_alphabet
        self.stack_alphabet = stack_alphabet
        self.delta = delta   # dict: (state, symbol_or_None, stack_top) -> [(new_state, push_tuple), ...]
        self.start_state = start_state
        self.start_stack = start_stack   # bottom-of-stack marker
        self.accept_states = accept_states

    def _moves(self, state, remaining_input, stack):
        """genuine Python list স্ট্যাক থেকে top pop করে সব সম্ভাব্য (state, input, stack) মুভ বের করে"""
        moves = []
        if not stack:
            return moves
        top = stack[-1]   # স্ট্যাকের টপ = list-এর শেষ উপাদান
        for (new_state, push) in self.delta.get((state, None, top), []):   # epsilon মুভ
            new_stack = list(stack[:-1])          # top pop
            new_stack.extend(reversed(push))       # push -- বাম দিকের সিম্বল টপে থাকবে
            moves.append((new_state, remaining_input, tuple(new_stack)))
        if remaining_input:
            a = remaining_input[0]
            for (new_state, push) in self.delta.get((state, a, top), []):   # সিম্বল পড়ে মুভ
                new_stack = list(stack[:-1])
                new_stack.extend(reversed(push))
                moves.append((new_state, remaining_input[1:], tuple(new_stack)))
        return moves

    def accepts(self, string):
        """সব সম্ভাব্য সমান্তরাল কনফিগারেশন ট্র্যাক করে -- অন্তত একটি accept স্টেটে পৌঁছালেই accept"""
        start_config = (self.start_state, string, (self.start_stack,))
        seen = {start_config}
        frontier = [start_config]
        while frontier:
            state, remaining, stack = frontier.pop()
            if remaining == "" and state in self.accept_states:
                return True
            for nxt in self._moves(state, remaining, stack):
                if nxt not in seen:
                    seen.add(nxt)
                    frontier.append(nxt)
        return False


states = {"q0", "q1", "qf"}
input_alphabet = {"0", "1"}
stack_alphabet = {"Z0", "X"}
delta = {
    ("q0", "0", "Z0"): [("q0", ("X", "Z0"))],   # push X, Z0 নিচে থাকবে
    ("q0", "0", "X"): [("q0", ("X", "X"))],     # push X, আরেকটা X-এর উপর
    ("q0", "1", "X"): [("q1", ())],             # pop X (প্রথম 1 দেখলে)
    ("q1", "1", "X"): [("q1", ())],             # প্রতিটি পরবর্তী 1-এ pop X
    ("q0", None, "Z0"): [("qf", ("Z0",))],      # খালি স্ট্রিং হলে সরাসরি accept
    ("q1", None, "Z0"): [("qf", ("Z0",))],      # সব X pop হয়ে গেলে accept
}
pda = PDA(states, input_alphabet, stack_alphabet, delta, "q0", "Z0", {"qf"})

accept_tests = ["0011", "000111", ""]
reject_tests = ["10", "0011000", "0111"]

print("ACCEPT হওয়া উচিত:")
for s in accept_tests:
    print(f"  {s!r:10s} -> {pda.accepts(s)}")

print("REJECT হওয়া উচিত:")
for s in reject_tests:
    print(f"  {s!r:10s} -> {pda.accepts(s)}")