एनएफए आणि डीएफए मधील फरक.

NFA vs DFA

गणनाचा सिद्धांत म्हणजे संगणक शास्त्राची शाखा, जी एल्गोरिदम वापरून समस्यांचे निराकरण कसे करते यावर निगडीत आहे. त्याचे तीन शाखा आहेत, म्हणजे; कॉम्प्युटेशनल कॉम्प्लेमेसिटी थिअरी, कॉम्प्युटेबिलिटी थिअरी आणि ऑटोलॅनॉन थिअरी.

ऑटोमेशन किंवा ऑटोमेटा सिद्धांत हे गणितीय गणिती मशीन किंवा सिस्टमचा अभ्यास आहे जे संगणनात्मक समस्यांचे निराकरण करण्यासाठी वापरले जाऊ शकते. एक automaton राज्ये आणि संक्रमणे बनलेले आहे, आणि तो एक प्रतीक किंवा इनपुट पत्र पाहतो म्हणून, तो इनपुट म्हणून वर्तमान राज्य आणि प्रतीक घेऊन दुसर्या राज्यातील एक संक्रमण करते.

ऑटोमेटॉन किंवा ऑटोमेटा सिद्धांतामध्ये अनेक वर्ग आहेत जे डिस्ट्रिक्टिक फिनीट ऑटोमाटाटा (डीएफए) आणि नीन्डेटिमिनिस्टिक परिमित ऑटोमेशन (एनएफए) समाविष्ट करतात. हे दोन वर्ग automata किंवा automaton चे संक्रमण कार्य आहेत

संक्रमणामध्ये, डीएफए रिक्त स्ट्रिंग वापरू शकत नाही आणि हे एक मशीन म्हणून समजू शकते. एखादा अट मान्य राज्य नसलेली स्थितीवर स्ट्रिंग समाप्त होत असल्यास, DFA त्यास नकार देईल. डीएपीए मशीन प्रत्येक इनपुट आणि आउटपुटसह बांधली जाऊ शकते.

डीएफएमध्ये वर्णमालाच्या प्रत्येक चिन्हासाठी फक्त एक राज्य संक्रमण आहे आणि त्याचे संक्रमणाचे फक्त एकच अंर्तभूत अवयव आहे ज्याचा अर्थ आहे प्रत्येक अक्षर वाचण्यासाठी, डीएफएमध्ये एक समान राज्य आहे. डीएफएमध्ये सदस्यत्व तपासणे सोपे आहे पण बांधकाम करणे अधिक कठीण आहे. डीएफएमध्ये बॅकट्रॅकिंगची परवानगी आहे, आणि त्यास NFA पेक्षा जास्त जागेची आवश्यकता आहे.

बॅकएरेकिंगला नेहमी एनएफएमध्ये परवानगी नाही. काही प्रकरणांमध्ये हे शक्य असले तरी, इतरांमध्ये तसे नाही. हे एनएफए तयार करणे अधिक सोपा आहे, आणि त्यास कमी जागेचीही आवश्यकता आहे, परंतु प्रत्येक इनपुट आणि आउटपुटसाठी एनएफए मशीन तयार करणे शक्य नाही.

हे एकाच वेळी मोजण्यासाठी अनेक लहान मशीन समजले जातात आणि सदस्यता तपासणे कठीण होऊ शकते. हे एम्टी स्ट्रिंग ट्रान्सिशियन वापरते, आणि राज्य आणि इनपुट चिन्हाच्या प्रत्येक जोडीसाठी असंख्य संभाव्य पुढील स्थिती आहेत. हे एखाद्या विशिष्ट अवस्थेपासून सुरू होते आणि चिन्हे वाचते, आणि नंतर automaton पुढील स्थितीवर आधारीत असते जे वर्तमान इंपुट आणि अन्य परिणामस्वरूपी घटनांवर अवलंबून असते. त्याच्या स्वीकार्य स्थितीत, NFA स्ट्रिंग स्वीकारतो आणि अन्यथा तो नाकारतो.

सारांश:

1 "डीएफए" याचा अर्थ "डिटर्मिनेस्टिक कंटिटा ऑटमाटा" आहे तर "एनएफए" चा अर्थ "निवेदनेविज्ञानी परिमित ऑटोमाटा. "< 2 दोन्ही automata चे संक्रमण कार्य आहेत डीएफएमध्ये पुढील शक्य अवस्था स्पष्टपणे सेट केली जाते तर एनएफएमध्ये प्रत्येक जोडीचे राज्य आणि इनपुट चिन्हात बर्याच संभाव्य पुढील राज्ये असतील.

3 डीएफए रिक्त स्ट्रिंग संक्रमण वापरू शकत नसले तरी NFA रिक्त स्ट्रिंग संक्रमण वापरू शकते.

4 एनएफए बांधणे सोपे आहे, तर डीएफए तयार करणे अधिक कठीण आहे.

5 एनएफए मध्ये बॅकएरेकिंगला डीएफए मध्ये परवानगी आहे की ते कदाचित परवानगी देऊ शकतात किंवा नसतील.< 6 एनएफएला कमी जागेची आवश्यकता असताना DFA साठी अधिक जागा आवश्यक आहे. < 7 डीएफए एक यंत्र म्हणून समजू शकतो आणि प्रत्येक इनपुट आणि आऊटपुटसाठी डीएफए मशीन बांधता येत आहे. 8. एनएफए एकत्रितपणे गणना करणार्या अनेक छोटी मशीन समजल्या जाऊ शकतात आणि प्रत्येक इनपुट आणि आऊटपुटसाठी एनएफए मशीनची निर्मिती करण्याची शक्यता नाही.. <