Automata machines: ऑटोमेटा एक प्रकार की मशीन है जो इनपुट के रूप में कुछ स्ट्रिंग लेती है और यह इनपुट सीमित संख्या में राज्यों से होकर गुजरती है और अंतिम स्थिति में प्रवेश कर सकती है।
ऑटोमेटा का सिद्धांत कंप्यूटर विज्ञान और गणितीय की एक सैद्धांतिक शाखा है। यह अमूर्त मशीनों और संगणना समस्याओं का अध्ययन है जिन्हें इन मशीनों का उपयोग करके हल किया जा सकता है। अमूर्त मशीन को ऑटोमेटा कहा जाता है। ऑटोमेटा सिद्धांत को विकसित करने के पीछे मुख्य प्रेरणा अलग-अलग प्रणालियों के गतिशील व्यवहार का वर्णन और विश्लेषण करने के तरीकों को विकसित करना था।
इस ऑटोमेटन में अवस्थाएँ और संक्रमण शामिल हैं। राज्य को वृत्तों द्वारा दर्शाया जाता है, और संक्रमण को तीरों द्वारा दर्शाया जाता है।
ऑटोमेटा सिद्धांत अमूर्त मशीनों और ऑटोमेटा के साथ-साथ कम्प्यूटेशनल समस्याओं का अध्ययन है जिन्हें उनका उपयोग करके हल किया जा सकता है। यह सैद्धांतिक कंप्यूटर विज्ञान में एक सिद्धांत है। ऑटोमेटा शब्द ग्रीक शब्द αὐτόματος से आया है, जिसका अर्थ है “स्व-अभिनय, स्व-इच्छाधारी, स्व-चालित”।
Automata –
ऑटोमेटन (बहुवचन में ऑटोमेटा) एक अमूर्त स्व-चालित कंप्यूटिंग उपकरण है जो स्वचालित रूप से संचालन के पूर्व निर्धारित अनुक्रम का पालन करता है। राज्यों की एक सीमित संख्या वाले एक ऑटोमेटन को परिमित ऑटोमेटन (एफए) या परिमित-राज्य मशीन (एफएसएम) कहा जाता है। दाईं ओर का चित्र एक परिमित-राज्य मशीन को दर्शाता है, जो एक प्रसिद्ध प्रकार का ऑटोमेटन है। इस ऑटोमेटन में स्थितियाँ (आकृति में वृत्तों द्वारा दर्शाई गई) और संक्रमण (तीरों द्वारा दर्शाई गई) शामिल हैं।
जैसे ही ऑटोमेटन इनपुट का एक प्रतीक देखता है, यह अपने संक्रमण फ़ंक्शन के अनुसार किसी अन्य राज्य में संक्रमण (या छलांग) करता है, जो पिछले राज्य और वर्तमान इनपुट प्रतीक को अपने तर्क के रूप में लेता है।
परिमित ऑटोमेटा – Finite
Automata in hindi
पैटर्न को पहचानने के लिए परिमित ऑटोमेटा का उपयोग किया जाता है।
यह प्रतीक की स्ट्रिंग को इनपुट के रूप में लेता है और तदनुसार अपनी स्थिति बदलता है। जब वांछित प्रतीक मिल जाता है, तब संक्रमण होता है।
संक्रमण के समय, ऑटोमेटा या तो अगली स्थिति में जा सकता है या उसी स्थिति में रह सकता है।
परिमित ऑटोमेटा में दो अवस्थाएँ होती हैं, राज्य स्वीकार करें या राज्य अस्वीकार करें। जब इनपुट स्ट्रिंग सफलतापूर्वक संसाधित हो जाती है, और ऑटोमेटा अपनी अंतिम स्थिति में पहुंच जाता है, तो यह स्वीकार हो जाएगा।
एफए की औपचारिक परिभाषा
एक परिमित ऑटोमेटन 5-ट्यूपल (Q, ∑, δ, q0, F) का एक संग्रह है
परिमित ऑटोमेटा मॉडल:
परिमित ऑटोमेटा को इनपुट टेप और परिमित नियंत्रण द्वारा दर्शाया जा सकता है।
इनपुट टेप: यह एक रैखिक टेप है जिसमें कुछ संख्या में सेल होते हैं। प्रत्येक इनपुट प्रतीक प्रत्येक कक्ष में रखा गया है।
परिमित नियंत्रण:
परिमित नियंत्रण इनपुट टेप से विशेष इनपुट प्राप्त करने पर अगली स्थिति तय करता है।
टेप रीडर कोशिकाओं को बाएँ से दाएँ एक-एक करके पढ़ता है, और एक समय में केवल एक इनपुट प्रतीक पढ़ा जाता है।
ऑटोमेटा के प्रकार:
परिमित ऑटोमेटा दो प्रकार के होते हैं:
DFA (नियतात्मक परिमित ऑटोमेटा)
NFA (गैर-नियतात्मक परिमित ऑटोमेटा)
1. DFA
डीएफए नियतात्मक परिमित ऑटोमेटा को संदर्भित करता है। नियतिवाद का तात्पर्य गणना की विशिष्टता से है। डीएफए में, मशीन केवल एक विशेष इनपुट कैरेक्टर के लिए एक स्थिति में जाती है। डीएफए शून्य कदम को स्वीकार नहीं करता है।
2. NFA
एनएफए का मतलब गैर-नियतात्मक परिमित ऑटोमेटा है। इसका उपयोग किसी विशेष इनपुट के लिए किसी भी संख्या में राज्यों को प्रसारित करने के लिए किया जाता है। यह अशक्त चाल को स्वीकार कर सकता है।
डीएफए और एनएफए के बारे में कुछ महत्वपूर्ण बिंदु:
प्रत्येक डीएफए एनएफए है, लेकिन एनएफए डीएफए नहीं है।
एनएफए और डीएफए दोनों में कई अंतिम स्थितियाँ हो सकती हैं।
डीएफए का उपयोग कंपाइलर में लेक्सिकल विश्लेषण में किया जाता है।
एनएफए एक सैद्धांतिक अवधारणा से अधिक है।