চমস্কি হায়ারার্কি

# অংশ ১ -- চারটি টাইপের রেফারেন্স টেবিল

chomsky_types = {
    "Type 0 (Unrestricted)":        {"automaton": "Turing Machine",           "pl_relevance": "তাত্ত্বিক সীমা -- সরাসরি PL সিনট্যাক্সে ব্যবহৃত হয় না"},
    "Type 1 (Context-Sensitive)":   {"automaton": "Linear-Bounded Automaton", "pl_relevance": "বিরল -- কিছু semantic constraint বোঝাতে উল্লেখ করা হয়, সিনট্যাক্সে নয়"},
    "Type 2 (Context-Free)":        {"automaton": "Pushdown Automaton",       "pl_relevance": "M5 -- বাস্তব PL সিনট্যাক্সের মূল ভিত্তি"},
    "Type 3 (Regular)":             {"automaton": "Finite Automaton",         "pl_relevance": "M4 -- লেক্সিক্যাল/টোকেন প্যাটার্নের ভিত্তি"},
}

print("চমস্কি হায়ারার্কি রেফারেন্স টেবিল:\n")
for typ, info in chomsky_types.items():
    print(f"  {typ:32s} → {info['automaton']:24s} | {info['pl_relevance']}")

# অংশ ২ -- Type 3 (regular) checker: "a*b*" -- শূন্য বা বেশি a, তারপর শূন্য বা বেশি b
def matches_a_star_b_star(s):
    seen_b = False
    for ch in s:
        if ch == 'a':
            if seen_b:
                return False   # b এসে যাওয়ার পর আবার a -- অবৈধ
        elif ch == 'b':
            seen_b = True
        else:
            return False
    return True

# অংশ ৩ -- একটি "bounded-state" checker: একটি ফাইনাইট অটোমাটার মতোই সসীম (max_depth+2 টি) স্টেট ব্যবহার করে
def fixed_depth_paren_checker(s, max_depth):
    depth = 0
    for ch in s:
        if ch == '(':
            depth += 1
            if depth > max_depth:
                return False   # স্টেট স্পেস ফুরিয়ে গেছে -- আর গভীরতা গুনতে পারছে না
        elif ch == ')':
            depth -= 1
            if depth < 0:
                return False
    return depth == 0

# অংশ ৪ -- একটি stack-based checker: unbounded গভীরতা সঠিকভাবে ট্র্যাক করতে পারে
def stack_based_paren_checker(s):
    stack = []
    for ch in s:
        if ch == '(':
            stack.append(ch)
        elif ch == ')':
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

print("\n--- Type 3 (regular) checker: a*b* ---")
for test in ["", "aaa", "bbb", "aaabbb", "aba", "abab"]:
    print(f"  matches_a_star_b_star({test!r:10s}) = {matches_a_star_b_star(test)}")

print("\n--- গভীরভাবে নেস্টেড balanced parentheses: bounded বনাম stack ---")
deep = "(" * 8 + ")" * 8   # ৮ স্তর গভীর নেস্টিং
print(f"  টেস্ট স্ট্রিং: {'(' * 8}{')' * 8}  (৮ স্তর গভীর)")
print(f"  fixed_depth_paren_checker(deep, max_depth=5) = {fixed_depth_paren_checker(deep, max_depth=5)}   -- সসীম স্টেট (৫) ফুরিয়ে গেছে, ভুল করে reject!")
print(f"  fixed_depth_paren_checker(deep, max_depth=8) = {fixed_depth_paren_checker(deep, max_depth=8)}    -- এবার যথেষ্ট স্টেট আছে বলে সঠিকভাবে accept")
print(f"  stack_based_paren_checker(deep)               = {stack_based_paren_checker(deep)}    -- স্ট্যাক unbounded, তাই যেকোনো গভীরতায় সঠিক")

deeper = "(" * 20 + ")" * 20   # আরও গভীর -- ২০ স্তর
print(f"\n  আরও গভীর টেস্ট (২০ স্তর): fixed_depth_paren_checker(deeper, max_depth=8) = {fixed_depth_paren_checker(deeper, max_depth=8)} (আবারও ফুরিয়ে গেছে)")
print(f"  stack_based_paren_checker(deeper)             = {stack_based_paren_checker(deeper)}    -- এখনও সঠিক, কোনো fixed limit নেই")