सिमुलेशन (कंप्यूटर विज्ञान): 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> | ||
| Line 12: | Line 12: | ||
समान रूप से, [[संबंधों की संरचना|संबंधपरक संरचना]] के संदर्भ में: | समान रूप से, [[संबंधों की संरचना|संबंधपरक संरचना]] के संदर्भ में: | ||
:<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>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> द्वारा अनुरूपण किया जा सकता है। इस प्रकार समानता अनुरूपण पूर्व-ऑर्डर का अधिकतम सममित उपसमुच्चय है, जिसका अर्थ है कि यह प्रतिवर्ती, सममित और सकर्मक है; इसलिए एक तुल्यता संबंध है। हालाँकि, यह आवश्यक रूप से एक अनुरूपण नहीं है, और यथार्थतः उन प्रकरणों में जब यह एक अनुरूपण नहीं है, यह पूरी तरह से [[द्विसमानता]] से अधिक स्थूल है (अर्थात् यह द्विसमानता का एक अधिसमुच्चय है)।<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> प्रमाण देने के लिए, एक समानता पर विचार करें जो एक अनुरूपण है। यह सममित है, यह एक ''द्विअनुरूपण'' है। यह द्विसमानता का एक ''उपसमुच्चय'' होना चाहिए, जो सभी द्विअनुरूपण का संघ है। यह देखना आसान है कि समानता हमेशा द्विसमानता का ''अधिसमुच्चय'' है। इससे यह निष्कर्ष निकलता है कि यदि समानता एक अनुरूपण है, तो यह द्विसमानता के समान है। यह द्विसमानता के समान है, तो यह स्वाभाविक रूप से एक अनुरूपण है (क्योंकि द्विसमानता एक अनुरूपण है)। इसलिए, समानता एक अनुरूपण है यदि और केवल यदि यह द्विसमानता के समान है। यदि ऐसा नहीं होता है, तो यह इसका यथार्थ रूप से अधिसमुच्चय होना चाहिए; इसलिए यथार्थ रूप से स्थूल तुल्यता संबंध है। | ||
------ | ------ | ||
| Line 38: | Line 38: | ||
==अलग-अलग परिवर्तन प्रणालियों की समानता== | ==अलग-अलग परिवर्तन प्रणालियों की समानता== | ||
दो अलग-अलग परिवर्तन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, | दो अलग-अलग परिवर्तन प्रणाली (S', Λ', →') और (S", Λ", →") की तुलना करते समय, अनुरूपण और समानता की मूल धारणाओं का उपयोग दो मशीनों की असंयुक्त संरचना बनाकर किया जा सकता है, (S, Λ, →) S = S' ∐ S", Λ = Λ' ∪ Λ" और → = →' ∪ →" के साथ, जहां ∐ समुच्चयो के मध्य असंयुक्त सम्मिलन संचालक है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[स्थिति परिवर्तन प्रणाली]] | * [[स्थिति परिवर्तन प्रणाली|अवस्था परिवर्तन प्रणाली]] | ||
* [[द्विसिमुलेशन| | * [[द्विसिमुलेशन|द्विअनुरूपण]] | ||
*[[सहसंयोजन]] | *[[सहसंयोजन]] | ||
* [[संक्रियात्मक शब्दार्थ]] | * [[संक्रियात्मक शब्दार्थ]] | ||
Revision as of 10:52, 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.
