क्या "वास्तविक" भाषाओं के साथ lemmas पंप करने के कोई उदाहरण हैं?

Question

pumping lemmaregular languages और context-free languages की एक संपत्ति है।

एल = {0 ^{n n n}:: n ≥ 0}

(जो संयोगवश, नहीं एक है लेकिन सभी उदाहरण मैंने देखा है की तरह बातें कर रहे हैं संदर्भ मुक्त भाषा)।

लेकिन मुझे इसमें क्या रूचि है यह है: क्या किसी भी दूरस्थ रूप से वास्तविक या उपयोगी भाषाओं के साथ इसका उपयोग करने के कोई उदाहरण हैं? मैं कोई भी खोजने में सक्षम नहीं हूं। क्या यह उन चीजों में से एक है या बिल्कुल सैद्धांतिक मूल्य बिल्कुल व्यावहारिक अनुप्रयोग के साथ नहीं है?

Answer 1

एल = {0 ^{n n}: n ≥ 0} एक विषय से मुक्त भाषा जा रहा है। एक अभिव्यक्ति में

कोष्ठक मिलान यानी

एल = {(ⁿ) ⁿ: n ≥ 0} समान रूप से होना करने के लिए माना जा सकता है

Answer 2

एक व्यावहारिक उपयोग तथ्य यह है कि हर किसी को है सी # या फोरट्रान के वाक्यविन्यास को पहचानने के लिए एक सीमित automaton बनाने की कोशिश करना बंद कर सकते हैं।

एक और व्यावहारिक उपयोग यह तथ्य है कि हर कोई सी # या फोरट्रान के अर्थशास्त्र को पहचानने के लिए पुशडाउन automaton बनाने की कोशिश करना बंद कर सकता है। (भले ही आप एक परिवर्तनीय नाम की गलत वर्तनी करते हैं, तो आपको एक नया वैरिएबल मुफ्त में मिलता है, नया वैरिएबल शायद उन ऑपरेटरों के साथ काम नहीं कर सकता है जिन्हें आपने अपने घोषित चरों में से एक का नाम देने का इरादा किया था।)

Answer 3

"है उन चीजों में से एक या पूरी तरह से सैद्धांतिक मूल्य बिल्कुल व्यावहारिक अनुप्रयोग के साथ? "

एचआरएम। व्यावहारिक आवेदन क्या है? आपने बुद्धिमानी से अपने प्रश्न "कंप्यूटर-विज्ञान" को टैग किया है। तो मुझे लगता है कि अपने प्रश्न पूछने के लिए है, "यह कंप्यूटर विज्ञान के लिए व्यावहारिक है?

जो मामले में, इस सवाल का जवाब है ...

बेशक यह है की

! यह पहली तरीकों में से एक के रूप में पढ़ाया जा रहा है से परे अलग-अलग भाषा जटिलता वर्गों को वर्गीकृत करने के लिए यह दिखाता है कि केवल रनटाइम से परे गणना से संबंधित मुद्दे हैं, इस मामले में कुछ मॉडल बस कुछ कार्यों की गणना नहीं कर सकते हैं। * यह एक बहुत कम है ऑटोटाटा सिद्धांत से संबंधित औपचारिक सबूत के लिए -बॉल परिचय।

कंप्यूटर विज्ञान का एक बड़ा हिस्सा है कि अधिकांश कंप्यूटर विज्ञान के छात्र (मेरे साथियों) प्रतीत होते हैं से बचने के लिए उत्सुकता सिद्धांत की सिद्धांत है, एक वर्गीकरण जो स्पष्ट रूप से लेम्मा को पंप करता है।

आशावादी स्पष्ट तथ्य यह है कि गणना के सिद्धांत, जैसे या नहीं, कंप्यूटर विज्ञान के लिए आधारभूत है। विभिन्न जटिलता वर्गों के विचार को समझने के लिए (बड़े-ओ स्वयं ने वास्तव में इसे काट नहीं दिया है) कंप्यूटर वैज्ञानिक की मौत का जादू नहीं करेगा, लेकिन यह क्षेत्र के एक बड़े हिस्से को उसके विचार से छुपाएगा।

* हां, आमतौर पर रोकथाम की समस्या पहले के रूप में दिखाई जाती है, लेकिन वे इसे पहली बार कभी नहीं मिलते हैं।

शायद आपके प्रश्न की अधिक क्रूर व्याख्या के रूप में, जिसका अर्थ है "क्या सॉफ्टवेयर का कोई भी टुकड़ा वास्तव में इसका उपयोग करता है?", मेरा जवाब बिल्कुल नहीं है। यह गणना के आधार का हिस्सा है, न कि इसके अनुप्रयोगों। यह अपने अनुप्रयोगों को बर्खास्त करने के लिए नहीं है, बिलकुल नहीं। दोनों बराबर, महान मूल्य के हैं।

Answer 4

इस अजगर कार्यक्रम मान्य है:

print ((((((((((((((((((((((((1)))))))))))))))))))))))) 

के साथ-साथ सही पक्ष पर बाईं तरफ के ( और ) की एक समान राशि के साथ अन्य सभी बराबर बयान।

आप इसे सत्यापित करने के लिए नियमित अभिव्यक्ति नहीं बना सकते हैं, इस प्रकार आपको एक पार्सर का उपयोग करना होगा।

यह सैद्धांतिक नहीं है। यही कारण है कि आप HTML का विश्लेषण करने के लिए regex का उपयोग नहीं कर सकते हैं।