পাঠ ১৪ · ৫৬-এর মধ্যে · মডিউল ৩
Home / Courses / Formal Language & Automata Theory / Theory of Computation / নন-রেগুলারিটি প্রমাণ

একটি ল্যাঙ্গুয়েজ রেগুলার নয় তা প্রমাণ করা

Proving languages are not regular
৮ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এই পাঠে যা শিখবেন

  • প্রুফ-বাই-কন্ট্রাডিকশন টেমপ্লেট — assume regular → choose s → show every split fails → contradiction
  • $L=\{0^n1^n\}$-এর সম্পূর্ণ, নিখুঁত প্রমাণ, ধাপে ধাপে
  • কেন "একটি split হাতে বেছে দেখানো" যথেষ্ট নয় — সব বৈধ split-ই ভাঙতে হবে
  • Python-এ real check_pumping_violation — প্রতিটি বৈধ $(x,y,z)$ split এক্সহস্টিভলি জেনারেট ও যাচাই
  • একাধিক $p$-এর মান নিয়ে কোড চালিয়ে প্রমাণ পুনরায় নিশ্চিত করা

১ · প্রুফ-বাই-কন্ট্রাডিকশন টেমপ্লেট

L13-এর পাম্পিং লেমাকে কনট্রাপজিটিভেContrapositive"$P \Rightarrow Q$" সত্য হলে "$\neg Q \Rightarrow \neg P$"-ও সত্য — যুক্তিগতভাবে সমতুল্য একটি ভিন্ন রূপ, প্রায়ই প্রমাণে বেশি ব্যবহারযোগ্য (Discrete Mathematics কোর্সে ফরমালি আলোচিত)। ব্যবহার করলে দাঁড়ায় — "যদি একটি ল্যাঙ্গুয়েজ পাম্পিং প্রপার্টি না মানে, তাহলে সেটি রেগুলার নয়।" ব্যবহারিকভাবে এটি একটি স্ট্যান্ডার্ড প্রুফ-বাই-কন্ট্রাডিকশন টেমপ্লেটে পরিণত হয় —

  1. ধরে নিন $L$ রেগুলার — তাহলে L13 অনুযায়ী একটি পাম্পিং লেংথ $p$ থাকতেই হবে।
  2. বেছে নিন একটি নির্দিষ্ট স্ট্রিং $s \in L$ যেখানে $|s| \geq p$ (এই বাছাইটাই প্রমাণের "শিল্প" — যুক্তিটা কাজ করার মতো করে বেছে নিতে হয়)।
  3. দেখান যে $s=xyz$-এর প্রতিটি সম্ভাব্য বৈধ ভাগ (শর্ত (১) $|y|>0$ ও শর্ত (২) $|xy|\leq p$ মেনে) নিয়ে, কোনো না কোনো $i$-এর জন্য $xy^iz \notin L$ — এটি শর্ত (৩)-এর সাথে সরাসরি বিরোধ।
  4. সিদ্ধান্ত নিন — যেহেতু ধরে নেওয়া অনুমান থেকে বিরোধ এসেছে, তাই মূল অনুমান ("$L$ রেগুলার") ভুল — $L$ রেগুলার নয়।

২ · ক্লাসিক উদাহরণ — $L = \{0^n1^n : n \geq 0\}$

এটিই সবচেয়ে বেশি উদ্ধৃত নন-রেগুলারিটি প্রমাণ — সমান সংখ্যক 0 তারপর সমান সংখ্যক 1 (যেমন "0011", "000111", খালি স্ট্রিং)। এই ভাষাকে রেগুলার হওয়ার জন্য অসীম "গণনা" মনে রাখতে হবে (কতগুলো 0 পড়া হয়েছে), যা একটি ফাইনাইট-স্টেট DFA-র পক্ষে অসম্ভব — নিচের প্রমাণ এটিই নিখুঁতভাবে দেখায়।

প্রমাণ · $L = \{0^n1^n : n \geq 0\}$ নন-রেগুলার

ধরুন $L$ রেগুলার, তাহলে একটি পাম্পিং লেংথ $p$ থাকে। বেছে নিন $s = 0^p1^p \in L$ (এবং $|s|=2p \geq p$)। এখন যেকোনো বৈধ split $s = xyz$ যেখানে $|xy| \leq p$, খেয়াল করুন — $s$-এর প্রথম $p$টি ক্যারেক্টারই সব "0"। যেহেতু $xy$ প্রথম $p$ ক্যারেক্টারের মধ্যেই সীমাবদ্ধ, তাই $xy$ (এবং তাই $y$-ও) সম্পূর্ণভাবে 0 দিয়ে গঠিত — $y = 0^k$ কোনো $k \geq 1$-এর জন্য। এখন $i=0$ নিলে (পাম্প ডাউন, $y$ সম্পূর্ণ বাদ) — $xy^0z = xz$-এ 0-এর সংখ্যা $k$ কমে গেছে কিন্তু 1-এর সংখ্যা অপরিবর্তিত — ফলে 0 আর 1-এর সংখ্যা আর সমান নেই, তাই $xz \notin L$। এটি শর্ত (৩)-এর সরাসরি বিরোধ — অতএব $L$ রেগুলার নয়। $\blacksquare$

একটি সাধারণ প্রমাণ-ভুল — শুধু একটি split হাতে বেছে দেখানো যে সেটি ভাঙে, এটি যথেষ্ট নয়! লেমার শর্ত (৩) বলে প্রতিটি বৈধ split-এই একটি $i$ থাকতে হবে যা ভাঙে — তাই প্রমাণে দেখাতে হয় যে সব সম্ভাব্য $(x,y,z)$ split-ই কোনো না কোনো $i$-তে ভেঙে যায়। $0^n1^n$-এর ক্ষেত্রে এটি সহজ কারণ শর্ত (২) ($|xy|\leq p$) সব বৈধ split-কেই "শুধু 0" আকারে বাধ্য করে দেয় — কিন্তু এই যুক্তিটা স্পষ্টভাবে বলা জরুরি, নাহলে প্রমাণটি অসম্পূর্ণ থেকে যায়।

৩ · কোডে এক্সহস্টিভ ভেরিফিকেশন

নিচের কোড সেলে check_pumping_violation(s, p, in_L) ফাংশনটি $|xy|\leq p$ ও $|y|>0$ মেনে সম্ভাব্য সবগুলো $(x,y,z)$ split জেনারেট করে, এবং প্রতিটির জন্য $i \in \{0,2,3\}$ টেস্ট করে দেখে কোনো একটি ভায়োলেশন খুঁজে পাওয়া যায় কি না। এটি $s=0^p1^p$-এর জন্য $p=1,2,3,4$ — প্রতিটির জন্য চালিয়ে নিশ্চিত করা হয়েছে যে সবগুলো বৈধ split-ই ভায়োলেশন ঘটায়, উপরের হাতে-লেখা প্রমাণকে একটি concrete, code-verified চেকে রূপান্তর করে।

Python
def in_zero_n_one_n(s):
    # সত্যিকারের মেম্বারশিপ চেকার (কোনো re মডিউল ব্যবহার ছাড়াই) -- L = { 0^n 1^n : n >= 0 }
    i = 0
    n = 0
    while i < len(s) and s[i] == '0':
        n += 1
        i += 1
    m = 0
    while i < len(s) and s[i] == '1':
        m += 1
        i += 1
    return i == len(s) and n == m   # পুরো স্ট্রিং শেষ হয়ে গেছে এবং 0/1-এর সংখ্যা সমান


def all_valid_splits(s, p):
    # |xy| <= p এবং |y| > 0 মেনে s = xyz-এর সম্ভাব্য সবগুলো ভাগ জেনারেট করে
    splits = []
    for xy_len in range(1, p + 1):        # শর্ত (২): |xy| <= p
        for y_start in range(0, xy_len):  # শর্ত (১): |y| > 0
            x = s[:y_start]
            y = s[y_start:xy_len]
            z = s[xy_len:]
            splits.append((x, y, z))
    return splits


def check_pumping_violation(s, p, in_L):
    assert len(s) >= p and in_L(s)
    results = []
    all_splits_violate = True
    for (x, y, z) in all_valid_splits(s, p):
        violated_by = None
        for i in (0, 2, 3):               # পাম্প ডাউন এবং পাম্প আপ, দুই দিকেই টেস্ট
            pumped = x + y * i + z
            if not in_L(pumped):
                violated_by = (i, pumped)
                break
        results.append((x, y, z, violated_by))
        if violated_by is None:
            all_splits_violate = False    # এই split-এ কোনো ভায়োলেশন পাওয়া যায়নি -- প্রমাণ ভেঙে যেত
    return results, all_splits_violate


for p in (1, 2, 3, 4):
    s = "0" * p + "1" * p
    results, all_violate = check_pumping_violation(s, p, in_zero_n_one_n)
    print(f"p={p}, s={s!r}: {len(results)}টি বৈধ (x,y,z) split চেক করা হলো")
    for (x, y, z, v) in results:
        i, pumped = v
        print(f"    x={x!r:6s} y={y!r:6s} z={z!r:6s} -> i={i}: xy^{i}z = {pumped!r}  (in L: {in_zero_n_one_n(pumped)})")
    print(f"  => প্রতিটি split-এই ভায়োলেশন পাওয়া গেছে (all_splits_violate): {all_violate}")
    print()

    


    

      লক্ষ্য করুন কোডের আউটপুটে প্রতিটি $p$-এর জন্য সবগুলো $(x,y,z)$ split ($p=4$-এ ১০টি split)
      একই সিদ্ধান্তে পৌঁছায় — $i=0$-এ ভায়োলেশন। এটিই হাতে-লেখা প্রমাণে "$xy$ সবসময় শুধু 0" আর্গুমেন্টের একটি
      সরাসরি, রান-টাইম-এ চালানো নিশ্চিতকরণ — কোনো একটি split হাতে বেছে দেখানো নয়, বরং সবগুলোই।
    


    

      
এক্সহস্টিভ চেক
প্রতিটি বৈধ split আলাদাভাবে জেনারেট ও যাচাই — কোনো একটি হাতে-বাছাই নয়।

      
পাম্প ডাউন ($i{=}0$)
$0^n1^n$-এ সবসময় নির্ণায়ক — 0-এর সংখ্যা কমে যায়, 1-এর সংখ্যা স্থির থাকে।

      
কনট্রাপজিটিভ
ধর্ম ভাঙলে নন-রেগুলার — এটিই এই টেমপ্লেটের মূল লজিক্যাল কাঠামো।

    


    

      মূল কথা · Key takeaway
      

        নন-রেগুলারিটি প্রমাণের কেন্দ্রীয় টেমপ্লেট — assume regular, choose a clever $s$, show every valid split
        fails, contradiction। "প্রতিটি split" শব্দটাই সবচেয়ে গুরুত্বপূর্ণ — একটি নয়, সব। $0^n1^n$-এর প্রমাণ এই
        টেমপ্লেটের সবচেয়ে ক্লাসিক প্রয়োগ, এবং এখানে দেখানো এক্সহস্টিভ কোড-ভেরিফিকেশন কৌশলটি প্রায় যেকোনো
        নন-রেগুলারিটি প্রমাণেই পুনর্ব্যবহারযোগ্য।
      

    


  


  

    
    
  


  

    
 ভাবনার প্রশ্ন

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        $s=0^p1^p$-এর বদলে যদি $s=1^p0^p$ বেছে নেওয়া হতো, প্রমাণটি কি একইভাবে কাজ করত?
      
      

        

          না, সরাসরি নয় — এবং এটি বাছাইয়ের গুরুত্ব দেখায়। $1^p0^p \notin L$ (যেহেতু $L$-এর সংজ্ঞা 0 আগে,
          তারপর 1), তাই প্রমাণের ধাপ (২)-এই ("বেছে নিন $s \in L$") এটি ব্যর্থ হবে — $s$ আদৌ $L$-এর সদস্যই নয়।
          এই কারণেই প্রমাণের "বাছাই" ধাপকে "শিল্প" বলা হয় — $s$-কে অবশ্যই $L$-এর সদস্য হতে হবে, এবং এমনভাবে
          গঠিত হতে হবে যাতে শর্ত (২) ($|xy|\leq p$) বাধ্য করে $y$ একটি নির্দিষ্ট, ভবিষ্যদ্বাণীযোগ্য আকারে থাকুক
          — এখানে "সব 0"।
        

      

    


    

      
        প্র ০২
        যদি কেউ শুধু $p=2$-এর একটিমাত্র split (যেমন $x{=}\varepsilon, y{=}00, z{=}11$) দেখিয়ে "প্রমাণ শেষ" বলে, এই প্রমাণে কী সমস্যা?
      
      

        

          এটি একটি অসম্পূর্ণ প্রমাণ। পাম্পিং লেমার শর্ত (৩) বলে — যদি $L$ রেগুলার হতো, তাহলে প্রতিটি
          বৈধ split-এর জন্যই সব $xy^iz \in L$ হতো। তাই বিরোধ প্রতিষ্ঠা করতে দেখাতে হবে সবগুলো
          বৈধ split ($p=2$-এ মোট ৩টি — উপরের কোড আউটপুট দেখুন) কোনো না কোনো $i$-তে ভাঙে। শুধু একটি split
          ভাঙলে সেটি বিরোধের একটি প্রয়োজনীয় অংশ দেখায়, কিন্তু বাকি split-গুলো (যেগুলো হয়তো না-ও ভাঙতে পারত,
          অন্য কোনো ভাষায়) যাচাই না করলে প্রমাণটি যুক্তিগতভাবে অসম্পূর্ণ থেকে যায় — এই কারণেই উপরের কোড
          সবগুলো split এক্সহস্টিভলি চেক করে।
        

      

    


    

      
        প্র ০৩
        $L = \{ww^R : w \in \{0,1\}^*\}$ (প্যালিনড্রোম) নন-রেগুলার প্রমাণেও কি একই টেমপ্লেট প্রযোজ্য?
      
      

        

          হ্যাঁ, একদম একই চার-ধাপের টেমপ্লেট প্রযোজ্য — শুধু $s$-এর বাছাই ভিন্ন হবে। উদাহরণস্বরূপ $s = 0^p110^p$
          (একটি প্যালিনড্রোম) বেছে নিলে, শর্ত (২) আবারও $y$-কে প্রথম $p$ ক্যারেক্টারের মধ্যে (সব 0) বাধ্য করবে —
          পাম্প ডাউন করলে বাম দিকের 0-এর সংখ্যা কমে যাবে কিন্তু ডান দিকের 0-এর সংখ্যা অপরিবর্তিত থাকবে, ফলে
          প্যালিনড্রোম-ধর্ম ভেঙে যাবে। এই টেমপ্লেটের সাধারণতা (generality) — যেকোনো ভাষায় প্রযোজ্য যেখানে একটি
          "সুষম গণনা" বা "মিলে যাওয়া অংশ" আছে যা ফাইনাইট স্টেট দিয়ে মনে রাখা যায় না — এটিই এই কৌশলটিকে এত
          শক্তিশালী করে তোলে।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        চিন্তা করুন: $L = \{0^i1^j : i > j\}$ নন-রেগুলার প্রমাণে $s = 0^{p+1}1^p$ কেন একটি
        ভালো বাছাই হবে? শর্ত (২) কীভাবে $y$-কে বাধ্য করবে চিন্তা করুন।
        
    
          
          
    
            
    
              $s=0^{p+1}1^p \in L$ (যেহেতু $p+1 > p$), এবং $|s| = 2p+1 \geq p$। শর্ত (২) ($|xy|\leq p$) আবারও
              $y$-কে প্রথম $p$ ক্যারেক্টারের মধ্যে বাধ্য করবে — যেহেতু প্রথম $p+1$টি ক্যারেক্টারই "0" (স্ট্রিং-এ
              মোট $p+1$টি 0 আছে), তাই $y$ নিশ্চিতভাবে শুধু 0 দিয়ে গঠিত ($y=0^k$)। পাম্প আপ করলে ($i=2$) 0-এর
              সংখ্যা বেড়ে যাবে (আরও বেশি $i>j$ হবে, তাই সেটি এখনও $L$-এই থাকবে!) — কিন্তু পাম্প ডাউন করলে
              ($i=0$) 0-এর সংখ্যা $k$ কমে যাবে; যদি $k \geq (p+1)-p = 1$... আসলে এখানে সাবধানে দেখতে হবে —
              যেহেতু $k \geq 1$ এবং মোট 0 ছিল $p+1$, পাম্প-ডাউনের পর 0-এর সংখ্যা হয় $p+1-k \leq p$, যা 1-এর
              সংখ্যা $p$-এর চেয়ে বড় নাও হতে পারে — এই সূক্ষ্ম বিশ্লেষণটাই দেখায় কেন $s$ সাবধানে বেছে নেওয়া এবং
              প্রতিটি সম্ভাব্য $k$ (অর্থাৎ প্রতিটি বৈধ split) আলাদাভাবে যাচাই করা জরুরি — ঠিক যেমন উপরের কোড করে।
            
    
          
    
        
    
      
    2. 
      
  2. 
        পরীক্ষা করুন: উপরের কোড সেলে for p in (1, 2, 3, 4):-এর রেঞ্জ বাড়িয়ে
        range(1, 7) করে Run চাপুন — বড় $p$-এর জন্যও কি সবগুলো split-এ ভায়োলেশন পাওয়া যায় (all_violate
        সবসময় True)?
        
    
          
          
    
            
    
              হ্যাঁ, $p$ যত বড়ই হোক না কেন all_violate সবসময় True থাকবে, কারণ হাতে-লেখা
              প্রমাণের যুক্তি ($s=0^p1^p$-এর প্রথম $p$ ক্যারেক্টার সবসময়ই সব 0, শর্ত (২) দিয়ে) $p$-এর নির্দিষ্ট
              মানের উপর নির্ভর করে না — এটি সাধারণভাবে সত্য যেকোনো $p \geq 1$-এর জন্য। কোডে বড় $p$ টেস্ট করলে
              split-সংখ্যা বাড়বে ($p=6$-এ ২১টি split) কিন্তু প্রতিটিই একই কারণে ($i=0$-এ 0-এর সংখ্যা কমে যাওয়া)
              ভাঙবে।
            
    
          
    
        
    
      
    3. 
    

  


  

    
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

    
  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 আগের পাঠ

    
L13 · রেগুলার ল্যাঙ্গুয়েজের জন্য পাম্পিং লেমা