কনটেক্সট-ফ্রি ল্যাঙ্গুয়েজের ক্লোজার প্রপার্টি

১ · CFL যেসব অপারেশনের নিচে ক্লোজড

ক্লোজার প্রপার্টিClosure Propertyএকটি নির্দিষ্ট অপারেশন কোনো ভাষা-শ্রেণির (যেমন CFL) সদস্যদের ওপর প্রয়োগ করলে ফলাফলও সেই একই শ্রেণিতে থাকে কি না, তা যাচাই করে। প্রশ্ন করে — একটি নির্দিষ্ট অপারেশন CFL-এর ওপর প্রয়োগ করলে ফলাফলও কি নিশ্চিতভাবে CFL হয়? M4-এর CFG-কম্বিনেশন টেকনিক দিয়ে সরাসরি প্রমাণ করা যায় CFL তিনটি অপারেশনের নিচে ক্লোজড —

• ইউনিয়ন: $L_1, L_2$ এর জন্য CFG $G_1=(V_1,\Sigma,R_1,S_1)$, $G_2=(V_2,\Sigma,R_2,S_2)$ থাকলে, একটি নতুন স্টার্ট সিম্বল $S$ যোগ করে $S \to S_1 \mid S_2$ রুল দিয়ে কম্বাইন্ড গ্রামার বানানো যায় — $L(G) = L_1 \cup L_2$।
• কনক্যাটেনেশন: একইভাবে $S \to S_1S_2$ — $L(G) = L_1L_2 = \{xy : x\in L_1, y\in L_2\}$।
• ক্লিনি স্টার: $S \to S_1S \mid \varepsilon$ — $L(G) = L_1^*$।

তিনটি ক্ষেত্রেই কৌশলটি একই — আলাদা গ্রামারের স্টার্ট সিম্বলগুলোকে একটি নতুন রুল দিয়ে জোড়া লাগানো, ঠিক যেভাবে L11-এ regex-কম্পোনেন্ট কম্বাইন করা হয়েছিল। যেহেতু $V_1, V_2$ ডিসজয়েন্ট রাখা যায় (দরকার হলে ভেরিয়েবল রিনেম করে), কম্বাইন্ড গ্রামারটি বৈধ থাকে।

২ · কেন ইন্টারসেকশন ও কমপ্লিমেন্টের নিচে CFL ক্লোজড নয়

এখানেই CFL রেগুলার ল্যাঙ্গুয়েজ (M3/L12) থেকে গুরুত্বপূর্ণভাবে আলাদা হয়ে যায়। রেগুলার ল্যাঙ্গুয়েজের ইন্টারসেকশন ক্লোজার DFA-প্রোডাক্ট কনস্ট্রাকশন দিয়ে প্রমাণ হয়েছিল — কিন্তু PDA-দের জন্য একই কৌশল খাটে না, কারণ দুটো PDA-এর স্ট্যাক একসাথে ট্র্যাক করতে গেলে একটিমাত্র স্ট্যাকের প্রয়োজন হয়, যা সাধারণভাবে সম্ভব নয়।

কমপ্লিমেন্ট: De Morgan's law থেকে সরাসরি অনুসরণ করে — $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$। যদি CFL কমপ্লিমেন্টের নিচে ক্লোজড হতো, তাহলে উপরের ইউনিয়ন-ক্লোজার (§১) এর সাথে মিলিয়ে CFL ইন্টারসেকশনের নিচেও ক্লোজড হয়ে যেত — কিন্তু আমরা এইমাত্র দেখলাম সেটা সত্যি নয়। সুতরাং, বিপরীতক্রমে (contrapositive), CFL কমপ্লিমেন্টের নিচে ক্লোজড হতে পারে না — একটি পরিষ্কার, পরোক্ষ (indirect) প্রমাণ যা আগে থেকে প্রতিষ্ঠিত সত্য পুনরায় ব্যবহার করে।

৩ · ব্যতিক্রম — রেগুলার ল্যাঙ্গুয়েজের সাথে ইন্টারসেকশন এখনও কাজ করে

যদিও CFL সাধারণ ইন্টারসেকশনের নিচে ক্লোজড নয়, একটি গুরুত্বপূর্ণ, ব্যবহারিকভাবে দরকারি বিশেষ ক্ষেত্র আছে — একটি CFL-কে যদি একটি রেগুলার ল্যাঙ্গুয়েজM2-M3-এ প্রতিষ্ঠিত, DFA/NFA দিয়ে চেনা ভাষার শ্রেণি-এর সাথে ইন্টারসেক্ট করা হয়, তাহলে ফলাফল আবারও CFL হয়। কারণ — একটি PDA (CFL-এর জন্য) এবং একটি DFA (রেগুলার ভাষার জন্য) একসাথে চালানো যায় — M3/L12-এর DFA-প্রোডাক্ট কনস্ট্রাকশনের সরাসরি সম্প্রসারণ — DFA-এর ফাইনাইট স্টেট সেট শুধু PDA-এর স্টেট সেটের সাথে মাল্টিপ্লাই হয় (স্ট্যাক অপরিবর্তিত থাকে, শুধু একটি স্ট্যাকই দরকার হয়) — accept হয় যখন উভয় কম্পোনেন্ট accept করে।

৪ · কোড: কাউন্টার-এক্সাম্পল কোড দিয়ে যাচাই

নিচের কোডে $L_1=\{a^nb^nc^m\}$ ও $L_2=\{a^mb^nc^n\}$-এর জন্য আলাদা CFG বানিয়ে, প্রতিটি একটি length bound পর্যন্ত জেনারেট করে, তাদের SET ইন্টারসেকশন হিসাব করে, এবং নিশ্চিত করা হচ্ছে ফলাফল ঠিক $\{a^nb^nc^n\}$-এর সাথে মিলে যায় — একটি জেনুইন, কোড-ভেরিফায়েড প্রমাণ, কোনো hardcoded ফলাফল নয়।

# CFL ইন্টারসেকশন-নন-ক্লোজারের কনক্রিট প্রমাণ
# G1: {a^n b^n c^m}  -- আগে সমান a-b জোড়া, তারপর স্বাধীনভাবে c
# G2: {a^m b^n c^n}  -- আগে স্বাধীনভাবে a, তারপর সমান b-c জোড়া

from collections import deque

def is_variable(sym, grammar):
    return sym in grammar

def generate_language_up_to_length(grammar, start, max_length):
    """L17-স্টাইলের BFS ডেরিভেশন-সার্চ -- প্রতিটি সেন্টেনশিয়াল ফর্মের
    বামতম ভেরিয়েবল এক্সপ্যান্ড করে, টার্মিনাল-কাউন্ট max_length ছাড়ালে prune করে।"""
    results = set()
    seen_forms = {(start,)}
    queue = deque([(start,)])
    while queue:
        form = queue.popleft()
        idx = next((i for i, s in enumerate(form) if is_variable(s, grammar)), None)
        if idx is None:
            s = ''.join(form)
            if len(s) <= max_length:
                results.add(s)
            continue
        var = form[idx]
        for production in grammar[var]:
            new_form = form[:idx] + tuple(production) + form[idx + 1:]
            terminal_count = sum(1 for s in new_form if not is_variable(s, grammar))
            if terminal_count > max_length:
                continue
            if new_form not in seen_forms:
                seen_forms.add(new_form)
                queue.append(new_form)
    return results

G1 = {                                    # {a^n b^n c^m : n,m >= 0}
    'S': [('A', 'C')],
    'A': [('a', 'A', 'b'), ()],
    'C': [('c', 'C'), ()],
}
G2 = {                                    # {a^m b^n c^n : n,m >= 0}
    'S': [('A', 'B')],
    'A': [('a', 'A'), ()],
    'B': [('b', 'B', 'c'), ()],
}

MAXLEN = 9
L1 = generate_language_up_to_length(G1, 'S', MAXLEN)
L2 = generate_language_up_to_length(G2, 'S', MAXLEN)
intersection = L1 & L2                    # আসল SET ইন্টারসেকশন

def is_anbncn(s):                         # L26-এর মেম্বারশিপ চেক -- CFG থেকে নয়, সরাসরি প্যাটার্ন-চেক
    if len(s) % 3 != 0:
        return False
    n = len(s) // 3
    return s == 'a' * n + 'b' * n + 'c' * n

expected = {s for s in (('a'*n + 'b'*n + 'c'*n) for n in range(0, MAXLEN // 3 + 1)) if len(s) <= MAXLEN}

print("L1 = {a^n b^n c^m} up to length", MAXLEN, "-- মোট", len(L1), "টি স্ট্রিং")
print("L2 = {a^m b^n c^n} up to length", MAXLEN, "-- মোট", len(L2), "টি স্ট্রিং")
print()
print("L1 ∩ L2 =", sorted(intersection, key=lambda s: (len(s), s)))
print("expected a^n b^n c^n =", sorted(expected, key=lambda s: (len(s), s)))
print()
print("সব intersection স্ট্রিং সত্যিই a^n b^n c^n প্যাটার্নের?", all(is_anbncn(s) for s in intersection))
print("L1 ∩ L2 == {a^n b^n c^n} ঠিক মিলে গেছে?", intersection == expected)