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

Aug 16 2020

मुझे यह भाषा दिखाने के बारे में सवाल आया $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$पीटर लिन्ज़ द्वारा पुस्तक में संदर्भ-मुक्त लेकिन रेखीय नहीं है। यह रैखिक भाषाओं के लिए अलग पंपिंग लेम्मा द्वारा आसानी से संभव है (जैसा कि लिंज़ की पुस्तक में दिया गया है), लेकिन मेरा सवाल अलग है।

जाहिर है कि यह एक सीएफएल है, और इसके लिए एक पुशडाउन ऑटोमेटन का निर्माण किया जा सकता है। लेकिन अगर मैं सीएफएल के लिए पंपिंग लेम्मा लागू करता हूं, तो मुझे लगता है कि मैं उन तारों को पंप करने में सक्षम हूं जो भाषा से संबंधित नहीं हैं, जिसका मतलब होगा कि भाषा सीएफएल नहीं है। स्पष्ट रूप से मैं कुछ गलत कर रहा हूं।

लिंज़ में दिए गए "गेम-लाइक" प्रारूप के अनुसार, आप कहेंगे $w = a^mb^mc^{2m}$, $|w| \ge m$। विरोधी कई विघटित विकल्प चुन सकता है$w = uvxyz$, वे इस तरह दिख सकते हैं -:

  • $v = a^k, y = a^l$: मामला जहां $|vxy|$ के भीतर समाहित है $a$स्ट्रिंग का है। पंप$i = 0$, और फिर $w_0 = a^{m – (k + l)}b^mc^{2m}$ भाषा में नहीं हो सकता क्योंकि समानता अब नहीं रखती है।
  • $v = a^k, y = b^l$: मामला जहां $v$ में हे $a$ अनुभाग, $x$ भर में फैला हुआ है $a$'रेत $b$'रेत $y$ में हे $b$अनुभाग। फिर से, पंप$i = 0$$w_0 = a^{m – k}b^{m – l}c^{2m}$ भाषा में नहीं हो सकता।

इस तरह के और भी मामले हैं। मैं सीएफएल पीएल के आवेदन में कहां गलत हूं?

जवाब

1 vonbrand Aug 17 2020 at 08:20

CFL के लिए पम्पिंग लेम्मा बताती है कि यदि $L$ एक सीएफएल है, एक निरंतर मौजूद है $N \ge 1$ ऐसे सभी के लिए $\omega \in L$ साथ में $\lvert \omega \rvert \ge N$ एक विभाजन है $\sigma = u v w x y$ साथ में $\lvert v w x \rvert \le N$ तथा $v x \ne \varepsilon$ ऐसा है कि $u v^k w x^k y \in L$ सबके लिए $k \ge 0$

(नियमित भाषाओं के लिए पम्पिंग लेम्मा समान है, नीचे चर्चा मामूली बदलाव के साथ लागू होती है)।

आप विरोधाभास द्वारा साबित करना चाहते हैं कि $L$सीएफएल नहीं है। तो आप मान लीजिए$L$सीएफएल है, और लेम्मा के विपरीत है। इसका मतलब है, विस्तार से:

  • जैसा $L$सीएफएल है, यह लेम्मा को संतुष्ट करता है। विशेष रूप से, एक स्थिर है$N$ ऐसा है कि...
  • जैसा कि लेम्मा में सभी लंबे तार हैं$L$ विभाजित किया जा सकता है, आप उस एक को लेने के लिए स्वतंत्र हैं जिसके साथ काम करना आसान है।
  • लेम्मा कहती है कि इसका कुछ विभाजन है$\omega$ऐसा है कि .... सभी के लिए $k \ge 0$...; किसी भी विभाजन के काम को साबित करने के लिए आपको लेम्मा का खंडन करना होगा । व्यवहार में, आप अपने दिए गए विभाजन को लेते हैं$\omega$( कोई भी विभाजन) और इसके लिए कुछ चुनें$k$इसके लिए जो भाषा में एक स्ट्रिंग नहीं देता है। आपको इसे मामलों में विभाजित करने की आवश्यकता हो सकती है।

उन स्ट्रिंग्स के लिए क्या होता है जो भाषा से संबंधित नहीं हैं, या इससे कम हैं $N$, पूरी तरह से अप्रासंगिक है। यह हो सकता है कि कुछ तारों को पंप किया जा सकता है, कि कुछ मूल्यों का$k$सभी तारों के लिए काम करते हैं, ... जो महत्वपूर्ण है वह एक तार के लिए है$\omega$(आपके द्वारा चुना गया) कोई भी विभाजन एक मान से काम नहीं करता है$k$(फिर से, जिसे आपने चुना है)। लेम्मा कहा है इसके लिए काम करता है सब काफी देर तक तार, साथ कुछ के लिए विभाजन सभी $k$, एक प्रतिधारण पर्याप्त है। अनंत उदाहरण कुछ नहीं साबित करते हैं।