सीएफजी के लिए लेम्मा पंप करना

लेम्मा

अगर L एक संदर्भ-मुक्त भाषा है, एक पंपिंग लंबाई है p ऐसे कि कोई भी तार w ∈ L लंबाई की ≥ p के रूप में लिखा जा सकता है w = uvxyz, कहाँ पे vy ≠ ε, |vxy| ≤ p, और सभी के लिए i ≥ 0, uvⁱxyⁱz ∈ L।

पम्पिंग लेम्मा के अनुप्रयोग

पम्पिंग लेम्मा का उपयोग यह जांचने के लिए किया जाता है कि कोई व्याकरण संदर्भ मुक्त है या नहीं। आइए एक उदाहरण लेते हैं और दिखाते हैं कि यह कैसे जांचा जाता है।

मुसीबत

पता करें कि क्या भाषा L = {xⁿyⁿzⁿ | n ≥ 1} संदर्भ मुक्त है या नहीं।

उपाय

लश्कर Lसंदर्भ मुक्त है। फिर,L पम्पिंग लेम्मा को संतुष्ट करना चाहिए।

सबसे पहले, एक नंबर चुनें nपम्पिंग लेम्मा। फिर, 0 ⁿ 1 ⁿ 2 ^{n के} रूप में z लें ।

टूटना z जांच uvwxy, कहाँ पे

|vwx| ≤ n and vx ≠ ε.

इसलिये vwx0 और 2s दोनों को शामिल नहीं कर सकता, क्योंकि अंतिम 0 और पहले 2 अलग-अलग हैं (n + 1) स्थिति। दो मामले हैं -

Case 1 - vwxकोई 2s है। फिरvxकेवल 0s और 1s है। फिरuwy, जो अंदर होना होगा L, है n 2s, लेकिन से कम n 0 या 1 एस।

Case 2 - vwx कोई 0s है।

यहां विरोधाभास होता है।

इसलिये, L एक संदर्भ-मुक्त भाषा नहीं है।