अनावश्यक अवस्थाएँ
परिमित ऑटोमेटा में ऐसी अवस्थाएँ हो सकती हैं, जिनसे अंतिम अवस्था तक पहुँचना संभव नहीं है और इसलिए वे बेकार हैं। ऐसी अवस्थाओं को हम अनावश्यक अवस्थाएँ (redundant states) कहते हैं। सामान्यतः हम इन अवस्थाओं को हटाना चाहते हैं, क्योंकि ये पूरे ऑटोमेटा को बेवजह जटिल बनाती हैं।
अनावश्यक अवस्थाओं का उदाहरण
मान लीजिए यह परिमित ऑटोमेटा है:
हम देखते हैं कि जैसे ही हम अवस्था q4 या q5 में पहुँचते हैं, हम फिर कभी अंतिम अवस्थाओं q1 या q2 में से किसी तक नहीं पहुँच पाएँगे। इसलिए ऐसी अवस्थाएँ अनावश्यक हैं और हम उन्हें बस हटा सकते हैं। इससे हमें एक नया ऑटोमेटा मिलेगा, जो फिर भी तुल्य होगा, यानी वही भाषा स्वीकार करेगा। अनावश्यक अवस्थाएँ हटाने के बाद ऑटोमेटा ऐसा दिखेगा:
और वह वही भाषा स्वीकार करेगा। फिर भी कभी-कभी कुछ अनावश्यक अवस्थाएँ रखना उपयोगी होता है — उदाहरण के लिए, जब हम पूर्ण ऑटोमेटा बनाते हैं।
अनावश्यक अवस्था की परिभाषा
मान लीजिए परिमित ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ है। हम कहते हैं कि अवस्था q ∈ Q अनावश्यक है, यदि कोई ऐसी स्ट्रिंग w ∈ Σ∗ और कोई ऐसी अवस्था qf ∈ F मौजूद न हो कि
अनावश्यक अवस्थाएँ कैसे हटाएँ
हम मानते हैं कि इनपुट पर ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ है, जिसमें पहले से कोई अगम्य अवस्था नहीं है। हम क्रमशः वे अवस्थाएँ ढूँढेंगे, जिनसे अंतिम अवस्थाओं तक पहुँचा जा सकता है, फिर वे अवस्थाएँ, जिनसे इन अवस्थाओं तक पहुँचा जा सकता है, और इसी तरह बार-बार। इस तरह हमें उन सभी अवस्थाओं का समुच्चय मिलेगा, जो अनावश्यक नहीं हैं। शुरुआत में हम S0 = F रखते हैं। आगे के समुच्चय Si, i ∈ ℕ के लिए, हम इस नियम से बनाएँगे:
उन सभी अवस्थाओं का परिणामी समुच्चय, जो अनावश्यक नहीं हैं, हम इस प्रकार व्यक्त कर सकते हैं:
और अनावश्यक अवस्थाओं का समुच्चय इस प्रकार
दूसरे शब्दों में: यदि Si = Si + 1 हो, तो समुच्चय Q ∖ Si में अनावश्यक अवस्थाएँ हैं। विधि को हम इस ऑटोमेटा पर समझाएँगे:
सबसे पहले हम समता S0 = {q1, q2} रखते हैं। आगे समुच्चय S1 बनाने के लिए हम समुच्चय S0 में वे सभी अवस्थाएँ जोड़ते हैं, जिनसे समुच्चय S0 की किसी अवस्था तक संक्रमण जाता है। इसलिए हम अवस्थाएँ q0 और q3 जोड़ते हैं, क्योंकि q0 से संक्रमण q1 में जाता है और q3 से संक्रमण q2 में। हमें S1 = {q0, q1, q2, q3} मिलता है। चूँकि S0 ≠ S1 है, हम आगे बढ़ते हैं।
अब हम समुच्चय S2 बनाते हैं। हम वे सभी अवस्थाएँ ढूँढते हैं, जिनसे S1 तक पहुँचा जा सकता है और जो अभी S1 में नहीं हैं। ऐसी केवल एक अवस्था है, q6, जिससे अवस्था q3 तक पहुँचा जा सकता है। हमें S2 = {q0, q1, q2, q3, q6} मिलता है। चूँकि S1 ≠ S2 है, हम आगे बढ़ते हैं।
अब हम समुच्चय S3 बनाते हैं। क्या कोई नई अवस्था है, जिससे S2 की किसी अवस्था तक पहुँचा जा सके? नहीं है: अवस्थाओं q4 और q5 से S2 की किसी भी अवस्था तक नहीं पहुँचा जा सकता और बाकी अवस्थाएँ पहले से S2 में हैं। इसलिए S3 = {q0, q1, q2, q3, q6} है। चूँकि S2 = S3 है, एल्गोरिद्म समाप्त हो जाता है और समुच्चय S2 उन अवस्थाओं का समुच्चय है, जो अनावश्यक नहीं हैं। समुच्चय {q4, q5} उन अवस्थाओं का समुच्चय है, जो अनावश्यक हैं।
औपचारिक रूप से अनावश्यक अवस्थाओं से रहित नया तुल्य ऑटोमेटा हम इस प्रकार बनाते हैं। ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ दिया है और हम इसके तुल्य, अनावश्यक अवस्थाओं से रहित ऑटोमेटा A′ = ⟨Q′, Σ, δ′, q0, F⟩ बनाते हैं।
- ∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a), यदि δ(q, a) ∈ Q′ हो, अन्यथा δ′(q, a) परिभाषित नहीं है
स्रोत
विषय-सूची: अगम्य अवस्थाएँ, अनावश्यक अवस्थाएँ, ऑटोमेटा का न्यूनीकरण