ডিটারমিনিস্টিক বনাম নন-ডিটারমিনিস্টিক PDA

# L25 -- ডিটারমিনিস্টিক বনাম নন-ডিটারমিনিস্টিক PDA, কনফিগারেশন-কাউন্ট দিয়ে verify

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
        self.start_state = start_state
        self.start_stack = start_stack
        self.accept_states = accept_states

    def _eps_moves(self, state, stack):
        if not stack:
            return []
        top = stack[-1]
        moves = []
        for (ns, push) in self.delta.get((state, None, top), []):
            new_stack = list(stack[:-1]); new_stack.extend(reversed(push))
            moves.append((ns, tuple(new_stack)))
        return moves

    def _sym_moves(self, state, stack, a):
        if not stack:
            return []
        top = stack[-1]
        moves = []
        for (ns, push) in self.delta.get((state, a, top), []):
            new_stack = list(stack[:-1]); new_stack.extend(reversed(push))
            moves.append((ns, tuple(new_stack)))
        return moves

    def _eps_close(self, configs):
        frontier, closure = list(configs), set(configs)
        while frontier:
            state, stack = frontier.pop()
            for cfg in self._eps_moves(state, stack):
                if cfg not in closure:
                    closure.add(cfg); frontier.append(cfg)
        return closure

    def _has_symbol_move(self, state, top):
        return any((state, a, top) in self.delta for a in self.input_alphabet)

    def _settled(self, configs):
        """একটি কনফিগারেশন 'transient' (উপেক্ষাযোগ্য) যদি তার একমাত্র সম্ভাব্য মুভ হয় একটি
        ε-মুভ (কোনো প্রতিদ্বন্দ্বী সিম্বল-মুভ ছাড়া) -- সেটি কোনো প্রকৃত 'চয়েস' নয়, শুধু
        যান্ত্রিকভাবে পরের কনফিগারেশনে গড়িয়ে যাওয়া। ε-মুভ এবং সিম্বল-মুভ একসাথে থাকলে
        সেটাই প্রকৃত ফর্ক -- তখন কনফিগারেশনটি গণনায় থেকে যায়।"""
        settled = set()
        for (s, st) in configs:
            top = st[-1] if st else None
            has_eps = top is not None and (s, None, top) in self.delta
            has_sym = top is not None and self._has_symbol_move(s, top)
            if not (has_eps and not has_sym):
                settled.add((s, st))
        return settled

    def trace(self, string):
        """প্রতিটি ইনপুট সিম্বল consume করার পর কতগুলো distinct সমান্তরাল কনফিগারেশন
        জীবিত আছে তা রিটার্ন করে -- (non)determinism-এর কনক্রিট প্রমাণ।"""
        configs = self._eps_close({(self.start_state, (self.start_stack,))})
        sizes = [len(self._settled(configs))]
        for a in string:
            nxt = set()
            for (state, stack) in configs:
                nxt.update(self._sym_moves(state, stack, a))
            configs = self._eps_close(nxt)
            sizes.append(len(self._settled(configs)))
        accepted = any(s in self.accept_states for (s, st) in configs)
        return accepted, sizes


def is_deterministic_pda(pda):
    """স্ট্রাকচারাল DPDA চেক: কোনো (state, stack-top)-এ ε-মুভ ও সিম্বল-মুভ একসাথে নয়,
    এবং কোনো (state, symbol, stack-top)-এর একাধিক গন্তব্য নয়।"""
    by_state_top = {}
    for (state, sym, top), dests in pda.delta.items():
        if len(dests) > 1:
            return False
        by_state_top.setdefault((state, top), []).append(sym)
    return all(not (None in syms and len(syms) > 1) for syms in by_state_top.values())


# --- ডিটারমিনিস্টিক PDA: L = {0^n 1^n} -- কোনো কনফিগারেশনেই একের বেশি মুভ নেই ---
det_delta = {
    ("q0", "0", "Z0"): [("qread0", ("X", "Z0"))],
    ("qread0", "0", "X"): [("qread0", ("X", "X"))],
    ("qread0", "1", "X"): [("qread1", ())],
    ("qread1", "1", "X"): [("qread1", ())],
    ("qread1", None, "Z0"): [("qacc", ("Z0",))],
}
det_pda = PDA({"q0", "qread0", "qread1", "qacc"}, {"0", "1"}, {"Z0", "X"},
              det_delta, "q0", "Z0", {"q0", "qacc"})

print("=== ডিটারমিনিস্টিক 0^n1^n PDA ===")
for s in ["0011", "000111", "", "10", "0011000", "0111"]:
    acc, sizes = det_pda.trace(s)
    print(f"  {s!r:10s} accept={acc!s:5s} প্রতি-ধাপে-কনফিগ={sizes} max={max(sizes)}")
print("is_deterministic_pda(det_pda):", is_deterministic_pda(det_pda))

# --- নন-ডিটারমিনিস্টিক PDA: L = {w w^R} -- মাঝপথ গেস করে (epsilon fork) ---
pal_delta = {
    ("push", "0", "Z0"): [("push", ("0", "Z0"))], ("push", "1", "Z0"): [("push", ("1", "Z0"))],
    ("push", "0", "0"): [("push", ("0", "0"))],   ("push", "0", "1"): [("push", ("0", "1"))],
    ("push", "1", "0"): [("push", ("1", "0"))],   ("push", "1", "1"): [("push", ("1", "1"))],
    ("push", None, "Z0"): [("pop", ("Z0",))],     # নন-ডিটারমিনিস্টিক গেস: এটাই মাঝপথ
    ("push", None, "0"): [("pop", ("0",))],
    ("push", None, "1"): [("pop", ("1",))],
    ("pop", "0", "0"): [("pop", ())],  ("pop", "1", "1"): [("pop", ())],
    ("pop", None, "Z0"): [("acc", ("Z0",))],
}
pal_pda = PDA({"push", "pop", "acc"}, {"0", "1"}, {"Z0", "0", "1"},
              pal_delta, "push", "Z0", {"acc"})

print("\n=== নন-ডিটারমিনিস্টিক w-w^R প্যালিনড্রোম PDA ===")
for s in ["0110", "1001", "", "0101", "0010", "111"]:
    acc, sizes = pal_pda.trace(s)
    print(f"  {s!r:10s} accept={acc!s:5s} প্রতি-ধাপে-কনফিগ={sizes} max={max(sizes)}")
print("is_deterministic_pda(pal_pda):", is_deterministic_pda(pal_pda))