S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB
दो स्ट्रसे पेड़ उत्पन्न करने वाली स्ट्रिंग को खोजने की कोशिश करने के अलावा कोई आसान तरीका?मैं कैसे साबित कर सकता हूं कि यह व्याकरण संदिग्ध है?
क्या कोई मुझे एक स्ट्रिंग दे सकता है जो इसे साबित कर सकता है।
संदर्भ-मुक्त व्याकरण संदिग्ध साबित करने के लिए कोई आसान तरीका नहीं है - वास्तव में the question is undecidable, Post correspondence problem में कमी से।
हाँ लेकिन मैं इसे उत्तर पत्र पर नहीं लिख सकता । व्याकरण के कौन से गुण मुझे स्ट्रिंग का सही चयन करने के लिए देखना चाहिए जो 2 पार्स पेड़ों को जन्म देता है? – crowso
@user: होपक्रॉफ्ट और उलमैन की मेरी प्रति के अनुसार, आपको "aaabbabbba" स्ट्रिंग पर विचार करना चाहिए, और आपके द्वारा निर्दिष्ट व्याकरण का उपयोग करके बाएं व्युत्पन्न, एक सही व्युत्पन्न, और एक पार्स पेड़ ढूंढना चाहिए। उम्मीद है कि हाथ में 4.8 व्यायाम करने के समाधान के साथ, बाकी स्पष्ट हो जाएंगे! –
एक स्ट्रिंग के साथ आने का कोई तरीका है? – crowso
वहाँ एक स्ट्रिंग यह है: bbaaba
S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba
@crowso आपको इसे सही उत्तर के रूप में चुनना चाहिए – Yugi
मेरे लिए यह अपनी स्पष्ट तरह दिखता है। – crowso
मुझे स्टैक ओवरफ्लो में आपका स्वागत करने की अनुमति दें और तीन चीजों को याद दिलाएं जो हम आम तौर पर यहां करते हैं: 1) जब आप सहायता प्राप्त करते हैं, तो इसे विशेषज्ञता के क्षेत्र में ** ** प्रश्नों का उत्तर देने का प्रयास करें ** ['एफएक्यू पढ़ें]] (http://tinyurl.com/2vycnvr) 3) जब आप अच्छे क्यू एंड ए देखते हैं, तो उन्हें 'ग्रे त्रिकोणों का उपयोग करके] [http://i.imgur.com/kygEP.png) का वोट दें, की विश्वसनीयता के रूप में प्रणाली उस प्रतिष्ठा पर आधारित है जो उपयोगकर्ताओं को अपना ज्ञान साझा करके हासिल होती है। यह भी याद रखना याद रखें कि आपकी समस्या, यदि कोई हो, तो बेहतर है, ['चेकमार्क साइन दबाकर] [http://i.imgur.com/uqJeW.png) –