✖

ऑटोमेटा का न्यूनीकरण

ऑटोमेटा के न्यूनीकरण (minimisation) से हमारा अर्थ है ऐसा तुल्य ऑटोमेटा ढूँढना, जिसमें अवस्थाओं की संख्या न्यूनतम संभव हो। ऐसे ऑटोमेटा को भी, जिसमें कोई अनावश्यक अवस्था नहीं है, और सरल बनाया जा सकता है।

उदाहरण

यह ऑटोमेटा लीजिए:

यह ऑटोमेटा केवल स्ट्रिंगें 01 और 11 स्वीकार करता है। साथ ही यह स्पष्ट है कि तीन अवस्थाओं वाला एक सरल ऑटोमेटा मौजूद है, जो वही भाषा स्वीकार करता है। अवस्थाओं q1 और q2 को एक नई अवस्था {q1, q2} में मिलाया जा सकता है; जो संक्रमण अवस्था q1 या q2 में जाते थे, वे नई अवस्था में जाएँगे, और q1 तथा q2 से निकलने वाले संक्रमणों के लिए भी यही होगा। हमें यह ऑटोमेटा मिलता है:

यह ऑटोमेटा स्पष्ट रूप से पिछले वाले जैसी भाषा ही स्वीकार करता है और साथ ही इसमें कम अवस्थाएँ हैं।

अवस्थाओं की तुल्यता

मान लीजिए ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ है। अवस्था q ∈ Q की भाषा, जिसे L(q) से दर्शाते हैं, हम इस प्रकार परिभाषित करते हैं

L(q)=L(⟨Q,Σ,δ,q,F⟩)

अर्थात् हम ऑटोमेटा A की प्रारंभिक अवस्था q0 से बदलकर q कर देते हैं और इस ऑटोमेटा द्वारा स्वीकृत भाषा ज्ञात करते हैं। दूसरे शब्दों में, भाषा L(q) में वे सभी स्ट्रिंगें w हैं, जिनके लिए ऑटोमेटा A में हम अवस्था q से स्ट्रिंग w पढ़कर ऑटोमेटा की किसी अंतिम अवस्था में पहुँचते हैं। पिछले ऑटोमेटा पर लौटें, तो L(q1) = {1} है।

हम कहते हैं कि दो भिन्न अवस्थाएँ q1 और q2 तुल्य हैं, यदि

L(q1)=L(q2)

इसका क्या अर्थ है? यदि अवस्थाएँ q1, q2 तुल्य हैं और हम उन्हें ऑटोमेटा की प्रारंभिक अवस्था बना दें, तो वे एक ही भाषा जनित करेंगी। दूसरे शब्दों में: यदि ऑटोमेटा विन्यास ⟨q1, w⟩ और ⟨q2, w⟩ में पहुँचे, तो उसे या तो दोनों स्थितियों में स्वीकार करना होगा या दोनों में अस्वीकार।

पिछले ऑटोमेटा पर लौटें: अवस्थाएँ q1 और q2 तुल्य हैं, क्योंकि यदि हम अवस्था q1 में हैं, तो इनपुट स्ट्रिंग तभी स्वीकार हो सकती है, जब स्ट्रिंग का न पढ़ा गया भाग 1 के बराबर हो। यही बात अवस्था q2 के लिए भी है।

इसलिए ऑटोमेटा के न्यूनीकरण में लक्ष्य तुल्य अवस्थाएँ ढूँढना और उन्हें हटाना है: हम उन्हें एक नई अवस्था में मिला देते हैं, जैसा हमने ऊपर के उदाहरण में किया।

तुल्य अवस्थाएँ कैसे ढूँढें

कौन-सी अवस्थाएँ निश्चित रूप से तुल्य नहीं होंगी? यदि हम एक अंतिम और एक गैर-अंतिम अवस्था लें, तो वे निश्चित रूप से तुल्य नहीं होंगी, क्योंकि अंतिम अवस्था की भाषा गैर-अंतिम अवस्था की भाषा से भिन्न है — अंतिम अवस्था स्ट्रिंग ε को निश्चित रूप से स्वीकार करती है, गैर-अंतिम नहीं। विधि हम सीधे एक उदाहरण पर दिखाएँगे। मान लीजिए यह ऑटोमेटा है:

हम अवस्थाओं के दो समुच्चय बनाकर शुरू करते हैं

S1=F={q3,q6},S2=Q∖F={q0,q1,q2,q4,q5}.

अब हम संक्रमण सारणी बनाते हैं और समूहों S1 और S2 की जानकारी बनाए रखते हैं:

समूहअवस्था01S1q3q5q4q6——S2q0q1q2q1—q3q2—q3q4q6—q5q6—

अब हम सारणी को इस तरह बदलते हैं कि उसमें सीधे यह लिखने के बजाय कि दिए गए प्रतीक पर हम किस अवस्था में जाते हैं, हम केवल वह समूह लिखते हैं, जिसमें हम जाते हैं। उदाहरण के लिए, अवस्था q3 से 0 पर हम अवस्था q5 में पहुँचते हैं, जो समूह S2 में है। इसलिए q5 के स्थान पर हम सारणी में S2 लिखते हैं:

समूहअवस्था01S1q3S2S2q6——S2q0S2S2q1—S1q2—S1q4S1—q5S1—

अब हम दोनों समूहों को और विभाजित करते हैं। एक समूह में हम हमेशा वे अवस्थाएँ रखते हैं, जो सभी प्रतीकों के लिए समान समूहों में जाती हैं। उदाहरण के लिए, अवस्थाएँ q3 और q6 एक समूह में नहीं होंगी, क्योंकि न 0 के लिए, न 1 के लिए वे एक ही समूह में जाती हैं। इसके विपरीत, अवस्थाएँ q1 और q2 एक समूह में होंगी, क्योंकि दोनों अवस्थाओं में 0 के लिए कोई संक्रमण नहीं है और दोनों 1 के लिए समूह S1 में जाती हैं। इस तरह हम नए समूह बनाते हैं:

समूहअवस्था01q3S2S2q6——q0S2S2q1—S1q2—S1q4S1—q5S1—

प्रत्येक समूह में हमारे संक्रमण समान हैं। नए बने समूहों को हम नाम देते हैं और फिर से देखते हैं कि अवस्थाएँ इन नए समूहों में से किसकी ओर जाती हैं:

समूहअवस्था01S1q3S5S5S2q6——S3q0S4S4S4q1—S1q2—S1S5q4S2—q5S2—

इस समय हम समूहों का अगला विभाजन करते हैं। परंतु हम देखते हैं कि अब कोई और विभाजन नहीं किया जा सकता, हमें वही समूह मिलेंगे — अवस्थाओं q1 और q2 के संक्रमण समूहों के स्तर पर समान हैं, परंतु वे पहले से एक ही समूह में हैं और समूह S4 में कोई और अवस्था नहीं है। तुल्य अवस्थाएँ ढूँढने का एल्गोरिद्म समाप्त हो गया है। प्रत्येक समूह से हमें केवल एक अवस्था चुननी है, बाकी को हटा देते हैं, और जो संक्रमण हटाई गई अवस्थाओं में जाते थे, वे सब उस एक चुनी हुई अवस्था में जाएँगे।

इसलिए हम चुन सकते हैं कि हमारे नए ऑटोमेटा में अवस्थाएँ q3, q6, q0, q1, q4 होंगी और अवस्थाएँ q2 और q5 हम हटा देंगे। जो संक्रमण q2 में जाते थे, वे अब q1 में जाएँगे, और जो संक्रमण q5 में जाते थे, वे q4 में जाएँगे:

ऑटोमेटा के न्यूनीकरण की विधि

  1. अगम्य अवस्थाएँ हटाइए,
  2. अनावश्यक अवस्थाएँ हटाइए,
  3. तुल्य अवस्थाएँ हटाइए।

स्रोत

विषय-सूची: अगम्य अवस्थाएँ, अनावश्यक अवस्थाएँ, ऑटोमेटा का न्यूनीकरण