मुझे यह समस्या है कि मुझे पंपिंग लेम्मा का उपयोग करके यह साबित करने की आवश्यकता है कि भाषा नियमित नहीं है, लेकिन मैं इसे कितना भी पढ़ूं, मुझे अभी भी समझ में नहीं आता है। क्या कोई कृपया इसे हल करने में मदद कर सकता है?

दिखाएँ कि L = { a^n c b^m | n, m are natural numbers and n < m} नियमित नहीं है।

1
Saul 17 मार्च 2020, 15:34

1 उत्तर

सबसे बढ़िया उत्तर

A^p c b^2p चुनें। यह स्ट्रिंग भाषा में p < 2p के बाद से है। इस स्ट्रिंग के पहले p वर्णों में किसी भी गैर-रिक्त सबस्ट्रिंग को p से अधिक के कारक द्वारा पंप करने से a की संख्या b की संख्या से अधिक बढ़ने की गारंटी है। यह पंपिंग लेम्मा के दावे का खंडन करता है कि एक नियमित भाषा में एक स्ट्रिंग पर ऐसा करने से उस भाषा में एक और स्ट्रिंग मिलनी चाहिए। इसलिए, भाषा नियमित नहीं हो सकती थी।

0
Patrick87 17 मार्च 2020, 17:55