আনরেস্ট্রিক্টেড গ্রামার ও টাইপ-০ ল্যাঙ্গুয়েজ

# চারটি চমস্কি টাইপের সম্পূর্ণ, পাশাপাশি তুলনা (L04-এর রোডম্যাপ এখন সম্পূর্ণ ভরাট)
chomsky_types = {
    'Type 3 (Regular)': {
        'rule_restriction': 'A -> aB অথবা A -> a  (right-linear)',
        'recognizing_automaton': 'DFA / NFA (M2)',
        'closure_under_complement': 'হ্যাঁ (L12)',
        'membership_decidable': 'হ্যাঁ, দ্রুত (L06/L16)',
    },
    'Type 2 (Context-Free)': {
        'rule_restriction': 'A -> alpha  (একক ভেরিয়েবল, alpha অবাধ)',
        'recognizing_automaton': 'PDA (M5)',
        'closure_under_complement': 'না (L27)',
        'membership_decidable': 'হ্যাঁ, CYK দিয়ে পলিনমিয়াল টাইম (L28)',
    },
    'Type 1 (Context-Sensitive)': {
        'rule_restriction': 'alpha A beta -> alpha gamma beta, gamma != eps',
        'recognizing_automaton': 'Linear Bounded Automaton (এই মডিউল, L29)',
        'closure_under_complement': 'হ্যাঁ (উন্নত ফলাফল, mention only)',
        'membership_decidable': 'হ্যাঁ, কিন্তু সম্ভাব্য ধীর (L29)',
    },
    'Type 0 (Unrestricted)': {
        'rule_restriction': 'alpha -> beta, alpha-তে >=1 ভেরিয়েবল, beta সম্পূর্ণ অবাধ',
        'recognizing_automaton': 'টুরিং মেশিন (M8)',
        'closure_under_complement': 'না (টুরিং-রিকগনাইজেবল কমপ্লিমেন্টের নিচে ক্লোজড নয়, M9)',
        'membership_decidable': 'না -- সাধারণভাবে আনডিসাইডেবল (forward-ref M9/L38-L39)',
    },
}
for type_name, features in chomsky_types.items():
    print(type_name)
    for key, value in features.items():
        print("   ", key, ":", value)
    print()

# একটি তুলনামূলকভাবে ছোট Type-0 গ্রামার {a^n b^n : n >= 0}-এর জন্য, ইচ্ছাকৃতভাবে
# একটি CONTRACTING রুল ব্যবহার করছে (XY -> eps, RHS দৈর্ঘ্য LHS-এর চেয়ে ছোট) --
# এটি CSG-তে (L29) সম্পূর্ণ নিষিদ্ধ, কিন্তু Type 0-তে সম্পূর্ণ বৈধ
RULES = [
    (('S',), ('a', 'S', 'b')),
    (('S',), ('X', 'Y')),
    (('X', 'Y'), ()),          # <-- কন্ট্রাক্টিং রুল: LHS দৈর্ঘ্য ২, RHS দৈর্ঘ্য ০
]
START = ('S',)

from collections import deque

def type0_derive_search(rules, start, target_string, max_steps=200000, max_form_len=12):
    """সাধারণ BFS স্ট্রিং-রিরাইটিং সার্চ -- এখন কন্ট্রাক্টিং রুলও থাকতে পারে,
    তাই L29-এর মতো দৈর্ঘ্য-ভিত্তিক pruning নিরাপদ নয় -- একটি সাধারণ max_form_len ক্যাপ ব্যবহার করা হচ্ছে।"""
    target = tuple(target_string)
    queue = deque([(start, [])])
    seen = {start}
    steps = 0
    while queue and steps < max_steps:
        steps += 1
        form, path = queue.popleft()
        if form == target:
            return path
        if len(form) > max_form_len:
            continue
        for lhs, rhs in rules:
            L = len(lhs)
            for i in range(0, len(form) - L + 1):
                if form[i:i + L] == lhs:
                    new_form = form[:i] + rhs + form[i + L:]
                    if new_form not in seen:
                        seen.add(new_form)
                        queue.append((new_form, path + [(form, lhs, rhs, new_form)]))
    return None

for w in ["", "ab", "aabb", "aaabbb"]:
    path = type0_derive_search(RULES, START, w)
    print(f"ডেরাইভ '{w}':", "পাওয়া গেছে" if path else "পাওয়া যায়নি", f"({len(path)} ধাপে)" if path else "")
    if path:
        for (form, lhs, rhs, new_form) in path:
            print("    ", ''.join(form), "--[", ''.join(lhs), "->", ''.join(rhs) or 'eps', "]-->", ''.join(new_form))