सिमुलेशन (कंप्यूटर विज्ञान): Difference between revisions
(TEXT) |
(TEXT) |
||
| 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> में सभी लेबल α के लिए: | ||
:<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>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"> | |||
Meaning the union of two simulations is a simulation. | Meaning the union of two simulations is a simulation. | ||
</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> द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह | दो अवस्था <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", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त यूनियन संचालक है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[स्थिति परिवर्तन प्रणाली|अवस्था | * [[स्थिति परिवर्तन प्रणाली|अवस्था ट्रांजिशन प्रणाली]] | ||
* [[द्विसिमुलेशन]] | * [[द्विसिमुलेशन]] | ||
*[[सहसंयोजन]] | *[[सहसंयोजन]] | ||
Revision as of 21:26, 4 August 2023
सैद्धांतिक कंप्यूटर विज्ञान में सिमुलेशन अवस्था ट्रांजिशन प्रणाली से संबद्ध प्रणाली के मध्य एक संबंध (गणित) है जो उसी तरह से व्यवहार करता है जैसे एक प्रणाली दूसरे का सिमुलेशन करता है।
सहज रूप से, एक प्रणाली दूसरी प्रणाली का सिमुलेशन करता है यदि वह उसकी सभी ट्रांजिशन के समान होता है।
मूल परिभाषा एक ट्रांजिशन प्रणाली के अंतर्गत अवस्था से संबंधित है, लेकिन इसे संबंधित घटकों के असंयुक्त यूनियन से युक्त एक प्रणाली का निर्माण करके दो अलग-अलग ट्रांजिशन प्रणाली को जोड़ने के लिए आसानी से अनुकूलित किया जा सकता है।
औपचारिक परिभाषा
एक लेबल अवस्था ट्रांजिशन प्रणाली (, , →) को देखते हुए, जहां अवस्था का एक समुच्चय है, लेबलों का एक समुच्चय है और → लेबल किए गए ट्रांजिशन का एक समुच्चय है (अर्थात, का एक उपसमुच्चय), एक संबंध सिमुलेशन है यदि और केवल यदि में अवस्था की प्रत्येक जोड़ी और में सभी लेबल α के लिए:
- यदि , तो ऐसा है कि
समान रूप से, संबंधात्मक कम्पोजीशन के संदर्भ में:
में दो अवस्था और दिए जाने पर, को द्वारा सिमुलेशन किया जा सकता है, जिसे लिखा जाता है, यदि और केवल यदि कोई सिमुलेशन जैसे कि है। संबंध को सिमुलेशन पूर्व-ऑर्डर कहा जाता है, और यह सभी सिमुलेशन का यूनियन है: यथार्थतः जब कुछ सिमुलेशन के लिए है।
यूनियन के अंतर्गत सिमुलेशन का समुच्चय बंद है;[Note 1] इसलिए, सिमुलेशन पूर्व ऑर्डर स्वयं सिमुलेशन है। यह सभी सिमुलेशन का यूनियन है, यह अद्वितीय सबसे बड़ा सिमुलेशन है। रिफ्लेक्सिव और ट्रांजिटिव क्लोजर के अंतर्गत सिमुलेशन भी बंद हैं; इसलिए, सबसे बड़ा सिमुलेशन रिफ्लेक्सिव और ट्रांजिटिव होना चाहिए। इससे यह पता चलता है कि सबसे बड़ा सिमुलेशन - सिमुलेशन पूर्व-ऑर्डर - वास्तव में एक पूर्व-ऑर्डर संबंध है।[1] ध्यान दें कि एक से अधिक संबंध हो सकते हैं जो सिमुलेशन और पूर्व-ऑर्डर दोनों हैं;[Note 2] सिमुलेशन पूर्व-ऑर्डर शब्द उनमें से सबसे बड़े को संदर्भित करता है (जो अन्य सभी का अधिसमुच्चय है)।
दो अवस्था और को समान कहा जाता है, लिखा जाता है, यदि और केवल यदि को द्वारा सिमुलेशन किया जा सकता है और को द्वारा सिमुलेशन किया जा सकता है। इस प्रकार समानता सिमुलेशन पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह रिफ्लेक्सिव, सममित और ट्रांजिटिव है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक सिमुलेशन नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक सिमुलेशन नहीं है, यह पूरी तरह से द्विसमानता से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।[Note 3] प्रमाण देने के लिए, एक समानता पर विचार करें जो एक सिमुलेशन है। यह सममित है, यह एक द्विसिमुलेशन है। यह द्विसमानता का एक उपसमुच्चय होना चाहिए, जो सभी द्विसिमुलेशन का यूनियन है। यह देखना आसान है कि समानता हमेशा द्विसमानता का अधिसमुच्चय है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक सिमुलेशन है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक सिमुलेशन है (क्योंकि द्विसमानता एक सिमुलेशन है)। इसलिए, समानता एक सिमुलेशन है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है।
- ↑ Meaning the union of two simulations is a simulation.
- ↑ Consider the relations and — each is both a simulation and a preorder.
- ↑ 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", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त यूनियन संचालक है।
यह भी देखें
संदर्भ
- 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.
- 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.
- ↑ Milner, Robin (1989). संचार और समवर्ती. USA: Prentice-Hall, Inc. ISBN 0131149849.
