✖

पूर्ण ऑटोमेटा

परिमित ऑटोमेटा की आधारभूत परिभाषा में यह आवश्यक नहीं है कि प्रत्येक अवस्था से सभी प्रतीकों के लिए संक्रमण मौजूद हो। पूर्ण ऑटोमेटा (complete automaton) वह ऑटोमेटा है, जिसमें सभी अवस्थाओं से इनपुट वर्णमाला के सभी प्रतीकों के लिए संक्रमण परिभाषित होते हैं।

पूर्ण ऑटोमेटा कैसे बनाएँ

मान लीजिए यह ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ है:

यहाँ अवस्था q0 से अक्षर “b” के लिए कोई संक्रमण नहीं बनाया गया है। यदि ऐसी स्थिति आए, तो हम कहते हैं कि ऑटोमेटा दी गई इनपुट स्ट्रिंग को स्वीकार नहीं करता। फिर भी औपचारिकता की दृष्टि से यह उचित नहीं हो सकता कि संक्रमण फलन δ कुछ मानों के लिए परिभाषित न हो; यहाँ, उदाहरण के लिए, यह δ(q0, b) के लिए परिभाषित नहीं है।

इसे आसानी से सुलझाया जा सकता है: हम एक तुल्य ऑटोमेटा बनाते हैं, जिसमें एक अवस्था अधिक होगी। “छूटे हुए” संक्रमण इसी अवस्था में जाएँगे, यह अवस्था अंतिम नहीं होगी और आगे के सभी इनपुट इसी अवस्था में लूप करेंगे। ऐसे ऑटोमेटा को हम पूर्ण ऑटोमेटा कहते हैं। संशोधित तुल्य ऑटोमेटा कुछ ऐसा दिख सकता है:

हमने अवस्था qfail जोड़ी है। अन्य अवस्थाओं से इसमें संक्रमण हमने तभी जोड़ा है, जब पहले वहाँ कोई संक्रमण नहीं था। यह अवस्था अंतिम नहीं है और आगे के सभी इनपुट के लिए इसमें लूप है। इसलिए यदि पिछले ऑटोमेटा में हमें कोई छूटा हुआ संक्रमण मिलता, तो यहाँ कोई संक्रमण छूटा हुआ नहीं है और ऑटोमेटा अवस्था qfail में पहुँच जाता।

इस प्रकार हम व्यापकता की हानि के बिना हमेशा मान सकते हैं कि ऑटोमेटा में अवस्थाओं और वर्णमाला के अक्षरों के सभी संयोजनों के लिए संक्रमण परिभाषित हैं।

परिभाषा

इस प्रकार पूर्ण ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ के लिए

∀q∈Q∀a∈Σ∃r∈Q:δ(q,a)=r.

स्रोत

विषय-सूची: परिमित ऑटोमेटा, पूर्ण ऑटोमेटा, अनियतात्मक परिमित ऑटोमेटा, अनियतात्मक ऑटोमेटा का अनुकरण, NFA का DFA में रूपांतरण