सिमुलेशन (कंप्यूटर विज्ञान): Difference between revisions

From Vigyanwiki
(TEXT)
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[सैद्धांतिक कंप्यूटर विज्ञान]] में '''अनुरूपण''' (सिमुलेशन) अवस्था परिवर्तन प्रणालियों से संबद्ध प्रणालियों के मध्य एक [[संबंध (गणित)]] है जो उसी तरह से व्यवहार करता है जैसे एक प्रणाली दूसरे का ''अनुरूपण'' करती है।
[[सैद्धांतिक कंप्यूटर विज्ञान]] में '''सिमुलेशन''' अवस्था ट्रांजिशन प्रणाली से संबद्ध प्रणाली के मध्य एक [[संबंध (गणित)]] है जो उसी तरह से व्यवहार करता है जैसे एक प्रणाली दूसरे का ''सिमुलेशन'' करता है।


सहज रूप से, एक प्रणाली दूसरी प्रणाली का अनुरूपण करती है यदि वह उसकी सभी परिवर्तन के समान होती है।
सहज रूप से, एक प्रणाली दूसरी प्रणाली का सिमुलेशन करता है यदि वह उसकी सभी ट्रांजिशन के समान होता है।


मूल परिभाषा एक परिवर्तन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के [[असंयुक्त संघ|असंयुक्त सम्मिलन]] से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग परिवर्तन प्रणालियों को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है।
मूल परिभाषा एक ट्रांजिशन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के [[असंयुक्त संघ|असंयुक्त यूनियन]] से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग ट्रांजिशन प्रणाली को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है।


==औपचारिक परिभाषा==
==औपचारिक परिभाषा==
एक लेबल अवस्था परिवर्तन प्रणाली (<math>S</math>, <math>\Lambda</math>, →) को देखते हुए, जहां <math>S</math> अवस्था का एक समुच्चय है, <math>\Lambda</math> लेबलों का एक समुच्चय है और → लेबल किए गए परिवर्तन का एक समुच्चय है (अर्थात, <math>S \times \Lambda \times S</math> का एक उपसमुच्चय), एक संबंध <math>R \subseteq S \times S</math> एक '''अनुरूपण''' है यदि और केवल यदि <math>R</math> में अवस्था की प्रत्येक जोड़ी <math>(p,q)</math> और <math>\Lambda</math> में सभी लेबल α के लिए:
एक लेबल अवस्था ट्रांजिशन प्रणाली (<math>S</math>, <math>\Lambda</math>, →) को देखते हुए, जहां <math>S</math> अवस्था का एक समुच्चय है, <math>\Lambda</math> लेबलों का एक समुच्चय है और → लेबल किए गए ट्रांजिशन का एक समुच्चय है (अर्थात, <math>S \times \Lambda \times S</math> का एक उपसमुच्चय), एक संबंध <math>R \subseteq S \times S</math> '''सिमुलेशन''' है यदि और केवल यदि <math>R</math> में अवस्था की प्रत्येक जोड़ी <math>(p,q)</math> और <math>\Lambda</math> में सभी लेबल α के लिए:


:<b>यदि <math>p \overset{\alpha}{\rightarrow} p'</math>, तो <math>q \overset{\alpha}{\rightarrow} q'</math> ऐसा है कि <math>(p',q') \in R</math></b>
:<b>यदि <math>p \overset{\alpha}{\rightarrow} p'</math>, तो <math>q \overset{\alpha}{\rightarrow} q'</math> ऐसा है कि <math>(p',q') \in R</math></b>


समान रूप से, [[संबंधों की संरचना|संबंधपरक संरचना]] के संदर्भ में:
समान रूप से, [[संबंधों की संरचना|संबंधात्मक कम्पोजीशन]] के संदर्भ में:
:<math>R^{-1}\,;\, \overset{\alpha}{\rightarrow}\quad {\subseteq}\quad \overset{\alpha}{\rightarrow}\,;\, R^{-1}</math>
:<math>R^{-1}\,;\, \overset{\alpha}{\rightarrow}\quad {\subseteq}\quad \overset{\alpha}{\rightarrow}\,;\, R^{-1}</math>
<math>S</math> में दो अवस्था <math>p</math> और <math>q</math> दिए जाने पर, <math>p</math> को <math>q</math> द्वारा '''अनुरूपण''' किया जा सकता है, जिसे <math>p \, \leq \, q</math> लिखा जाता है, यदि और केवल यदि कोई अनुरूपण <math>R</math> जैसे कि <math>(p, q) \in R</math> है। संबंध <math>\leq</math> को '''अनुरूपण पूर्व-ऑर्डर''' कहा जाता है, और यह सभी अनुरूपण का संघ है: <math>(p,q) \in\,\leq\,</math> यथार्थतः जब <math>(p, q) \in R</math> कुछ अनुरूपण <math>R</math> के लिए है।
<math>S</math> में दो अवस्था <math>p</math> और <math>q</math> दिए जाने पर, <math>p</math> को <math>q</math> द्वारा '''सिमुलेशन''' किया जा सकता है, जिसे <math>p \, \leq \, q</math> लिखा जाता है, यदि और केवल यदि कोई सिमुलेशन <math>R</math> जैसे कि <math>(p, q) \in R</math> है। संबंध <math>\leq</math> को '''सिमुलेशन पूर्व-ऑर्डर''' कहा जाता है, और यह सभी सिमुलेशन का यूनियन है: <math>(p,q) \in\,\leq\,</math> यथार्थतः जब <math>(p, q) \in R</math> कुछ सिमुलेशन <math>R</math> के लिए है।


संघ के अंतर्गत अनुरूपण का समुच्चय बंद है;<ref group="Note">
यूनियन के अंतर्गत सिमुलेशन का समुच्चय बंद है;<ref group="Note">
     Meaning the union of two simulations is a simulation.
     Meaning the union of two simulations is a simulation.
</ref> इसलिए, अनुरूपण [[पूर्व आदेश|पूर्व ऑर्डर]] स्वयं एक अनुरूपण है। यह सभी अनुरूपण का संघ है, यह अद्वितीय सबसे बड़ा अनुरूपण है। निजवाचक और सकर्मक संवरक के अंतर्गत अनुरूपण भी बंद हैं; इसलिए, सबसे बड़ा अनुरूपण प्रतिवर्ती और सकर्मक होना चाहिए। इससे यह पता चलता है कि सबसे बड़ा अनुरूपण - अनुरूपण पूर्व-ऑर्डर - वास्तव में एक पूर्व-ऑर्डर संबंध है।<ref>{{cite book |last=Milner |first=Robin |title=संचार और समवर्ती|year=1989 |isbn=0131149849 |publisher=Prentice-Hall, Inc. |location=USA}}</ref> ध्यान दें कि एक से अधिक संबंध हो सकते हैं जो अनुरूपण और पूर्व-ऑर्डर दोनों हैं;<ref group="Note">Consider the relations <math>\{\}</math> and <math>\{(0, 0)\}</math> — each is both a simulation and a preorder.</ref> अनुरूपण पूर्व-ऑर्डर शब्द उनमें से सबसे बड़े को संदर्भित करता है (जो अन्य सभी का अधिसमुच्चय है)।
</ref> इसलिए, सिमुलेशन [[पूर्व आदेश|पूर्व ऑर्डर]] स्वयं सिमुलेशन है। यह सभी सिमुलेशन का यूनियन है, यह अद्वितीय सबसे बड़ा सिमुलेशन है। रिफ्लेक्सिव और ट्रांजिटिव क्लोजर के अंतर्गत सिमुलेशन भी बंद हैं; इसलिए, सबसे बड़ा सिमुलेशन रिफ्लेक्सिव और ट्रांजिटिव होना चाहिए। इससे यह पता चलता है कि सबसे बड़ा सिमुलेशन - सिमुलेशन पूर्व-ऑर्डर - वास्तव में एक पूर्व-ऑर्डर संबंध है।<ref>{{cite book |last=Milner |first=Robin |title=संचार और समवर्ती|year=1989 |isbn=0131149849 |publisher=Prentice-Hall, Inc. |location=USA}}</ref> ध्यान दें कि एक से अधिक संबंध हो सकते हैं जो सिमुलेशन और पूर्व-ऑर्डर दोनों हैं;<ref group="Note">Consider the relations <math>\{\}</math> and <math>\{(0, 0)\}</math> — each is both a simulation and a preorder.</ref> सिमुलेशन पूर्व-ऑर्डर शब्द उनमें से सबसे बड़े को संदर्भित करता है (जो अन्य सभी का अधिसमुच्चय है)।


दो अवस्था <math>p</math> और <math>q</math> को '''समान''' कहा जाता है, <math>p \leq\geq q</math> लिखा जाता है, यदि और केवल यदि <math>p</math> को <math>q</math> द्वारा अनुरूपण किया जा सकता है और <math>q</math> को <math>p</math> द्वारा अनुरूपण किया जा सकता है। इस प्रकार समानता अनुरूपण पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह प्रतिवर्ती, सममित और सकर्मक है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक अनुरूपण नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक अनुरूपण नहीं है, यह पूरी तरह से [[द्विसमानता]] से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।<ref group="Note">For an example, see '''Fig. 1''' in {{cite journal
दो अवस्था <math>p</math> और <math>q</math> को '''समान''' कहा जाता है, <math>p \leq\geq q</math> लिखा जाता है, यदि और केवल यदि <math>p</math> को <math>q</math> द्वारा सिमुलेशन किया जा सकता है और <math>q</math> को <math>p</math> द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह रिफ्लेक्सिव, सममित और ट्रांजिटिव है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक सिमुलेशन नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक सिमुलेशन नहीं है, यह पूरी तरह से [[द्विसमानता]] से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।<ref group="Note">For an example, see '''Fig. 1''' in {{cite journal
|last1 = Champarnaud
|last1 = Champarnaud
|first1 = J.-M
|first1 = J.-M
Line 32: Line 32:
|doi = 10.1016/j.tcs.2004.02.048
|doi = 10.1016/j.tcs.2004.02.048
|doi-access = free
|doi-access = free
}}</ref> प्रमाण देने के लिए, एक समानता पर विचार करें जो एक अनुरूपण है। यह सममित है, यह एक ''द्विअनुरूपण'' है। यह द्विसमानता का एक ''उपसमुच्चय'' होना चाहिए, जो सभी द्विअनुरूपण का संघ है। यह देखना आसान है कि समानता हमेशा द्विसमानता का ''अधिसमुच्चय'' है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक अनुरूपण है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक अनुरूपण है (क्योंकि द्विसमानता एक अनुरूपण है)। इसलिए, समानता एक अनुरूपण है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है।
}}</ref> प्रमाण देने के लिए, एक समानता पर विचार करें जो एक सिमुलेशन है। यह सममित है, यह एक ''द्विसिमुलेशन'' है। यह द्विसमानता का एक ''उपसमुच्चय'' होना चाहिए, जो सभी द्विसिमुलेशन का यूनियन है। यह देखना आसान है कि समानता हमेशा द्विसमानता का ''अधिसमुच्चय'' है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक सिमुलेशन है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक सिमुलेशन है (क्योंकि द्विसमानता एक सिमुलेशन है)। इसलिए, समानता एक सिमुलेशन है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है।


------
------
{{reflist|group=Note}}
{{reflist|group=Note}}


==अलग-अलग परिवर्तन प्रणालियों की समानता==
==अलग-अलग ट्रांजिशन प्रणाली की समानता==
दो अलग-अलग परिवर्तन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, अनुरूपण और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त सम्मिलन संचालक है।
दो अलग-अलग ट्रांजिशन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, सिमुलेशन और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त यूनियन संचालक है।


==यह भी देखें==
==यह भी देखें==
* [[स्थिति परिवर्तन प्रणाली|अवस्था परिवर्तन प्रणाली]]
* [[स्थिति परिवर्तन प्रणाली|अवस्था ट्रांजिशन प्रणाली]]
* [[द्विसिमुलेशन|द्विअनुरूपण]]
* [[द्विसिमुलेशन]]
*[[सहसंयोजन]]
*[[सहसंयोजन]]
* [[संक्रियात्मक शब्दार्थ]]
* [[संक्रियात्मक शब्दार्थ]]
Line 74: Line 74:
}}
}}


{{DEFAULTSORT:Simulation Preorder}}[[Category: सैद्धांतिक कंप्यूटर विज्ञान]] [[Category: संक्रमण प्रणालियाँ]]
{{DEFAULTSORT:Simulation Preorder}}


 
[[Category:Created On 24/07/2023|Simulation Preorder]]
 
[[Category:Machine Translated Page|Simulation Preorder]]
[[Category: Machine Translated Page]]
[[Category:Pages with script errors|Simulation Preorder]]
[[Category:Created On 24/07/2023]]
[[Category:Templates Vigyan Ready|Simulation Preorder]]
[[Category:संक्रमण प्रणालियाँ|Simulation Preorder]]
[[Category:सैद्धांतिक कंप्यूटर विज्ञान|Simulation Preorder]]

Latest revision as of 14:44, 11 August 2023

सैद्धांतिक कंप्यूटर विज्ञान में सिमुलेशन अवस्था ट्रांजिशन प्रणाली से संबद्ध प्रणाली के मध्य एक संबंध (गणित) है जो उसी तरह से व्यवहार करता है जैसे एक प्रणाली दूसरे का सिमुलेशन करता है।

सहज रूप से, एक प्रणाली दूसरी प्रणाली का सिमुलेशन करता है यदि वह उसकी सभी ट्रांजिशन के समान होता है।

मूल परिभाषा एक ट्रांजिशन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के असंयुक्त यूनियन से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग ट्रांजिशन प्रणाली को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है।

औपचारिक परिभाषा

एक लेबल अवस्था ट्रांजिशन प्रणाली (, , →) को देखते हुए, जहां अवस्था का एक समुच्चय है, लेबलों का एक समुच्चय है और → लेबल किए गए ट्रांजिशन का एक समुच्चय है (अर्थात, का एक उपसमुच्चय), एक संबंध सिमुलेशन है यदि और केवल यदि में अवस्था की प्रत्येक जोड़ी और में सभी लेबल α के लिए:

यदि , तो ऐसा है कि

समान रूप से, संबंधात्मक कम्पोजीशन के संदर्भ में:

में दो अवस्था और दिए जाने पर, को द्वारा सिमुलेशन किया जा सकता है, जिसे लिखा जाता है, यदि और केवल यदि कोई सिमुलेशन जैसे कि है। संबंध को सिमुलेशन पूर्व-ऑर्डर कहा जाता है, और यह सभी सिमुलेशन का यूनियन है: यथार्थतः जब कुछ सिमुलेशन के लिए है।

यूनियन के अंतर्गत सिमुलेशन का समुच्चय बंद है;[Note 1] इसलिए, सिमुलेशन पूर्व ऑर्डर स्वयं सिमुलेशन है। यह सभी सिमुलेशन का यूनियन है, यह अद्वितीय सबसे बड़ा सिमुलेशन है। रिफ्लेक्सिव और ट्रांजिटिव क्लोजर के अंतर्गत सिमुलेशन भी बंद हैं; इसलिए, सबसे बड़ा सिमुलेशन रिफ्लेक्सिव और ट्रांजिटिव होना चाहिए। इससे यह पता चलता है कि सबसे बड़ा सिमुलेशन - सिमुलेशन पूर्व-ऑर्डर - वास्तव में एक पूर्व-ऑर्डर संबंध है।[1] ध्यान दें कि एक से अधिक संबंध हो सकते हैं जो सिमुलेशन और पूर्व-ऑर्डर दोनों हैं;[Note 2] सिमुलेशन पूर्व-ऑर्डर शब्द उनमें से सबसे बड़े को संदर्भित करता है (जो अन्य सभी का अधिसमुच्चय है)।

दो अवस्था और को समान कहा जाता है, लिखा जाता है, यदि और केवल यदि को द्वारा सिमुलेशन किया जा सकता है और को द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह रिफ्लेक्सिव, सममित और ट्रांजिटिव है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक सिमुलेशन नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक सिमुलेशन नहीं है, यह पूरी तरह से द्विसमानता से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।[Note 3] प्रमाण देने के लिए, एक समानता पर विचार करें जो एक सिमुलेशन है। यह सममित है, यह एक द्विसिमुलेशन है। यह द्विसमानता का एक उपसमुच्चय होना चाहिए, जो सभी द्विसिमुलेशन का यूनियन है। यह देखना आसान है कि समानता हमेशा द्विसमानता का अधिसमुच्चय है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक सिमुलेशन है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक सिमुलेशन है (क्योंकि द्विसमानता एक सिमुलेशन है)। इसलिए, समानता एक सिमुलेशन है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है।


  1. Meaning the union of two simulations is a simulation.
  2. Consider the relations and — each is both a simulation and a preorder.
  3. For an example, see Fig. 1 in Champarnaud, J.-M; Coulon, F. (2004). "NFA reduction algorithms by means of regular inequalities". Theoretical Computer Science. 327 (3): 241–253. doi:10.1016/j.tcs.2004.02.048. ISSN 0304-3975.

अलग-अलग ट्रांजिशन प्रणाली की समानता

दो अलग-अलग ट्रांजिशन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, सिमुलेशन और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त यूनियन संचालक है।

यह भी देखें

संदर्भ

  1. Park, David (1981). "Concurrency and Automata on Infinite Sequences" (PDF). In Deussen, Peter (ed.). Proceedings of the 5th GI-Conference, Karlsruhe. Lecture Notes in Computer Science. Vol. 104. Springer-Verlag. pp. 167–183. doi:10.1007/BFb0017309. ISBN 978-3-540-10576-3.
  2. van Glabbeek, R. J. (2001). "The Linear Time – Branching Time Spectrum I: The Semantics of Concrete, Sequential Processes". Handbook of Process Algebra. Elsevier. pp. 3–99.
  1. Milner, Robin (1989). संचार और समवर्ती. USA: Prentice-Hall, Inc. ISBN 0131149849.