কনটেক্সট-ফ্রি ল্যাঙ্গুয়েজের ডিসিশন প্রপার্টি

# CNF গ্রামার: ব্যালেন্সড বন্ধনী, S -> (S)S | eps থেকে সঠিকভাবে CNF-এ কনভার্ট করা
# ধাপ ১: নতুন স্টার্ট S0 -> S | eps  (S0 কখনো কোনো রুলের ডানদিকে থাকে না)
# ধাপ ২: S-এর নিজস্ব eps-প্রোডাকশন সাবস্টিটিউশন দিয়ে বাদ দেওয়া: S -> (S)S | ()S | (S) | ()
# ধাপ ৩: টার্মিনাল আইসোলেট করা ও লম্বা রুল চেইনে ভাঙা (L20-এর ধাপ)
from collections import deque

_S_RULES = [('T_open', 'X1'), ('T_open', 'Y1'), ('T_open', 'Z1'), ('T_open', 'T_close')]
CNF = {
    'S0': _S_RULES + [()],        # S0: S-এর ইউনিট-প্রোডাকশন বাদ দিয়ে সরাসরি + eps
    'S':  list(_S_RULES),          # S নিজে কখনো eps জেনারেট করে না (eps শুধু S0-তে)
    'X1': [('S', 'X2')],
    'X2': [('T_close', 'S')],
    'Y1': [('T_close', 'S')],
    'Z1': [('S', 'T_close')],
    'T_open':  [('(',)],
    'T_close': [(')',)],
}
START = 'S0'

def is_variable(sym, grammar):
    return sym in grammar

def is_cnf(grammar, start):
    """যাচাই করে প্রতিটি রুল A->BC অথবা A->a আকৃতির, শুধু start-এর eps ছাড়া,
    আর start কখনো কোনো রুলের ডানদিকে নেই।"""
    for var, prods in grammar.items():
        for prod in prods:
            if len(prod) == 0:
                if var != start:
                    return False
            elif len(prod) == 1:
                if is_variable(prod[0], grammar):
                    return False
            elif len(prod) == 2:
                if not (is_variable(prod[0], grammar) and is_variable(prod[1], grammar)):
                    return False
            else:
                return False
    return True

print("is_cnf(CNF):", is_cnf(CNF, START))

def cyk_membership(grammar, start, w):
    """আসল CYK ডায়নামিক-প্রোগ্রামিং টেবিল-ফিলিং অ্যালগরিদম -- table[i][l] =
    পজিশন i থেকে শুরু, দৈর্ঘ্য l সাবস্ট্রিং জেনারেট করতে পারে এমন ভেরিয়েবলের সেট।"""
    n = len(w)
    if n == 0:
        return () in grammar.get(start, [])
    table = [[set() for _ in range(n + 1)] for _ in range(n)]
    for i in range(n):                                   # বেস কেস: দৈর্ঘ্য ১
        for var, prods in grammar.items():
            for prod in prods:
                if len(prod) == 1 and prod[0] == w[i]:
                    table[i][1].add(var)
    for length in range(2, n + 1):                        # ইনডাক্টিভ কেস: দৈর্ঘ্য ২..n
        for i in range(0, n - length + 1):
            for split in range(1, length):
                left = table[i][split]
                right = table[i + split][length - split]
                if not left or not right:
                    continue
                for var, prods in grammar.items():
                    for prod in prods:
                        if len(prod) == 2 and prod[0] in left and prod[1] in right:
                            table[i][length].add(var)
    return start in table[0][n]

def derive_leftmost_search(grammar, start, target, max_steps=50000):
    """একটি স্বাধীন, সম্পূর্ণ ভিন্ন কৌশল -- BFS ডেরিভেশন-সার্চ -- CYK-এর ক্রস-ভেরিফিকেশনের জন্য।"""
    queue = deque([(start,)])
    seen = {(start,)}
    steps = 0
    while queue and steps < max_steps:
        steps += 1
        form = queue.popleft()
        idx = next((i for i, s in enumerate(form) if is_variable(s, grammar)), None)
        if idx is None:
            if ''.join(form) == target:
                return True
            continue
        if sum(1 for s in form if not is_variable(s, grammar)) > len(target):
            continue
        for production in grammar[form[idx]]:
            new_form = form[:idx] + tuple(production) + form[idx + 1:]
            if new_form not in seen:
                seen.add(new_form)
                queue.append(new_form)
    return False

test_strings = ["", "()", "(())", "()()", "(()())", "(", ")(", "(()", "((()))", "(()))("]
print("\nস্ট্রিং        | CYK   | derivation-search | মিলেছে?")
all_agree = True
for s in test_strings:
    cyk_result = cyk_membership(CNF, START, s)
    deriv_result = derive_leftmost_search(CNF, START, s)
    agree = cyk_result == deriv_result
    all_agree = all_agree and agree
    print(f"{s!r:14s} | {str(cyk_result):5s} | {str(deriv_result):18s} | {agree}")
print("\nসবগুলো মিলেছে:", all_agree)