मैं अपने लेक्सर में एक डीएफए मिनीमाइज़र को लागू करने के लिए देख रहा हूं, लेकिन मुझे ऐसा लगता है कि यह पहले से ही न्यूनतम डीएफए नहीं है अभिव्यक्ति।नियमित अभिव्यक्ति जो मृत या अनावश्यक राज्यों के साथ एक डीएफए उत्पन्न करती है
मैं एक एनएफए से डीएफए का निर्माण कर रहा हूं जो पोस्टफिक्स नियमित अभिव्यक्ति से थॉमसन निर्माण का उपयोग करके बनाया गया है। ड्रैगन पुस्तक में वर्णित यह बिल्कुल काफी है। लेक्सर बनाने के लिए एनएफए के कई प्रारंभिक राज्य से ईपीएसलॉन संक्रमण का उपयोग करके संयुक्त होते हैं। यह संयुक्त एनएफए पर है कि डीएफए एल्गोरिदम लागू किया गया है।
तो, क्या कोई "ज्ञात" नियमित अभिव्यक्ति है जो एक डीएफए उत्पन्न करेगी जो मृत राज्य उन्मूलन और राज्य न्यूनीकरण के लिए एक अच्छा परीक्षण बिस्तर बनाती है?
मैं निश्चित रूप से केवल एक अजीब डीएफए को हैक कर सकता हूं और उस पर एल्गोरिदम लागू कर सकता हूं, लेकिन यह वास्तव में उचित परीक्षण केस नहीं होगा? यदि ऐसा है कि जिस विधि को मैं डीएफए बना रहा हूं वह मृत राज्यों से ग्रस्त नहीं है, तो वह जानकारी उतनी ही मूल्यवान होगी, तब से मैं राज्य उन्मूलन सुविधा को पूरी तरह से कार्यान्वित कर सकता हूं।
संपादित करें: मामले में आप आदेश सही ढंग से जवाब देने के लिए में कार्यान्वयन विवरण की जरूरत है, कोड, github पर उपलब्ध है विशेष रूप से NFA.cs और DFA.cs कक्षाएं। इसके अतिरिक्त मैंने निर्माण एल्गोरिदम पर blog posts पर एक श्रृंखला लिखी है, जिसका उपयोग मैं कर रहा हूं।