চমস্কি নর্মাল ফর্ম

# ধাপ ৫: isolate_terminals ও break_long_rules -- এবং সম্পূর্ণ পাইপলাইন
from collections import deque
import itertools

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

def isolate_terminals(grammar, counter=None):
    """যেকোনো length>=2 রুলে টার্মিনালকে একটি ফ্রেশ ভেরিয়েবলে বদলায় (A->aB হয় A->TaB, Ta->a)"""
    if counter is None:
        counter = itertools.count(1)
    new_rules = {v: list(rhss) for v, rhss in grammar.rules.items()}
    new_vars = set(grammar.V)
    term_vars = {}
    for var in list(new_rules.keys()):
        updated = []
        for rhs in new_rules[var]:
            if len(rhs) < 2:
                updated.append(rhs)
                continue
            new_rhs = []
            for sym in rhs:
                if sym in grammar.T:
                    if sym not in term_vars:
                        tv = f"T{next(counter)}"
                        term_vars[sym] = tv
                        new_vars.add(tv)
                    new_rhs.append(term_vars[sym])
                else:
                    new_rhs.append(sym)
            updated.append(tuple(new_rhs))
        new_rules[var] = updated
    for sym, tv in term_vars.items():
        new_rules[tv] = [(sym,)]
    return Grammar(new_vars, grammar.T, new_rules, grammar.S)

def break_long_rules(grammar, counter=None):
    """A -> B1 B2 ... Bk (k>2) কে A->B1 Y1, Y1->B2 Y2, ..., Y(k-2)->B(k-1)Bk চেইনে ভাঙে"""
    if counter is None:
        counter = itertools.count(1)
    new_rules = {}
    new_vars = set(grammar.V)
    for var, rhss in grammar.rules.items():
        updated = []
        for rhs in rhss:
            if len(rhs) <= 2:
                updated.append(rhs)
                continue
            symbols = list(rhs)
            chain_start = f"Y{next(counter)}"
            new_vars.add(chain_start)
            updated.append((symbols[0], chain_start))
            cur, i = chain_start, 1
            while i < len(symbols) - 2:
                nxt = f"Y{next(counter)}"
                new_vars.add(nxt)
                new_rules.setdefault(cur, []).append((symbols[i], nxt))
                cur, i = nxt, i + 1
            new_rules.setdefault(cur, []).append((symbols[i], symbols[i + 1]))
        new_rules[var] = updated
    return Grammar(new_vars, grammar.T, new_rules, grammar.S)

def is_cnf(grammar):
    for var, rhss in grammar.rules.items():
        for rhs in rhss:
            if var == grammar.S and rhs == ():
                continue
            if len(rhs) == 1 and rhs[0] in grammar.T:
                continue
            if len(rhs) == 2 and rhs[0] in grammar.V and rhs[1] in grammar.V:
                continue
            return False, (var, rhs)
    return True, None

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

# ---- মূল: ব্যালেন্সড বন্ধনী গ্রামার, S -> (S)S | epsilon ----
G0 = Grammar({'S'}, {'(', ')'}, {'S': [('(', 'S', ')', 'S'), ()]}, 'S')

# ধাপ ১+২ (concrete, এই নির্দিষ্ট গ্রামারের জন্য): নতুন স্টার্ট S0, S-এর নিজস্ব
# ε-প্রোডাকশন বাদ দিয়ে (S)S-এর প্রতিটি S-occurrence অপশনালি সরানোর সব কম্বিনেশন যোগ
rules1 = {
    'S0': [('S',), ()],
    'S':  [('(', 'S', ')', 'S'), ('(', ')', 'S'), ('(', 'S', ')'), ('(', ')')],
}
G1 = Grammar({'S0', 'S'}, {'(', ')'}, rules1, 'S0')

# ধাপ ৩: unit প্রোডাকশন S0->S বাদ -- S-এর রুল সরাসরি S0-তে কপি
rules2 = {
    'S0': [('(', 'S', ')', 'S'), ('(', ')', 'S'), ('(', 'S', ')'), ('(', ')'), ()],
    'S':  [('(', 'S', ')', 'S'), ('(', ')', 'S'), ('(', 'S', ')'), ('(', ')')],
}
G2 = Grammar({'S0', 'S'}, {'(', ')'}, rules2, 'S0')
# ধাপ ৪ (L19): S0, S উভয়ই জেনারেটিং ও রিচেবল -- কিছু বাদ দেওয়ার প্রয়োজন নেই

# ধাপ ৫: টার্মিনাল আইসোলেট, তারপর লম্বা রুল ভাঙা
G3 = isolate_terminals(G2)
G4 = break_long_rules(G3)

ok, bad = is_cnf(G4)
print("is_cnf(চূড়ান্ত গ্রামার):", ok, bad)

lang_orig = generate_language_up_to_length(G0, 'S', 6)
lang_cnf = generate_language_up_to_length(G4, 'S0', 6)
print("L(মূল) length<=6:", sorted(lang_orig, key=lambda w: (len(w), w)))
print("L(CNF)  length<=6:", sorted(lang_cnf, key=lambda w: (len(w), w)))
print("ভাষা অভিন্ন:", lang_orig == lang_cnf)

# ---- উদাহরণ ২: A -> aBcD (টার্মিনাল ও একাধিক ভেরিয়েবলের মিশ্রণ) ----
G5 = Grammar({'A', 'B', 'D'}, {'a', 'c'}, {'A': [('a', 'B', 'c', 'D')], 'B': [('a',)], 'D': [('c',)]}, 'A')
G5 = isolate_terminals(G5)
G5 = break_long_rules(G5)
ok5, bad5 = is_cnf(G5)
print("\nA->aBcD উদাহরণ, is_cnf:", ok5, bad5)
for v, rhss in G5.rules.items():
    print(" ", v, "->", ' | '.join(''.join(r) if r else 'ε' for r in rhss))