मुझे जावा में एक एनएफए अनुकरण करने के लिए एक असाइनमेंट दिया गया है। अब निम्नलिखित नियमित अभिव्यक्ति है कि मुझेजावा में एनएफए सिमुलेशन
ab*((b|d)|c*)
मुझे लगता है कि मेरे पास बहुत सारे ई-प्रतीक हैं। मैं बस सोच रहा था कि नीचे दी गई निम्नलिखित छवि सही है या नहीं।
आपका NFA ग्राफ सही है। यह regex ab*((b|d)|c*) से मेल खाएगा और कुछ भी नहीं। हालांकि, यह बहुत आसान हो सकता है, उदा। इस तरह:
मुझे नहीं लगता कि यह पूरी तरह से सही है, शाखाकरण भाग '((बी | डी) | सी *)' दो शाखाएं हैं, तीन नहीं, यह या तो (बी | डी) या सी * है, इसलिए आपके 'बी' से नोड यह प्रतिनिधित्व करने के लिए और अधिक सटीक नहीं होगा कि एक पूरी तरह से अलग पथ के रूप में जो तब 'बी' या 'डी' में शाखाएं हों? –
मुझे यकीन है कि ऊपर वाला एक थॉम्पसन निर्माण का उपयोग नहीं कर रहा है। यह छोटा है लेकिन मुझे अपने व्याख्याता द्वारा इसे कैसे किया जाए, इसकी शैली दी गई थी। – unleashed
@unleashed मैं कहूंगा कि थॉम्पसन एक एनएफए बनाने के लिए एक एल्गोरिदम (एक प्रक्रिया) है, न कि एनएफए का एक प्रकार। आप थॉम्पसन के साथ बनाई गई चीज़ के रूप में अपना एनएफए देख सकते हैं और फिर अनुकूलित कर सकते हैं। (बीटीडब्ल्यू: सवाल यह था कि आपका एनएफए आपकी नियमित अभिव्यक्ति के बराबर है। वहां थॉमसन के बारे में कुछ भी नहीं :-)) –
नोड्स 10, 11, 12 और 13 शायद सिर्फ दो नोड्स के रूप में घनीभूत जा सकता है? –
यही वह है जो मैंने शुरुआत में किया था लेकिन व्याख्याता इसे दोहराने के लिए उपरोक्त शैली का उपयोग करना चाहता था और एनएफए बनाने के लिए थॉम्पसन निर्माण का उपयोग कर रहा था। मैं बस 2 से 3 ई संक्रमण, 3 से 4 ई संक्रमण और 4 से 5 या 4 से 7 ई संक्रमण के बारे में संदिग्ध हूं। – unleashed
ठीक है, 2-3 बी ''के मामलों में कम किया जा सकता है जिसके परिणामस्वरूप कोई भी बी नहीं है, आपके पास 1-2 से' e' संक्रमण होगा। इसके अलावा मुझे लगता है कि बाकी का यह उचित लगता है। आखिरकार अंतिम परिणाम वही है, केवल एक कम नोड। –