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

১ · CFL পাম্পিং লেমার বিবৃতি

M3/L13 রেগুলার ল্যাঙ্গুয়েজের জন্য একটি পাম্পিং লেমা দিয়েছিল — এখন M4-M5-এ CFL নিয়ে কাজ করার পর, একই ধরনের কিন্তু আরও জটিল একটি প্রপার্টি CFL-এর জন্যও প্রমাণ করা যায়:

যদি $L$ কনটেক্সট-ফ্রি হয়, তাহলে একটি পাম্পিং লেংথPumping lengthএকটি নির্দিষ্ট সংখ্যা $p$, ভাষা $L$-এর উপর নির্ভরশীল, যার চেয়ে বড় দৈর্ঘ্যের প্রতিটি স্ট্রিং পাম্পিং প্রপার্টি মেনে চলতে বাধ্য $p \geq 1$ আছে যেন প্রতিটি স্ট্রিং $s \in L$ যেখানে $|s| \geq p$, সেটিকে পাঁচ ভাগে ভাগ করা যায় $s = uvxyz$, যা নিচের শর্তগুলো মেনে চলে:

• (১) $|vy| > 0$ (দুটো পাম্পড অংশের অন্তত একটি খালি নয়)
• (২) $|vxy| \leq p$ (মাঝের তিন অংশ একসাথে $p$-এর মধ্যে সীমাবদ্ধ)
• (৩) সব $i \geq 0$-এর জন্য, $uv^ixy^iz \in L$ ($v$ আর $y$ — দুটোকেই একইসাথে, একই সংখ্যকবার — "পাম্প" করলেও ফলাফল $L$-এই থেকে যায়)

$$\forall s \in L, |s| \geq p \implies \exists\, u,v,x,y,z: s=uvxyz \land |vy|>0 \land |vxy|\leq p \land \forall i\geq 0, uv^ixy^iz \in L$$

২ · কেন এটি সত্য — পার্স ট্রি-এর উচ্চতা ও Pigeonhole

L13-এ যুক্তিটি ছিল DFA-এর ফিক্সড সংখ্যক স্টেট নিয়ে — লম্বা স্ট্রিং মানেই কোনো স্টেট পুনরায় ভিজিট হবে (pigeonhole)। CFL-এর জন্য যুক্তিটি একইরকম, কিন্তু এবার পার্স ট্রি-এর উচ্চতা নিয়ে কাজ করে:

যথেষ্ট লম্বা স্ট্রিং-এর জন্য, তার CFG পার্স ট্রি (CNF-আকারে, L20 — যা নিশ্চিত করে প্রতিটি ইন্টারনাল নোডের ঠিক দুটো চাইল্ড আছে) root থেকে leaf পর্যন্ত এমন একটি পাথ ধারণ করবে যার দৈর্ঘ্য গ্রামারের মোট ভ্যারিয়েবল সংখ্যার চেয়ে বেশি — pigeonhole অনুযায়ী, সেই পাথে কোনো ভ্যারিয়েবল অবশ্যই পুনরাবৃত্তি হবে। সেই পুনরাবৃত্ত ভ্যারিয়েবলের দুটো occurrence-এর মাঝের subtree-টি "পাম্পযোগ্য" — একটি occurrence-এর subtree অন্যটির জায়গায় বসিয়ে দিলে (duplicate বা remove করে) একটি নতুন বৈধ পার্স ট্রি পাওয়া যায়। এই subtree-এর দ্বারা উৎপন্ন অংশই $v$ (বামে) আর $y$ (ডানে), আর তার ভেতরের অংশ $x$।

৩ · প্রমাণ — $a^nb^nc^n$ কনটেক্সট-ফ্রি নয়

L18-এর গ্রামার-ভিত্তিক উদাহরণে $a^nb^nc^n$ দেখা গিয়েছিল "inherently ambiguous" প্রসঙ্গে। এখন CFL পাম্পিং লেমা দিয়ে দেখানো যাক এই ভাষাটি আসলে কনটেক্সট-ফ্রিই নয়:

• (১) ধরে নিন $L = \{a^nb^nc^n : n \geq 0\}$ কনটেক্সট-ফ্রি — তাহলে একটি পাম্পিং লেংথ $p$ থাকতেই হবে।
• (২) নির্বাচন করুন $s = a^pb^pc^p \in L$, যার দৈর্ঘ্য $3p \geq p$।
• (৩) যেকোনো বৈধ বিভাজন $s = uvxyz$ শর্ত $|vxy| \leq p$ মেনে — এর মানে $vxy$ ব্লকটি $a$, $b$, $c$ — তিনটি symbol-block-এর সবগুলোতে একসাথে বিস্তৃত হতে পারবে না (কারণ প্রতিটি ব্লকের দৈর্ঘ্য $p$, আর তিনটি ব্লক মিলিয়ে দৈর্ঘ্য $3p$, কিন্তু $vxy \leq p$ হওয়ায় এটি সর্বোচ্চ দুটি সংলগ্ন ব্লক স্পর্শ করতে পারে)।
• (৪) পাম্পিং (যেমন $i=2$, দ্বিগুণ করা) তাই হয় কিছু symbol-এর সংখ্যা বাড়িয়ে দেবে অন্যগুলো অপরিবর্তিত রেখে — $a,b,c$-এর সংখ্যার সমতা ভেঙে যাবে — contradiction, যেহেতু $L$ ধরে নেওয়া হয়েছিল $n=n=n$ ভাষা।
• (৫) সিদ্ধান্ত: $L = \{a^nb^nc^n\}$ কনটেক্সট-ফ্রি নয়।

৪ · Python-এ Exhaustive Split-Checking

নিচের কোড সেলে একটি সত্যিকারের check_cfl_pumping_violation ফাংশন — একটি নির্দিষ্ট $s$ ও claimed $p$-এর জন্য প্রতিটি সম্ভাব্য বৈধ পাঁচ-ভাগ বিভাজন ($|vxy|\leq p$, $|vy|>0$ শর্ত মেনে) enumerate করে, এবং প্রতিটির জন্য $i=2$ দিয়ে পাম্প করে $a^nb^nc^n$-এ membership হারায় কিনা যাচাই করে — এটি হাতে-বাছাই করা একটি বিভাজন নয়, বরং সব সম্ভাব্য বিভাজনের উপর একটি সম্পূর্ণ, exhaustive যাচাই।

# L26 -- CFL পাম্পিং লেমা, a^n b^n c^n কনটেক্সট-ফ্রি নয় তার exhaustive প্রমাণ

def is_anbncn(s):
    """L = {a^n b^n c^n : n >= 0}-এর জন্য মেম্বারশিপ চেকার -- regex ছাড়া, সরাসরি স্ক্যান"""
    i, n = 0, len(s)
    a_count = 0
    while i < n and s[i] == "a":
        a_count += 1; i += 1
    b_count = 0
    while i < n and s[i] == "b":
        b_count += 1; i += 1
    c_count = 0
    while i < n and s[i] == "c":
        c_count += 1; i += 1
    if i != n:          # ক্রম ভুল থাকলে (a*b*c* না হলে)
        return False
    return a_count == b_count == c_count


def all_five_way_splits(s, p):
    """s = uvxyz -- |vxy| <= p এবং |vy| > 0 শর্ত মানা সব সম্ভাব্য বিভাজন yield করে"""
    n = len(s)
    for vxy_start in range(0, n + 1):
        max_vxy_len = min(p, n - vxy_start)
        for vxy_len in range(0, max_vxy_len + 1):
            vxy_end = vxy_start + vxy_len
            u, vxy, z = s[:vxy_start], s[vxy_start:vxy_end], s[vxy_end:]
            for v_len in range(0, vxy_len + 1):
                for y_len in range(0, vxy_len - v_len + 1):
                    x_len = vxy_len - v_len - y_len
                    if v_len + y_len == 0:
                        continue   # শর্ত (1): |vy| > 0
                    v = vxy[:v_len]
                    x = vxy[v_len:v_len + x_len]
                    y = vxy[v_len + x_len:]
                    yield (u, v, x, y, z)


def check_cfl_pumping_violation(s, p, membership_fn, i=2):
    """s-এর প্রতিটি বৈধ পাঁচ-ভাগ বিভাজনে i=2 দিয়ে পাম্প করে membership ভাঙে কিনা চেক করে।
    রিটার্ন করে (সবগুলো বিভাজনই violate করেছে কিনা, মোট কতগুলো বিভাজন, প্রথম ব্যতিক্রম আছে কি)।"""
    total = 0
    non_violating = None
    for (u, v, x, y, z) in all_five_way_splits(s, p):
        total += 1
        pumped = u + v * i + x + y * i + z
        if membership_fn(pumped) and non_violating is None:
            non_violating = (u, v, x, y, z, pumped)   # প্রমাণ ভেঙে যাবে যদি এটি ঘটে
    return (non_violating is None, total, non_violating)


for p in (2, 3, 4):
    s = "a" * p + "b" * p + "c" * p
    all_violate, total, counterexample = check_cfl_pumping_violation(s, p, is_anbncn, i=2)
    print(f"p={p}  s={s!r}  মোট-বিভাজন-চেক-করা={total}  প্রতিটিই-violate-করেছে={all_violate}")
    if counterexample:
        print("   ব্যতিক্রম পাওয়া গেছে (প্রমাণ ভেঙে যেত):", counterexample)

print()
print("সিদ্ধান্ত: প্রতিটি পরীক্ষিত p-এর জন্য, a^p b^p c^p-এর প্রতিটি সম্ভাব্য পাঁচ-ভাগ বিভাজন,")
print("i=2 দিয়ে পাম্প করলে a^n b^n c^n ভাষার বাইরে চলে যায় -- অর্থাৎ কোনো পাম্পিং লেংথ")
print("থাকতেই পারে না (contradiction), তাই L = {a^n b^n c^n} কনটেক্সট-ফ্রি নয় (QED)।")