কনটেক্সট-ফ্রি গ্রামার — ফরমাল ডেফিনিশন ও ডেরিভেশন

# CFG-এর ফরমাল সংজ্ঞা কোডে -- একটি real Grammar ক্লাস ও leftmost-derivation-search
from collections import deque

class Grammar:
    def __init__(self, variables, terminals, rules, start):
        self.V = set(variables)   # V -- ভেরিয়েবল (নন-টার্মিনাল)
        self.T = set(terminals)   # Sigma -- টার্মিনাল অ্যালফাবেট
        self.rules = rules        # R -- dict: variable -> RHS-সিকোয়েন্সের লিস্ট
        self.S = start            # S -- স্টার্ট ভেরিয়েবল

def derive_leftmost(grammar, start, target, max_steps=200):
    """সবচেয়ে বামের ভেরিয়েবল বারবার এক্সপ্যান্ড করে (BFS সহ) S =>* target -- সত্যিকারের derivation খোঁজে"""
    init = (start,)
    queue = deque([(init, [init])])
    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):        # ফাইনালাইজড 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) + 5:   # গ্রোথ বাউন্ড -- অতিরিক্ত বড় ব্রাঞ্চ prune
                continue
            queue.append((new_form, history + [new_form]))
    return None

def generate_language_up_to_length(grammar, start, max_length):
    """S থেকে সব সম্ভাব্য derivation BFS করে L(G)-কে length bound পর্যন্ত exhaustively জেনারেট করে"""
    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

# ব্যালেন্সড বন্ধনী গ্রামার -- G = (V, Sigma, R, S)
V, T = {'S'}, {'(', ')'}
rules = {'S': [('(', 'S', ')', 'S'), ()]}   # S -> (S)S | epsilon
G = Grammar(V, T, rules, 'S')

target = "(())()"
history = derive_leftmost(G, 'S', target)
print(f"টার্গেট স্ট্রিং: {target!r}\n")
print("খুঁজে পাওয়া leftmost derivation:")
for i, form in enumerate(history):
    shown = ''.join(form) if form else 'ε'
    print(f"  ধাপ {i}: {shown}")

print()
lang = generate_language_up_to_length(G, 'S', 6)
print(f"L(G), length <= 6 পর্যন্ত ({len(lang)}টি স্ট্রিং):")
print(sorted(lang, key=lambda w: (len(w), w)))