CFG সিমপ্লিফিকেশন — অপ্রয়োজনীয় সিম্বল ও প্রোডাকশন

# find_generating_symbols, find_reachable_symbols, remove_useless_symbols -- সঠিক ক্রমে
from collections import deque

class Grammar:
    def __init__(self, variables, terminals, rules, start):
        self.V = set(variables)
        self.T = set(terminals)
        self.rules = rules
        self.S = start

def find_generating_symbols(grammar):
    """fixed-point: A জেনারেটিং যদি তার কোনো রুল সম্পূর্ণভাবে টার্মিনাল ও ইতিমধ্যে-জানা জেনারেটিং সিম্বল দিয়ে তৈরি"""
    generating = set()
    changed = True
    while changed:
        changed = False
        for var, rhss in grammar.rules.items():
            if var in generating:
                continue
            for rhs in rhss:
                if all((sym in grammar.T) or (sym in generating) for sym in rhs):
                    generating.add(var)
                    changed = True
                    break
    return generating

def find_reachable_symbols(grammar, start):
    """S থেকে BFS -- গ্রামারের রুলকে একটি রেফারেন্স গ্রাফ হিসেবে ট্র্যাভার্স করে"""
    reachable = {start}
    queue = deque([start])
    while queue:
        var = queue.popleft()
        for rhs in grammar.rules.get(var, []):
            for sym in rhs:
                if sym in grammar.V and sym not in reachable:
                    reachable.add(sym)
                    queue.append(sym)
    return reachable

def _restrict_rules(grammar, keep_vars):
    new_rules = {}
    for var, rhss in grammar.rules.items():
        if var not in keep_vars:
            continue
        kept = [rhs for rhs in rhss if all((s in grammar.T) or (s in keep_vars) for s in rhs)]
        if kept:
            new_rules[var] = kept
    return new_rules

def remove_useless_symbols(grammar):
    """সঠিক ক্রম: generating আগে, তারপর অবশিষ্ট গ্রামারে reachability"""
    generating = find_generating_symbols(grammar)
    gen_rules = _restrict_rules(grammar, generating | grammar.T)
    gen_grammar = Grammar(generating, grammar.T, gen_rules, grammar.S)
    reachable = find_reachable_symbols(gen_grammar, grammar.S)
    final_vars = generating & reachable
    final_rules = _restrict_rules(gen_grammar, final_vars | grammar.T)
    return Grammar(final_vars, grammar.T, final_rules, grammar.S)

def generate_language_up_to_length(grammar, start, max_length):
    result = set()
    queue = deque([(start,)])
    seen = {(start,)}
    while queue:
        form = queue.popleft()
        if sum(1 for s in form if s not in grammar.V) > max_length:
            continue
        idx = next((i for i, sym in enumerate(form) if sym in grammar.V), None)
        if idx is None:
            if len(form) <= max_length:
                result.add(''.join(form))
            continue
        var = form[idx]
        for rhs in grammar.rules.get(var, []):
            new_form = form[:idx] + rhs + form[idx + 1:]
            if sum(1 for s in new_form if s not in grammar.V) > max_length:
                continue
            if new_form in seen:
                continue
            seen.add(new_form)
            queue.append(new_form)
    return result

# ডেলিবারেটলি: B রিচেবল কিন্তু কখনো জেনারেট করে না (কোনো base case নেই);
# A জেনারেটিং কিন্তু সঠিক-ক্রম সিমপ্লিফিকেশনের পর আর রিচেবল থাকবে না
V = {'S', 'A', 'B'}
T = {'a', 'b'}
rules = {
    'S': [('A', 'B'), ('a',)],
    'A': [('b',)],
    'B': [('b', 'B')],
}
G = Grammar(V, T, rules, 'S')

print("generating:", find_generating_symbols(G))
print("reachable (মূল গ্রামারে):", find_reachable_symbols(G, 'S'))

simplified = remove_useless_symbols(G)
print("\nসঠিক ক্রমে সিমপ্লিফাই করার পর:")
print("  ভেরিয়েবল:", simplified.V)
print("  রুল:", simplified.rules)

lang_before = generate_language_up_to_length(G, 'S', 5)
lang_after = generate_language_up_to_length(simplified, 'S', 5)
print("\nL(মূল গ্রামার) length<=5:", sorted(lang_before))
print("L(সিমপ্লিফায়েড) length<=5:", sorted(lang_after))
print("ভাষা অপরিবর্তিত:", lang_before == lang_after)