PDA অ্যাকসেপ্টেন্স — ফাইনাল স্টেট বনাম এম্পটি স্ট্যাক

# L23 -- final-state বনাম empty-stack PDA অ্যাকসেপ্টেন্স, সমতা কনক্রিটলি verify করা

class PDA:
    def __init__(self, states, input_alphabet, stack_alphabet, delta, start_state, start_stack, accept_states=None):
        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 or set()

    def _moves(self, state, remaining_input, stack):
        moves = []
        if not stack:
            return moves
        top = stack[-1]
        for (new_state, push) in self.delta.get((state, None, top), []):
            new_stack = list(stack[:-1])
            new_stack.extend(reversed(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 _reachable_configs(self, string):
        start_config = (self.start_state, string, (self.start_stack,))
        seen = {start_config}
        frontier = [start_config]
        while frontier:
            state, remaining, stack = frontier.pop()
            yield (state, remaining, stack)
            for nxt in self._moves(state, remaining, stack):
                if nxt not in seen:
                    seen.add(nxt)
                    frontier.append(nxt)

    def accepts_by_final_state(self, string):
        return any(remaining == "" and state in self.accept_states
                   for (state, remaining, stack) in self._reachable_configs(string))

    def accepts_by_empty_stack(self, string):
        return any(remaining == "" and len(stack) == 0
                   for (state, remaining, stack) in self._reachable_configs(string))


# --- এম্পটি-স্ট্যাক PDA for L = {0^n 1^n}, কোনো accept state দরকার নেই ---
es_delta = {
    ("q0", "0", "Z0"): [("q0", ("X", "Z0"))],
    ("q0", "0", "X"): [("q0", ("X", "X"))],
    ("q0", "1", "X"): [("q1", ())],
    ("q1", "1", "X"): [("q1", ())],
    ("q0", None, "Z0"): [("q0", ())],   # খালি স্ট্রিং: সরাসরি বটম-মার্কার pop
    ("q1", None, "Z0"): [("q1", ())],   # সব X pop হয়ে গেলে বটম-মার্কারও pop -> স্ট্যাক খালি
}
es_pda = PDA({"q0", "q1"}, {"0", "1"}, {"Z0", "X"}, es_delta, "q0", "Z0", accept_states=set())


def convert_to_final_state_acceptance(empty_stack_pda):
    """স্ট্যান্ডার্ড কনস্ট্রাকশন: empty-stack PDA -> সমতুল্য final-state PDA।
    নতুন বটম-মার্কার X0 এবং নতুন স্টেট q0', qf যোগ করা হয়।"""
    new_start, new_accept, X0 = "q0__NEW", "qf__NEW", "X0__NEW"
    new_states = set(empty_stack_pda.states) | {new_start, new_accept}
    new_stack_alphabet = set(empty_stack_pda.stack_alphabet) | {X0}
    new_delta = {k: list(v) for k, v in empty_stack_pda.delta.items()}

    new_delta[(new_start, None, X0)] = [(empty_stack_pda.start_state,
                                          (empty_stack_pda.start_stack, X0))]
    for q in empty_stack_pda.states:
        new_delta.setdefault((q, None, X0), []).append((new_accept, (X0,)))

    return PDA(new_states, empty_stack_pda.input_alphabet, new_stack_alphabet, new_delta,
               new_start, X0, accept_states={new_accept})


fs_pda = convert_to_final_state_acceptance(es_pda)

print("স্ট্রিং      | এম্পটি-স্ট্যাক | কনভার্টেড ফাইনাল-স্টেট | মিলছে?")
print("-" * 60)
all_match = True
for s in ["0011", "000111", "", "10", "0011000", "0111"]:
    a = es_pda.accepts_by_empty_stack(s)
    b = fs_pda.accepts_by_final_state(s)
    all_match = all_match and (a == b)
    print(f"{s!r:12s} | {a!s:14s} | {b!s:22s} | {a == b}")
print("\nসবগুলো মিলেছে (সমতা নিশ্চিত):", all_match)