✖

NFA का DFA में रूपांतरण

हम दिखाएँगे कि अनियतात्मक ऑटोमेटा को नियतात्मक ऑटोमेटा में कैसे बदला जाता है। इससे हम सिद्ध करेंगे कि अनियतात्मक और नियतात्मक ऑटोमेटा की अभिकलन क्षमता (computational power) तुल्य है।

आधारभूत विचार

मान लीजिए एप्सिलॉन संक्रमणों के बिना एक अनियतात्मक ऑटोमेटा ⟨QN, ΣN, δN, q0, FN⟩ है। हम नियतात्मक ऑटोमेटा ⟨QD, ΣD, δD, p0, FD⟩ इस प्रकार बनाते हैं कि

  • QD ⊆ 2QN
  • ΣD = ΣN
  • p0 = {q0}
  • FD = {Q ∈ QD | Q ∩ FN ≠ ∅}

संक्रमण फलन δD को हम इस प्रकार परिभाषित करते हैं:

∀Q∈QD,a∈ΣD:δD(Q,a)=⋃q∈QδN(q,a)

इसका क्या अर्थ है? अनियतात्मक ऑटोमेटा एक साथ कई अवस्थाओं में हो सकता है; उदाहरण के लिए, ऐसी स्थिति आ सकती है कि हमारा अनियतात्मक ऑटोमेटा अवस्थाओं {q0, q1} में है। अगला प्रतीक, मान लीजिए 1, पढ़ने पर हम अवस्थाओं के समुच्चय {q0, q2, q3} में पहुँच सकते हैं। उसी ऑटोमेटा के नियतात्मक रूप में यह ऐसे दिखेगा: हम दो अवस्थाएँ बनाते हैं, उनके नाम {q0, q1} और {q0, q2, q3} रखते हैं और उनके बीच प्रतीक 1 का संक्रमण बना देते हैं। औपचारिक रूप से हम एक अवस्था से दूसरी अवस्था में पहुँचते हैं, परंतु नामों के कारण हमें पता रहेगा कि अनियतात्मक ऑटोमेटा में हम क्रमशः दो और तीन अवस्थाओं में होते।

उदाहरण

मान लीजिए यह अनियतात्मक ऑटोमेटा है:

नियतात्मक ऑटोमेटा बनाने के लिए हमें सबसे पहले नया संक्रमण फलन बनाना होगा। इसमें एक सारणी हमारी सहायता करेगी, जिसमें हम सभी संक्रमण लिखेंगे। शुरुआत में सारणी ऐसी दिखती है:

अवस्था/प्रतीक01{q0}

एल्गोरिद्म के अंत में बाएँ स्तंभ में नियतात्मक ऑटोमेटा की सभी अवस्थाएँ होंगी। भरी हुई सारणी हमें संक्रमण फलन देगी। अब हम सारणी में लिखते हैं कि यदि हम अवस्थाओं {q0} में हैं और इनपुट पर प्रतीक 0 और 1 हैं, तो हम किन अवस्थाओं में पहुँचते हैं।

अवस्था/प्रतीक01{q0}{q1}{q1,q2}

अवस्था q0 से प्रतीक 0 का संक्रमण केवल अवस्था q1 में जाता है, जबकि प्रतीक 1 के संक्रमण अवस्थाओं q1 और q2 में जाते हैं। अब हम सारणी में दो नई अवस्थाएँ जोड़ते हैं: {q1} और {q1, q2}। क्यों? जैसे ही हम सारणी में अवस्थाओं का कोई ऐसा समुच्चय भरते हैं, जो अभी बाएँ स्तंभ में नहीं है, हम अवस्थाओं के इस समुच्चय को वहाँ जोड़ देते हैं।

अवस्था/प्रतीक01{q0}{q1}{q1,q2}{q1}{q1,q2}

और फिर से भरते हैं। अवस्था {q1, q2} के लिए हमें दोनों अवस्थाएँ जाँचना नहीं भूलना है, अर्थात् अवस्था q1 से हम जहाँ पहुँचते हैं, उसका उस समुच्चय से सम्मिलन, जहाँ हम अवस्था q2 से पहुँचते हैं।

अवस्था/प्रतीक01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}

हमें कुछ नई अवस्थाएँ मिलीं, जिन्हें सारणी में जोड़ना होगा:

अवस्था/प्रतीक01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q3}

…और फिर से संक्रमण भरते हैं:

अवस्था/प्रतीक01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}

अवस्थाएँ {q0, q1, q3}, {q1} और {q1,q2} पहले से सारणी में हैं, इसलिए हम केवल अवस्था {q0,q1,q2,q3} जोड़ते हैं।

अवस्था/प्रतीक01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}{q0,q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}

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

हम दिखा सकते हैं कि ऑटोमेटा वास्तव में सही काम करता है। आइए, स्ट्रिंग 11001 को स्वीकार करने का प्रयास करें। नियतात्मक ऑटोमेटा में हम इस रास्ते पर चलेंगे

q0→1q1,q2→1q0,q3→0q1→0q0,q1,q3→1q0,q1,q2,q3

और ऑटोमेटा स्ट्रिंग स्वीकार कर लेगा, क्योंकि जिस अवस्था {q0, q1, q2, q3} में हम अंत में पहुँचे, वह स्वीकारक (अंतिम) अवस्था है। अनियतात्मक ऑटोमेटा में अनुकरण के दौरान हम इन्हीं अवस्थाओं में पहुँचते: हम अवस्था q0 में शुरू करते और प्रतीक 1 पर अवस्थाओं {q1, q2} में पहुँचते। अगला प्रतीक 1 हमें अवस्थाओं {q0,q3} में पहुँचाता, और आगे की अवस्थाओं के लिए भी इसी तरह। अंत में हम सभी अवस्थाओं {q0, q1, q2, q3} में होते और ऑटोमेटा स्ट्रिंग स्वीकार कर लेता।

स्रोत

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