গ্রেইবাখ নর্মাল ফর্ম

# হাতে-করা GNF রূপান্তর -- is_gnf checker ও derivation-length যাচাই
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 is_gnf(grammar):
    """প্রতিটি রুল A -> a-alpha শেপে কি না -- ঠিক একটি টার্মিনাল দিয়ে শুরু, তারপর শুধু ভেরিয়েবল"""
    for var, rhss in grammar.rules.items():
        for rhs in rhss:
            if var == grammar.S and rhs == ():
                continue
            if len(rhs) == 0 or rhs[0] not in grammar.T:
                return False, (var, rhs)
            if any(sym not in grammar.V for sym in rhs[1:]):
                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

def derive_leftmost(grammar, start, target, max_steps=60):
    queue = deque([((start,), [(start,)])])
    while queue:
        form, history = queue.popleft()
        if len(history) - 1 > max_steps:
            continue
        idx = next((i for i, sym in enumerate(form) if sym in grammar.V), None)
        if idx is None:
            if ''.join(form) == target:
                return history
            continue
        prefix = ''.join(form[:idx])
        if not target.startswith(prefix):
            continue
        var = form[idx]
        for rhs in grammar.rules.get(var, []):
            new_form = form[:idx] + rhs + form[idx + 1:]
            terms = []
            for s in new_form:
                if s in grammar.V:
                    break
                terms.append(s)
            if not target.startswith(''.join(terms)):
                continue
            if len(new_form) > len(target) + 6:
                continue
            queue.append((new_form, history + [new_form]))
    return None

def derivation_length_matches_string_length(grammar, start, string):
    """একটি স্ট্রিং derive করতে ঠিক len(string) ধাপ লাগে কি না -- GNF-এর দাবিকৃত বৈশিষ্ট্য"""
    hist = derive_leftmost(grammar, start, string, max_steps=len(string) + 2)
    if hist is None:
        return False, None
    steps = len(hist) - 1
    return steps == len(string), steps

# ---- সোর্স CNF গ্রামার, a^n b^n (n>=1) ----
rules_cnf = {
    'S': [('A', 'B'), ('A', 'C')],
    'A': [('a',)],
    'B': [('b',)],
    'C': [('S', 'B')],
}
G_cnf = Grammar({'S', 'A', 'B', 'C'}, {'a', 'b'}, rules_cnf, 'S')

# ---- হাতে-করা GNF (A প্রতিস্থাপিত, তাই আর রেফারেন্স হয় না -- L19 অনুযায়ী বাদ) ----
rules_gnf = {
    'S': [('a', 'B'), ('a', 'C')],
    'B': [('b',)],
    'C': [('a', 'B', 'B'), ('a', 'C', 'B')],
}
G_gnf = Grammar({'S', 'B', 'C'}, {'a', 'b'}, rules_gnf, 'S')

ok, bad = is_gnf(G_gnf)
print("is_gnf(G_gnf):", ok, bad)

lang_cnf = generate_language_up_to_length(G_cnf, 'S', 8)
lang_gnf = generate_language_up_to_length(G_gnf, 'S', 8)
print("L(CNF) length<=8:", sorted(lang_cnf, key=lambda w: (len(w), w)))
print("L(GNF) length<=8:", sorted(lang_gnf, key=lambda w: (len(w), w)))
print("ভাষা অভিন্ন:", lang_cnf == lang_gnf)

print()
for s in ["ab", "aabb", "aaabbb"]:
    matches, steps = derivation_length_matches_string_length(G_gnf, 'S', s)
    print(f"স্ট্রিং={s!r}  length={len(s)}  derivation ধাপ={steps}  মেলে={matches}")