पंपिंग लेम्मा (नियमित भाषा)

Question

मुझे पंपिंग लेम्मा समस्या के साथ कुछ मदद की ज़रूरत है। abbc^n

y = uvw is the string from the pumping lemma. 

मैं y जाने =, एन पम्पिंग लेम्मा से लंबाई है:

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) } 

यह मैं अब तक क्या मिला है। y एल में है क्योंकि एस की संख्या बी: एस की संख्या से कम है, और बी: एस की संख्या सी: एस की संख्या से कम है।

मैं आपको = ए, वी = बीबी और डब्ल्यू = सी^एन। | यूवी | < वाई, जैसा कि lemma पंपिंग में कहा गया है। अगर मैं "पंप" (बीबी)^2 प्राप्त करता हूं तो मुझे

y = abbbbc^n which violates the rule #b(L) < #c(L). 

क्या यह सही है? क्या मैं "सही रास्ते" पर हूं?

धन्यवाद

Answer 1

पम्पिंग लेम्मा में बताने के लिए जब आप शब्दों के अनंत संख्या के साथ एक नियमित भाषा L है वहाँ भाषा है कि हमेशा दोहराता में एक पैटर्न है कि है की मुख्य विचार।

उस भाषा से जुड़े नियमित अभिव्यक्ति में क्लेन-स्टार (पैटर्न) होगा।

उस नियमित अभिव्यक्ति (और भाषा) से जुड़े automaton में एक लूप होगा।

सबूत कबूतर सिद्धांत का उपयोग करके किया जाता है।

यह बहुत ही सूचक है।

ध्यान दें कि सभी शर्तों को q0 में शुरू होना चाहिए और इस मामले में qn में समाप्त होना चाहिए। इसलिए, भाषा को परिभाषित करने वाला ऑटोमाटा सीमित (अधिकतम एन राज्य) है, इसलिए सीमित संख्या में राज्य हैं, लेकिन शब्दों (यानी शब्दों) में> एन अक्षर हो सकते हैं। कबूतर सिद्धांत हमें बताता है कि एक राज्य होना चाहिए जो 2 गुना तक पहुंच गया हो, इसलिए उस स्थिति में एक लूप मौजूद होगा।

अपने अंकन में, आप छवि इतनी के साथ पत्राचार कर सकते हैं:

• अपने u छवि

• v से x है छवि में y

• w से z है छवि

q0 से qn तक पहुंचने के लिए, आप सेट से किसी भी स्ट्रिंग का उपयोग कर सकते हैं: { uw , uvw, uvvw, uvvvw, ... }।

इस विशेष मामले में पैटर्न Py है, सेट X{xz xyz xyyz xyyyz ...} और Slength(x)+length(y) है।