✖

अगम्य अवस्थाएँ

परिमित ऑटोमेटा में ऐसी अवस्थाएँ हो सकती हैं, जिन तक पहुँचना संभव नहीं है। ऐसी अवस्थाओं को हम अगम्य अवस्थाएँ (unreachable states) कहते हैं। सामान्यतः हम इन अवस्थाओं को हटाना चाहते हैं, क्योंकि ये पूरे ऑटोमेटा को बेवजह जटिल बनाती हैं।

अगम्य अवस्थाओं का उदाहरण

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

हम देखते हैं कि हम कुछ भी करें, अवस्था q3 तक कभी नहीं पहुँचेंगे, क्योंकि उसकी ओर कोई संक्रमण नहीं जाता। इसलिए अवस्था q3 के बारे में हम कहते हैं कि वह अगम्य है। प्रश्न — यदि किसी दूसरी अवस्था से कोई संक्रमण अवस्था q3 की ओर जाता, तो क्या वह गम्य होती? यदि हम अवस्थाओं q0, q1, q2, q5 में से किसी एक से किनारा खींचते, तो वह गम्य होती। यदि हम एक और नोड जोड़ते और संक्रमण उससे खींचते…

…तो स्वाभाविक रूप से दोनों अवस्थाएँ q3 और q4 अगम्य होतीं।

अगम्य अवस्था की परिभाषा

सबसे पहले हम गम्य अवस्था परिभाषित करते हैं। मान लीजिए परिमित ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ है। हम कहते हैं कि अवस्था q ∈ Q गम्य है, यदि कोई ऐसी स्ट्रिंग w ∈ Σ∗ मौजूद हो कि

⟨q0,w⟩↦∗⟨q,ε⟩.

अवस्था q ∈ Q अगम्य है, यदि वह गम्य नहीं है।

अगम्य अवस्थाएँ कैसे हटाएँ

यदि ऑटोमेटा में पहले से कुछ अगम्य अवस्थाएँ हैं, तो उन्हें हटाना उचित है। इसलिए हम एक तुल्य ऑटोमेटा A′ = ⟨Q′, Σ, δ′, q0, F′⟩ बनाते हैं, जिसमें कोई अगम्य अवस्था नहीं होगी।

गम्य अवस्थाओं का समुच्चय हम पुनरावृत्ति से बनाएँगे। हम समुच्चय S0 = {q0} से शुरू करते हैं, क्योंकि प्रारंभिक अवस्था निश्चित रूप से गम्य है। अगला समुच्चय हम इस प्रकार बनाते हैं:

Si={r|δ(q,a)=r किसी q∈Si−1,a∈Σ के लिए}∪Si−1

सरल शब्दों में, समुच्चय S0 हमेशा दिया हुआ है। समुच्चय S1 बनाने के लिए हम समुच्चय S0 की सभी अवस्थाएँ लेते हैं और देखते हैं कि Σ के सभी प्रतीकों के संक्रमण कहाँ-कहाँ जाते हैं। इन अवस्थाओं का हम अवस्थाओं के पिछले समुच्चय S0 से सम्मिलन लेते हैं। इसी विधि से हम समुच्चय S2 और आगे के समुच्चय ज्ञात करते हैं। स्पष्ट है कि Si − 1 ⊆ Si होगा।

तब गम्य अवस्थाओं का समुच्चय हमें इस प्रकार मिलता है:

⋃i=1∞Si

यह अजीब लग सकता है कि हम अपरिमित रूप से अनेक समुच्चयों Si का सम्मिलन ले रहे हैं, परंतु ऑटोमेटा में अवस्थाओं की संख्या परिमित है। इसका अर्थ है कि किसी क्षण समुच्चय Sj और Sj + 1 तथा आगे के सभी समुच्चय बराबर हो जाएँगे, इसलिए अपरिमित रूप से अनेक समुच्चयों के सम्मिलन से भी हमें अवस्थाओं का परिमित समुच्चय मिल सकता है।

आइए, ऑटोमेटा

पर लौटें और गम्य अवस्थाओं का समुच्चय ज्ञात करें। हम आधारभूत समता से शुरू करते हैं

S0={q0}

अब हम समुच्चय S1 परिकलित करते हैं। इसके लिए हमें अवस्था q0 से निकलने वाले सभी संक्रमण ढूँढने हैं और उनकी लक्ष्य अवस्थाओं को समुच्चय S0 में जोड़ना है। q0 → a q1 और q0 → bq2 हैं, इसलिए समुच्चय S1 में अवस्थाएँ q1 और q2 भी होंगी:

S1={q0,q1,q2}

आगे हम समुच्चय S2 बनाते हैं। हम देखते हैं कि अवस्थाओं q0, q1, q2 से हम कहाँ-कहाँ पहुँच सकते हैं। केवल एक नई अवस्था है, q5, जिस तक हम अवस्था q1 से पहुँच सकते हैं:

S2={q0,q1,q2,q5}

आगे हम समुच्चय S3 बनाते हैं। क्या अवस्थाओं q0, q1, q2, q5 से हम किसी नई अवस्था में पहुँच सकते हैं? नहीं, इसलिए समुच्चय S3 में वही अवयव होंगे, जो S2 में हैं:

S3={q0,q1,q2,q5}

चूँकि S2 = S3 है, इसलिए S3 = S4 = S5 = … भी है। सभी Si का सम्मिलन लेने पर हमें समुच्चय S2 मिलता है, क्योंकि किसी भी आगे के समुच्चय में कोई नया अवयव नहीं जुड़ेगा।

इस प्रकार ऑटोमेटा की गम्य अवस्थाओं का समुच्चय {q0, q1, q2, q5} के बराबर है। अगम्य अवस्थाएँ हमें समुच्चयों के साधारण अंतर से मिलती हैं:

Q∖⋃i=1∞Si

हमारे ऑटोमेटा की अगम्य अवस्थाओं का समुच्चय {q3, q4} है। हम ऑटोमेटा A से सभी अगम्य अवस्थाएँ हटा देते हैं और वे सभी संक्रमण भी, जिनमें कोई अगम्य अवस्था थी। अर्थात् ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ के तुल्य, अगम्य अवस्थाओं से रहित ऑटोमेटा A′ = ⟨Q′, Σ, δ′, q0, F′⟩ को हम इस प्रकार परिभाषित करते हैं:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

स्रोत

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