PDA ও CFG ইকুইভ্যালেন্স

# L24 -- CFG -> PDA কনস্ট্রাকশন, L17-স্টাইল CFG জেনারেশনের বিপরীতে সমতা verify করা
import itertools

# ---- L17-স্টাইল Grammar (ব্যালেন্সড বন্ধনী: S -> (S)S | epsilon) ----
grammar = {
    "S": [["(", "S", ")", "S"], []],   # [] মানে S -> epsilon
}
start_symbol = "S"


def generate_language_up_to_length(grammar, start, max_length):
    """leftmost-derivation sentential form-এর উপর BFS, দৈর্ঘ্য-বাউন্ড পর্যন্ত টার্মিনাল স্ট্রিং জমা করে"""
    variables = set(grammar.keys())
    language = set()
    seen = {(start,)}
    frontier = [(start,)]
    while frontier:
        new_frontier = []
        for form in frontier:
            idx = next((i for i, sym in enumerate(form) if sym in variables), None)
            if idx is None:
                s = "".join(form)
                if len(s) <= max_length:
                    language.add(s)
                continue
            var = form[idx]
            for rhs in grammar[var]:
                new_form = form[:idx] + tuple(rhs) + form[idx + 1:]
                terminal_len = sum(1 for sym in new_form if sym not in variables)
                if terminal_len > max_length:
                    continue
                if new_form not in seen:
                    seen.add(new_form)
                    new_frontier.append(new_form)
        frontier = new_frontier
    return language


lang = generate_language_up_to_length(grammar, start_symbol, 6)
print("CFG-জেনারেটেড ব্যালেন্সড-বন্ধনী স্ট্রিং (দৈর্ঘ্য <=6):", sorted(lang, key=lambda s: (len(s), s)))


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

    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 accepts_by_empty_stack(self, string):
        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 len(stack) == 0:
                return True
            for nxt in self._moves(state, remaining, stack):
                if nxt not in seen:
                    seen.add(nxt)
                    frontier.append(nxt)
        return False


def cfg_to_pda(grammar, start_symbol, terminal_alphabet):
    """CFG -> PDA: একটিমাত্র স্টেট, স্ট্যাক নিজেই বর্তমান sentential form ধরে রাখে --
    ভ্যারিয়েবল নন-ডিটারমিনিস্টিকভাবে rule অনুযায়ী expand হয়, টার্মিনাল ইনপুটের সাথে সরাসরি মেলে।"""
    variables = set(grammar.keys())
    stack_alphabet = variables | set(terminal_alphabet)
    delta = {}
    for var, rules in grammar.items():
        delta[("q", None, var)] = [("q", tuple(rhs)) for rhs in rules]   # rhs push, leftmost টপে
    for a in terminal_alphabet:
        delta[("q", a, a)] = [("q", ())]   # ইনপুট সিম্বল == স্ট্যাক-টপ টার্মিনাল হলে দুটোই pop/consume
    return PDA({"q"}, set(terminal_alphabet), stack_alphabet, delta, "q", start_symbol)


pda = cfg_to_pda(grammar, start_symbol, {"(", ")"})

# দৈর্ঘ্য 6 পর্যন্ত {(,)}-এর উপর সব সম্ভাব্য স্ট্রিং (member + non-member সবগুলো) টেস্ট করা হচ্ছে
MAX_LEN = 6
mismatches = []
tested = 0
for length in range(0, MAX_LEN + 1):
    for combo in itertools.product("()", repeat=length):
        s = "".join(combo)
        tested += 1
        cfg_member = s in lang
        pda_member = pda.accepts_by_empty_stack(s)
        if cfg_member != pda_member:
            mismatches.append((s, cfg_member, pda_member))

print(f"\nমোট {tested}টি স্ট্রিং টেস্ট করা হয়েছে (দৈর্ঘ্য {MAX_LEN} পর্যন্ত সবগুলো)।")
print("অমিল পাওয়া গেছে:", mismatches)
print("CFG-PDA সমতা নিশ্চিত হলো:", len(mismatches) == 0)