नियमित व्याकरण के लिए पम्पिंग लेम्मा
प्रमेय
L को एक नियमित भाषा होने दें। फिर एक अस्तित्व है‘c’ ऐसा हर स्ट्रिंग के लिए w में L -
|w| ≥ c
हम टूट सकते हैं w तीन तार में, w = xyz, ऐसा
- | Y | > 0
- | Xy | ≤ सी
- सभी k all 0 के लिए, स्ट्रिंग xy k z भी L में है।
पम्पिंग लेम्मा के अनुप्रयोग
पम्पिंग लेम्मा को यह दिखाने के लिए लागू किया जाना चाहिए कि कुछ भाषाएं नियमित नहीं हैं। किसी भाषा को नियमित दिखाने के लिए इसका उपयोग कभी नहीं किया जाना चाहिए।
अगर L नियमित है, यह पम्पिंग लेम्मा को संतुष्ट करता है।
अगर L पम्पिंग लेम्मा को संतुष्ट नहीं करता है, यह गैर-नियमित है।
यह साबित करने की विधि कि एक भाषा L नियमित नहीं है
सबसे पहले, हमें यह मान लेना होगा L नियमित है।
इसलिए, पंपिंग लेम्मा को पकड़ना चाहिए L।
विरोधाभास प्राप्त करने के लिए पंपिंग लेम्मा का उपयोग करें -
चुनते हैं w ऐसा है कि |w| ≥ c
चुनते हैं y ऐसा है कि |y| ≥ 1
चुनते हैं x ऐसा है कि |xy| ≤ c
शेष स्ट्रिंग को असाइन करें z.
चुनते हैं k इस तरह के परिणामस्वरूप स्ट्रिंग में नहीं है L.
Hence L is not regular.
Problem
साबित करो L = {aibi | i ≥ 0} नियमित नहीं है।
Solution -
सबसे पहले, हम मानते हैं कि L नियमित है और n राज्यों की संख्या है।
W = a n b n । इस प्रकार | डब्ल्यू | = 2 एन ≥ एन।
लेम्मा पंप करके, w = xyz, जहाँ | xy | ≤ n।
X = a p , y = a q , और z = a r b n , जहाँ p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. इस प्रकार | y | ≠ 0।
K = 2. तब xy 2 z = a p a 2q a r b n ।
संख्या के रूप में = (p + 2q + r) = (p + q + r) + q = n + q
इसलिए, xy 2 z = a n + q b n । ≠ क्ष के बाद से 0, xy 2 जेड प्रपत्र एक की नहीं है एन बी एन ।
इस प्रकार, xy 2 z, L में नहीं है। इसलिए L नियमित नहीं है।