12
एक सीएस कोर्स मैं वहाँ ले रहा हूँ कि नियमित रूप से नहीं है एक भाषा का एक उदाहरण है:{a^nb^n | क्यों है n> = 0} नियमित नहीं है?
{a^nb^n | n >= 0}
मैं समझ सकता है कि यह नियमित रूप से के बाद से कोई परिमित अवस्था automaton/मशीन लिखा जा सकता है नहीं है कि पुष्टि करता है और इस इनपुट को स्वीकार करता है क्योंकि इसमें स्मृति घटक की कमी है। (अगर मैं गलत हूं तो कृपया मुझे सही करें)
wikipedia entry on Regular Language इस उदाहरण को भी सूचीबद्ध करता है, लेकिन यह (गणितीय) प्रमाण प्रदान नहीं करता है कि यह नियमित क्यों नहीं है।
क्या कोई मुझे इस पर प्रबुद्ध कर सकता है और इसके लिए सबूत प्रदान कर सकता है, या मुझे भी एक अच्छा संसाधन बता सकता है?
धन्यवाद, बस मैं जो देख रहा था। –
अंतिम दावे को बेहतर स्पष्टीकरण की आवश्यकता है। X2yz शब्द में या तो एक प्रकार के अधिक अक्षर होंगे (यदि y में बी की तुलना में अधिक है या इसके विपरीत), या डुप्लिकेट करने से यह अक्षर ऑर्डर को तोड़ देगा, जिसमें बी के सभी के बाद आना चाहिए। –
अपूर्ण सबूत। आपने एक्स, वाई, जेड परिभाषित नहीं किया है। एक्स केवल सीमा है कि | xy | <= पी, जहां पी पंपिंग लंबाई है। आपको पूर्ण होने के लिए (ए | एबी | बी) के आधार पर वाई स्ट्रिंग्स के साथ तीन मामलों में अपना सबूत विभाजित करना होगा। xy अच्छी तरह से बी से अधिक बी हो सकता है: x = a, y = b^n, z = b – oligofren