एनएफए से डीएफए प्रश्न

Question

सबसे पहले, यह एक सवाल नहीं है कि एल्गोरिदम को एनएफए को डीएफए में परिवर्तित करने के लिए कहा जाए।

यह ज्ञात (और साबित हुआ) कि एनएफए के बराबर डीएफए में 2 ^एन राज्य हैं, भले ही ज्यादातर बार एनएफए के रूप में राज्यों की संख्या उतनी ही कम हो।

एनएफए समकक्ष डीएफए के राज्यों की संख्या के अनुमान के बारे में मैं अनुमान कैसे लगा सकता हूं? किस विशेष प्रकार के एनएफए को 2 ^एन राज्यों के बराबर डीएफए की आवश्यकता होगी?

यह पूछने का मेरा कारण कुछ एनएफए "आविष्कार" करने में सक्षम होना है जो निश्चित रूप से कम से कम उत्पादन के बिना उत्पादन करेगा, 2 ^एन - 1 राज्यों के साथ "मृत राज्य"।

Answer 1

राज्यों फट की संख्या गैर नियतिवाद की वजह से है, जो आपके प्रश्न की कुंजी है।

यदि आप एक एनएफए लेते हैं, जहां प्रत्येक संक्रमण विशिष्ट रूप से निर्धारित किया जाता है, यानी एक निर्धारक एनएफए, तो यह सामान्य डीएफए के अलावा कुछ भी नहीं है। हालांकि, एक बार जब आपके पास ऐसा राज्य होता है जहां दो संक्रमण संभव होते हैं तो यह डीएफए से अलग होता है।

रूपांतरण एल्गोरिदम पर विचार करें और देखें कि क्या होता है यदि आपके पास एक राज्य के लिए एक ही लेबल के साथ दो या दो से अधिक संक्रमण हैं। यह वह जगह है जहां आपको उन नए राज्यों की आवश्यकता है जो राज्यों के सेट के अनुरूप हैं।

तो प्रश्न यह पता लगाने के लिए नीचे आता है कि इनमें से कितने सुपरसेट राज्य वास्तव में पहुंच योग्य हैं। बेशक आप इसके लिए एक फैंसी एल्गोरिदम का आविष्कार कर सकते हैं, लेकिन सही संख्या प्राप्त करने के लिए, सामान्य रूपांतरण एल्गोरिदम चलाएं और पहुंचने योग्य राज्यों को हटा दें।

एन राज्यों के साथ एनएफए के लिए, जिसके लिए समकक्ष डीएफए में 2^एन राज्य गैर-निर्धारणा का शोषण करने के बारे में सोचते हैं। पहला विचार सभी संक्रमणों को लेबल करना होगा, हालांकि, यह बहुत अच्छी तरह से काम नहीं करता है। इसके बजाए याद रखें कि आपको कुछ लेबलों के साथ राज्यों के सभी सबसेट तक पहुंचने में सक्षम होना चाहिए।

यदि आप प्रारंभिक स्थिति की गणना नहीं करते हैं, तो आप निम्न निर्माण कर सकते हैं: एन नोड्स बनाएं और 2^n के प्रत्येक सेट के लिए एक अद्वितीय लेबल बनाएं और एनएफए में प्रत्येक लेबल में इस लेबल के साथ एक संक्रमण जोड़ें उस सेट का। यह आपको एन + 1 राज्यों (1 प्रारंभिक राज्य होने) के साथ एक एनएफए देता है, जहां डीएफए को 2^एन +1 राज्यों की आवश्यकता होती है। बेशक, यह कम हो जाने के बाद 2^एन डीएफए राज्यों को प्राप्त करने के बाद, यह मुश्किल हो जाता है।

Answer 2

ठीक है, धारणा से शुरू करें कि n -> n। अब, प्रत्येक गैर-निर्धारिती संक्रमण के लिए जहां एक राज्य से आप एक्स अन्य राज्यों में समाप्त हो सकते हैं, एक्स द्वारा अपने अनुमान को गुणा करें। यह सटीक नहीं हो सकता है, क्योंकि आप डबल-गिन सकते हैं। लेकिन यह आपको ऊपरी बाउंड देना चाहिए।

हालांकि, यह एकमात्र निश्चित तरीका है कि यह एक संबंधित डीएफए बनाने के लिए और फिर राज्यों (मुझे लगता है) की गणना करें।

अंत में, आप शायद DFAs (और उस बात के लिए NFAs) में से कुछ को आसान बनाने में कर सकते हैं, लेकिन यह एक पूरी नई कहानी है ...

Answer 3

साथ शुरू राज्य एस और अंतिम अवस्था एन, इस NFA A(N) एन के एक समारोह के रूप में लेने,:

S a-> S 
S b-> S 
S a-> 0 // NOTE: only "a" allows you to leave state S 
0 a-> 1 
0 b-> 1 
1 a-> 2 
1 b-> 2 
... 
N-1 a-> N 
N-2 b-> N 
N 

यह स्पष्ट है कि इस [ab]* जिसका वां-से-अंतिम अक्षर है में सभी स्ट्रिंग्स को स्वीकार करता है होना चाहिए a।

A(N) की determinization प्रभावी रूप से (आप इतनी है कि जब स्ट्रिंग अप्रत्याशित रूप से समाप्त हो जाती है, आप कह सकते हैं कि क्या वहाँ एक a था, उस खिड़की कि a थे में सभी पदों जानने की जरूरत पिछले N-1 पत्र याद करने के लिए है, एन पत्र पहले)।

मुझे यकीन नहीं है कि यह वास्तव में आपके इच्छित राज्यों की संख्या को हिट करता है, लेकिन यह कम से कम 2 के कारक के भीतर है - {0,...,N} के सभी सबसेट संभव हैं, लेकिन आप हमेशा S में भी हैं। यह 2^(N+1) राज्य होना चाहिए, लेकिन A(N) में N+2 राज्य थे।

Answer 4

जोनाथन ग्रेहल के उत्कृष्ट उत्तर पर आगे बढ़ने के लिए।

प्रत्येक राज्य A(N) की 0, 1, ..., N एक selfloop लेबल c, यानी, आप निम्नलिखित संक्रमण जोड़ने के लिए जोड़ें:
0 c-> 0
1 c-> 1
...
N c-> N

फिर c कभी नहीं आग संभालने, DFA शामिल जोनाथन के डीएफए के राज्य 2^(N+1) राज्य। हालांकि, जब भी c एक राज्य {S,j,k,...,z} <> {S} से मनाया जाता है तो हम राज्य {j,k,...,z} तक पहुंचते हैं। इसलिए {S,0,...,N} के सभी सबसेट खाली सेट को छोड़कर संभव हैं और डीएफए में 2^(N+2)-1 राज्य हैं जबकि A(N) में N+2 राज्य हैं।