কনটেক্সট-সেনসিটিভ গ্রামার ও লিনিয়ার বাউন্ডেড অটোমাটা

১ · কনটেক্সট-সেনসিটিভ গ্রামার — দুই সমতুল্য সংজ্ঞা

L17-এর CFG রুল $A \to \alpha$-এ ভেরিয়েবল $A$ যেকোনো কনটেক্সটে থাকলেই রিপ্লেস করা যায় — "কনটেক্সট-ফ্রি" নামটার উৎস ঠিক এখানেই। কনটেক্সট-সেনসিটিভ গ্রামারContext-Sensitive Grammarএকটি গ্রামার যার প্রতিটি রুলে একটি ভেরিয়েবল শুধু একটি নির্দিষ্ট বাম-ডান কনটেক্সটে থাকলেই রিপ্লেস করা যায়। (CSG, Type 1) এই স্বাধীনতা সরিয়ে নেয় — প্রতিটি রুল এই আকৃতির:

$$\alpha A \beta \to \alpha\gamma\beta \quad \text{যেখানে } \gamma \neq \varepsilon$$

অর্থাৎ ভেরিয়েবল $A$ শুধু তখনই $\gamma$ দিয়ে রিপ্লেস করা যায় যখন এটি বাম দিকে ঠিক $\alpha$ ও ডান দিকে ঠিক $\beta$ দিয়ে ঘেরা থাকে — "context-sensitive" নামের উৎস।

একটি সমতুল্য, অনেক সময় বেশি ব্যবহারিক বিকল্প সংজ্ঞা আছে — নন-কন্ট্রাক্টিং (noncontracting) গ্রামার: প্রতিটি রুল $\alpha \to \beta$ এই শর্ত মেনে চলে —

$$|\beta| \geq |\alpha|$$

অর্থাৎ ডেরাইভড স্ট্রিং কখনো ছোট হয় না, শুধু বড় হতে পারে বা একই দৈর্ঘ্যে থাকতে পারে। এই দুই সংজ্ঞা প্রমাণযোগ্যভাবে সমতুল্য (mention only — বিস্তারিত প্রমাণ এই পাঠের সুযোগের বাইরে)। এই কোর্স "নন-কন্ট্রাক্টিং" রূপটি ব্যবহার করবে, কারণ এটি কোডে ডিরেক্টলি চেক করা সহজ।

২ · লিনিয়ার বাউন্ডেড অটোমাটা (LBA)

লিনিয়ার বাউন্ডেড অটোমাটাLinear Bounded Automaton (LBA)একটি টুরিং-মেশিন-সদৃশ যন্ত্র যার টেপ ব্যবহার ইনপুটের দৈর্ঘ্যেই সীমাবদ্ধ -- অতিরিক্ত টেপ ব্যবহার করা যায় না। হলো একটি টুরিং-মেশিন-সদৃশ যন্ত্র (সম্পূর্ণ ফরমাল সংজ্ঞা M8/L32-এ, কিন্তু LBA-কে এখানেই introduce করা হচ্ছে কারণ চমস্কি হায়ারার্কিতে ঠিক এটাই এর জায়গা) যার টেপ ঠিক ইনপুটের দৈর্ঘ্যে সীমাবদ্ধ — ইনপুটের বাইরে অতিরিক্ত টেপ ব্যবহার করতে পারে না, M8-এর আনরেস্ট্রিক্টেড, অসীম-টেপ টুরিং মেশিনের সরাসরি বৈপরীত্যে।

থিওরেম (L08-এর NFA=DFA ও L24-এর CFG=PDA-এর ঠিক CSG-LBA অ্যানালগ): একটি ভাষা কনটেক্সট-সেনসিটিভ হয় যদি এবং শুধুমাত্র যদি কোনো LBA সেটি চেনে। এই থিওরেমটাই চমস্কি হায়ারার্কির প্রতিটি স্তরের "গ্রামার ⇔ অটোমাটা" প্যাটার্নের ধারাবাহিকতা — regular⇔DFA (M2), context-free⇔PDA (M4-M5), এখন context-sensitive⇔LBA (M7)।

৩ · কেন CSG মেম্বারশিপ ডিসাইডেবল — বাউন্ডেড টেপের সরাসরি পরিণতি

এখানেই একটি genuinely গুরুত্বপূর্ণ, forward-looking সত্য দাঁড় করানো যায়। যেহেতু একটি LBA-এর টেপ ইনপুট দৈর্ঘ্যে সীমাবদ্ধ, তার সম্ভাব্য কনফিগারেশনএকটি মুহূর্তে যন্ত্রের সম্পূর্ণ অবস্থা — বর্তমান স্টেট, টেপের বিষয়বস্তু, ও হেড-এর অবস্থান — একসাথে-এর সংখ্যা ফাইনাইট (যদিও সম্ভবত বিশাল)। LBA সিমুলেট করার সময় — যেহেতু ফাইনাইট কনফিগারেশন — মেশিন হয় accept করবে, reject করবে, অথবা একটি কনফিগারেশন পুনরাবৃত্তি (repeat) করবে (যা detectable, তাই "infinite loop" ধরা পড়ে যায়, একে reject হিসেবে গণ্য করা যায়)। এর মানে — মেশিন কখনোই সত্যিকারভাবে চিরকাল নতুন, unrepeat-হওয়া কনফিগারেশনে চলতে পারে না — মেম্বারশিপ প্রশ্ন সবসময় একটি নির্দিষ্ট সময়ে ডিসাইড করা যায়।

৪ · CFG বনাম CSG — একটি তুলনা

নিচের কোডে CFG ও CSG-এর মূল বৈশিষ্ট্যগুলো পাশাপাশি তুলনা করা একটি রেফারেন্স টেবিল বানানো হয়েছে, এবং $\{a^nb^nc^n : n \geq 1\}$-এর জন্য একটি real CSG বানিয়ে তার ওপর একটি জেনুইন derivation-search চালানো হয়েছে — L26 প্রমাণ করেছিল এই ভাষা context-free নয়; এখানেই ঠিক দেখানো হচ্ছে কেন Type 1-এ এক ধাপ ওপরে ওঠা দরকার হয়েছিল এই ভাষা জেনারেট করতে।

# CFG বনাম CSG -- মূল বৈশিষ্ট্যের তুলনা টেবিল
comparison = {
    'CFG (Type 2)': {
        'rule_form': 'A -> alpha  (একটি ভেরিয়েবল, যেকোনো কনটেক্সটে রিপ্লেসযোগ্য)',
        'growth_property': 'কন্ট্রাক্টিং অনুমোদিত (A -> eps সম্ভব)',
        'recognizing_automaton': 'PDA (M5)',
        'example_language': '{0^n 1^n}  -- L14/L22',
    },
    'CSG (Type 1)': {
        'rule_form': 'alpha A beta -> alpha gamma beta  (কনটেক্সট-নির্ভর)',
        'growth_property': 'নন-কন্ট্রাক্টিং -- |beta| >= |alpha| সবসময়',
        'recognizing_automaton': 'Linear Bounded Automaton (এই পাঠ)',
        'example_language': '{a^n b^n c^n}  -- L26-এ context-free নয় প্রমাণিত',
    },
}
for grammar_type, features in comparison.items():
    print(grammar_type)
    for key, value in features.items():
        print("   ", key, ":", value)
    print()

# {a^n b^n c^n : n >= 1}-এর জন্য একটি real CSG (নন-কন্ট্রাক্টিং রুল)
#   S  -> a S B C
#   S  -> a B C
#   CB -> BC
#   aB -> ab
#   bB -> bb
#   bC -> bc
#   cC -> cc
RULES = [
    (('S',), ('a', 'S', 'B', 'C')),
    (('S',), ('a', 'B', 'C')),
    (('C', 'B'), ('B', 'C')),
    (('a', 'B'), ('a', 'b')),
    (('b', 'B'), ('b', 'b')),
    (('b', 'C'), ('b', 'c')),
    (('c', 'C'), ('c', 'c')),
]
START = ('S',)

from collections import deque

def csg_can_derive(rules, start, target_string, max_len_bound, max_steps=200000):
    """BFS স্ট্রিং-রিরাইটিং সার্চ -- start থেকে ঠিক target_string ডেরাইভ করা যায় কি না।
    সব রুল নন-কন্ট্রাক্টিং (RHS দৈর্ঘ্য >= LHS দৈর্ঘ্য) বলে, দৈর্ঘ্য টার্গেটের চেয়ে বড় হয়ে গেলে
    আর কখনো ছোট হবে না -- তাই দৈর্ঘ্য-ভিত্তিক pruning নিরাপদ।"""
    target = tuple(target_string)
    queue = deque([start])
    seen = {start}
    steps = 0
    while queue and steps < max_steps:
        steps += 1
        form = queue.popleft()
        if form == target:
            return True
        if len(form) > max_len_bound:
            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 and len(new_form) <= max_len_bound:
                        seen.add(new_form)
                        queue.append(new_form)
    return False

print("CSG দিয়ে 'aabbcc' (a^2b^2c^2) ডেরাইভ করা যায়?", csg_can_derive(RULES, START, "aabbcc", max_len_bound=6))
print("CSG দিয়ে 'aabbc' (ভুল প্যাটার্ন) ডেরাইভ করা যায়?", csg_can_derive(RULES, START, "aabbc", max_len_bound=6))
print("CSG দিয়ে 'abc' (a^1b^1c^1) ডেরাইভ করা যায়?", csg_can_derive(RULES, START, "abc", max_len_bound=3))