प्रसंग-मुक्त व्याकरण में अस्पष्टता

यदि एक संदर्भ मुक्त व्याकरण G कुछ स्ट्रिंग के लिए एक से अधिक व्युत्पन्न वृक्ष हैं w ∈ L(G), यह एक कहा जाता है ambiguous grammar। उस व्याकरण से उत्पन्न कुछ स्ट्रिंग के लिए बहु-दाएं या बाएं-सबसे व्युत्पन्न मौजूद हैं।

मुसीबत

जाँच करें कि क्या उत्पादन नियमों के साथ व्याकरण जी -

X → X + X | X * X | X | ए

अस्पष्ट है या नहीं।

समाधान

चलो स्ट्रिंग के लिए व्युत्पन्न पेड़ का पता लगाते हैं "a + a * a"। इसकी दो सबसे बाईं व्युत्पन्नियाँ हैं।

Derivation 1- एक्स → एक्स + एक्स → ए + एक्स → ए + एक्स * एक्स → ए + ए * एक्स → ए + ए * ए

Parse tree 1 -

Derivation 2- एक्स → एक्स * एक्स * एक्स → एक्स + एक्स * एक्स → ए + एक्स * एक्स → ए + ए * एक्स → ए + ए * ए

Parse tree 2 -

चूँकि एकल स्ट्रिंग "a + a * a", व्याकरण के लिए दो पार्स पेड़ हैं G अस्पष्ट है।