संभाव्य ऑटोमेटन: Difference between revisions

Revision as of 00:18, 5 June 2023

गणित और कंप्यूटर विज्ञान में, संभाव्य automaton (PA) गैर-नियतात्मक परिमित automaton का सामान्यीकरण है; इसमें परिमित राज्य मशीन में दिए गए संक्रमण की संभावना शामिल है, इसे स्टोकेस्टिक मैट्रिक्स में बदलना।^[1]^[2]इस प्रकार, संभाव्य automaton भी मार्कोव श्रृंखला की अवधारणाओं और परिमित प्रकार के सबशिफ्ट का सामान्यीकरण करता है। संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त औपचारिक भाषा को स्टोकेस्टिक भाषा कहा जाता है; इनमें उपसमुच्चय के रूप में नियमित भाषाएं शामिल हैं। स्टोकेस्टिक भाषाओं की संख्या बेशुमार है।

1963 में माइकल ओ राबिन द्वारा अवधारणा पेश की गई थी;^[2] निश्चित विशेष मामले को कभी-कभी राबिन ऑटोमेटन के रूप में जाना जाता है (ω-automaton#स्वीकृति की शर्तों के उपवर्ग के साथ भ्रमित नहीं होना चाहिए। ω-automata को राबिन ऑटोमेटा भी कहा जाता है)। हाल के वर्षों में, क्वांटम संभावनाओं, क्वांटम परिमित automaton के संदर्भ में संस्करण तैयार किया गया है।

अनौपचारिक विवरण

किसी दिए गए प्रारंभिक राज्य और इनपुट चरित्र के लिए, नियतात्मक परिमित automaton (DFA) में ठीक अगला राज्य होता है, और nondeterministic परिमित automaton (NFA) में अगले राज्यों का सेट होता है। इसके बजाय संभाव्य automaton (PA) में अगले राज्यों का भारित सेट (या पंक्ति और स्तंभ वैक्टर) होता है, जहाँ वज़न 1 होना चाहिए और इसलिए इसे संभावनाओं के रूप में व्याख्या किया जा सकता है (इसे स्टोकेस्टिक वेक्टर बनाते हुए)। इन भारों के परिचय को प्रतिबिंबित करने के लिए धारणाएं बताती हैं और स्वीकृति को भी संशोधित किया जाना चाहिए। दिए गए कदम के रूप में मशीन की स्थिति को अब राज्यों के स्टोचैस्टिक वेक्टर द्वारा भी दर्शाया जाना चाहिए, और राज्य को स्वीकार किया जाता है यदि इसकी स्वीकृति स्थिति में होने की कुल संभावना कुछ कट-ऑफ से अधिक हो जाती है।

पीए कुछ अर्थों में नियतात्मक से गैर-नियतात्मक तक आधा-अधूरा कदम है, क्योंकि यह अगले राज्यों के सेट की अनुमति देता है लेकिन उनके वजन पर प्रतिबंध के साथ। हालांकि, यह कुछ हद तक भ्रामक है, क्योंकि पीए वजन को परिभाषित करने के लिए वास्तविक संख्या की धारणा का उपयोग करता है, जो डीएफए और एनएफए दोनों की परिभाषा में अनुपस्थित है। यह अतिरिक्त स्वतंत्रता उन्हें उन भाषाओं को तय करने में सक्षम बनाती है जो नियमित नहीं हैं, जैसे कि अपरिमेय मापदंडों वाली पी-एडिक भाषाएँ। जैसे, पीए डीएफए और एनएफए दोनों (जो समान रूप से प्रसिद्ध हैं) की तुलना में अधिक शक्तिशाली हैं।

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

संभाव्य automaton को nondeterministic परिमित automaton के विस्तार के रूप में परिभाषित किया जा सकता है $(Q,\Sigma ,\delta ,q_{0},F)$ , दो संभावनाओं के साथ: संभावना $P$ विशेष राज्य संक्रमण हो रहा है, और प्रारंभिक अवस्था के साथ $q_{0}$ दिए गए प्रारंभिक अवस्था में ऑटोमेटन की संभावना देने वाले स्टोचैस्टिक वेक्टर द्वारा प्रतिस्थापित किया गया।

साधारण गैर-नियतात्मक परिमित automaton के लिए, किसी के पास है

राज्यों का परिमित सेट (गणित)। $Q$
इनपुट प्रतीकों का परिमित सेट $\Sigma$
संक्रमण समारोह $\delta :Q\times \Sigma \to \wp (Q)$
राज्यों का समूह $F$ स्वीकृत (या अंतिम) राज्यों के रूप में प्रतिष्ठित $F\subseteq Q$ .

यहाँ, $\wp (Q)$ के सत्ता स्थापित को दर्शाता है $Q$ .

करींग के उपयोग से, संक्रमण समारोह $\delta :Q\times \Sigma \to \wp (Q)$ गैर-नियतात्मक परिमित automaton को सदस्यता समारोह के रूप में लिखा जा सकता है

\delta :Q\times \Sigma \times Q\to \{0,1\}

ताकि $\delta (q,a,q^{\prime })=1$ अगर $q^{\prime }\in \delta (q,a)$ और $0$ अन्यथा। करी ट्रांज़िशन फ़ंक्शन को मैट्रिक्स प्रविष्टियों के साथ मैट्रिक्स के रूप में समझा जा सकता है

\left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })

गणित का सवाल $\theta _{a}$ तब वर्ग मैट्रिक्स है, जिसकी प्रविष्टियाँ शून्य या एक हैं, यह दर्शाता है कि संक्रमण है या नहीं $q{\stackrel {a}{\rightarrow }}q^{\prime }$ एनएफए द्वारा अनुमति दी जाती है। इस तरह के संक्रमण मैट्रिक्स को हमेशा गैर-नियतात्मक परिमित automaton के लिए परिभाषित किया जाता है।

संभाव्य automaton इन matrices को स्टोकास्टिक मैट्रिक्स के परिवार द्वारा प्रतिस्थापित करता है $P_{a}$ , वर्णमाला में प्रत्येक प्रतीक a के लिए $\Sigma$ ताकि संक्रमण की संभावना द्वारा दिया जाता है

\left[P_{a}\right]_{qq^{\prime }}

किसी राज्य से किसी भी राज्य में राज्य परिवर्तन निश्चित रूप से प्रायिकता के साथ होना चाहिए, और इसलिए किसी के पास होना चाहिए

\sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1

सभी इनपुट पत्रों के लिए $a$ और आंतरिक राज्य $q$ . संभाव्य automaton की प्रारंभिक स्थिति पंक्ति वेक्टर द्वारा दी गई है $v$ , जिनके घटक व्यक्तिगत प्रारंभिक अवस्थाओं की संभावनाएँ हैं $q$ , जो 1 में जोड़ें:

\sum _{q}\left[v\right]_{q}=1

संक्रमण मैट्रिक्स दाईं ओर कार्य करता है, ताकि इनपुट स्ट्रिंग का उपभोग करने के बाद, संभाव्य automaton की स्थिति $abc$ , होगा

vP_{a}P_{b}P_{c}

विशेष रूप से, संभाव्य automaton की स्थिति हमेशा स्टोकास्टिक वेक्टर होती है, क्योंकि किसी भी दो स्टोकास्टिक मैट्रिक्स का उत्पाद स्टोकास्टिक मैट्रिक्स होता है, और स्टोकास्टिक वेक्टर और स्टोकास्टिक मैट्रिक्स का उत्पाद फिर से स्टोकास्टिक वेक्टर होता है। इस सदिश को कभी-कभी राज्यों का वितरण कहा जाता है, यह बल देते हुए कि यह असतत संभाव्यता वितरण है।

औपचारिक रूप से, संभाव्य ऑटोमेटन की परिभाषा के लिए गैर-नियतात्मक ऑटोमेटन के यांत्रिकी की आवश्यकता नहीं होती है, जिसके साथ विवाद हो सकता है। औपचारिक रूप से, संभाव्य automaton PA को tuple के रूप में परिभाषित किया गया है $(Q,\Sigma ,P,v,F)$ . राबिन automaton वह है जिसके लिए प्रारंभिक वितरण होता है $v$ समन्वय वेक्टर है; अर्थात्, प्रविष्टि को छोड़कर सभी के लिए शून्य है, और शेष प्रविष्टि है।

स्टोकेस्टिक भाषाएँ

संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त औपचारिक भाषा के सेट को स्टोकेस्टिक भाषा कहा जाता है। वे उपसमुच्चय के रूप में नियमित भाषाओं को शामिल करते हैं।

होने देना $F=Q_{\text{accept}}\subseteq Q$ ऑटोमेटन की स्वीकृति या अंतिम अवस्थाओं का सेट हो। अंकन के दुरुपयोग से, $Q_{\text{accept}}$ कॉलम वेक्टर के रूप में भी समझा जा सकता है जो कि सदस्यता कार्य है $Q_{\text{accept}}$ ; अर्थात्, इसमें तत्वों के संगत स्थानों पर 1 है $Q_{\text{accept}}$ , और एक शून्य अन्यथा। इस वेक्टर को स्केलर (गणित) बनाने के लिए आंतरिक स्थिति संभावना के साथ अनुबंधित किया जा सकता है। विशिष्ट automaton द्वारा मान्यता प्राप्त भाषा को तब परिभाषित किया जाता है

L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}

कहाँ $\Sigma ^{*}$ वर्णमाला (कंप्यूटर विज्ञान) में सभी स्ट्रिंग (कंप्यूटर विज्ञान) का सेट है $\Sigma$ (ताकि * क्लेन स्टार हो)। भाषा कट-पॉइंट के मान पर निर्भर करती है $\eta$ , आमतौर पर सीमा में होने के लिए लिया जाता है $0\leq \eta <1$ .

भाषा को η कहा जाता है - स्टोचैस्टिक अगर और केवल अगर वहाँ कुछ पीए मौजूद है जो निश्चित रूप से भाषा को पहचानता है $\eta$ . भाषा को स्टोकेस्टिक कहा जाता है अगर और केवल अगर कुछ है $0\leq \eta <1$ जिसके लिए $L_{\eta }$ η-स्टोकेस्टिक है।

कट-प्वाइंट को 'पृथक कट-पॉइंट' कहा जाता है अगर और केवल अगर मौजूद हो $\delta >0$ ऐसा है कि

\vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta

सभी के लिए $s\in \Sigma ^{*}$

गुण

हर नियमित भाषा स्टोचैस्टिक है, और अधिक दृढ़ता से, हर नियमित भाषा η-स्टोकेस्टिक है। कमजोर आक्षेप यह है कि प्रत्येक 0-स्टोकेस्टिक भाषा नियमित है; हालाँकि, सामान्य बातचीत पकड़ में नहीं आती है: ऐसी स्टोकेस्टिक भाषाएँ हैं जो नियमित नहीं हैं।

प्रत्येक η-स्टोकेस्टिक भाषा कुछ के लिए स्टोकेस्टिक है $0<\eta <1$ .

प्रत्येक स्टोकेस्टिक भाषा को राबिन ऑटोमेटन द्वारा प्रदर्शित किया जा सकता है।

अगर $\eta$ पृथक कट-पॉइंट है, फिर $L_{\eta }$ नियमित भाषा है।

p-adic भाषाएँ

पी-एडिक | पी-एडिक भाषाएं स्टोकास्टिक भाषा का उदाहरण प्रदान करती हैं जो नियमित नहीं है, और यह भी दिखाती है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। पी-एडिक भाषा को स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है

L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ and }}0.n_{1}n_{2}n_{3}\ldots >\eta \}

पत्रों में $0,1,2,\ldots ,(p-1)$ .

अर्थात्, p-adic भाषा केवल [0, 1] में वास्तविक संख्याओं का समुच्चय है, जिसे आधार-p में लिखा गया है, जैसे कि वे इससे अधिक हैं $\eta$ . यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ स्टोकेस्टिक हैं।^[3] विशेष रूप से, इसका तात्पर्य है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। पी-एडिक भाषा नियमित है अगर और केवल अगर $\eta$ तर्कसंगत है।

सामान्यीकरण

संभाव्य automaton की ज्यामितीय व्याख्या है: राज्य वेक्टर को बिंदु के रूप में समझा जा सकता है जो ऑर्थोगोनल कोने के विपरीत मानक संकेतन के चेहरे पर रहता है। ट्रांज़िशन मेट्रिसेस बिंदु पर अभिनय करते हुए मोनोइड बनाते हैं। यह बिंदु कुछ सामान्य टोपोलॉजिकल स्पेस से होने के कारण सामान्यीकृत हो सकता है, जबकि ट्रांज़िशन मेट्रिसेस को टोपोलॉजिकल स्पेस पर काम करने वाले ऑपरेटरों के संग्रह से चुना जाता है, इस प्रकार सेमीऑटोमेटन का निर्माण होता है। जब कट-पॉइंट को उपयुक्त रूप से सामान्यीकृत किया जाता है, तो टोपोलॉजिकल ऑटोमेटन होता है।

ऐसे सामान्यीकरण का उदाहरण क्वांटम परिमित ऑटोमेटन है; यहां, ऑटोमेटन राज्य को जटिल प्रक्षेप्य स्थान में बिंदु द्वारा दर्शाया गया है, जबकि संक्रमण मेट्रिसेस एकात्मक समूह से चुना गया निश्चित सेट है। कट-प्वाइंट को क्वांटम कोण के अधिकतम मान की सीमा के रूप में समझा जाता है।

↑ Paz, Azaria (2014). संभाव्य ऑटोमेटा का परिचय।. ISBN 9781483244655. OCLC 1027002902.
↑ ^2.0 ^2.1 Michael O. Rabin (1963). "संभाव्य ऑटोमेटा". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0.
↑ Merve Nur Cakir; Saleemi, Mehwish; Zimmermann, Karl-Heinz (2021). "स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर". arXiv:2103.14423 [cs.FL].

संदर्भ

Salomaa, Arto (1969). "Finite nondeterministic and probabilistic automata". Theory of Automata. Oxford: Pergamon Press.

[1] Paz, Azaria (2014). संभाव्य ऑटोमेटा का परिचय।. ISBN 9781483244655. OCLC 1027002902.

[:0-2] 2.0 ^2.1 Michael O. Rabin (1963). "संभाव्य ऑटोमेटा". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0.

[3] Merve Nur Cakir; Saleemi, Mehwish; Zimmermann, Karl-Heinz (2021). "स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर". arXiv:2103.14423 [cs.FL].

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-{{technical|date=January 2021}}
+गणित और [[कंप्यूटर विज्ञान]] में, संभाव्य automaton (PA) गैर-नियतात्मक परिमित automaton का सामान्यीकरण है; इसमें परिमित राज्य मशीन में दिए गए संक्रमण की संभावना शामिल है, इसे [[स्टोकेस्टिक मैट्रिक्स]] में बदलना।<ref>{{Cite book |last=Paz |first=Azaria |url=https://www.worldcat.org/oclc/1027002902 |title=संभाव्य ऑटोमेटा का परिचय।|date=2014 |others= |isbn=9781483244655 |oclc=1027002902}}</ref><ref name=":0" />इस प्रकार, संभाव्य automaton भी [[मार्कोव श्रृंखला]] की अवधारणाओं और परिमित प्रकार के सबशिफ्ट का सामान्यीकरण करता है। संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त [[औपचारिक भाषा]] को स्टोकेस्टिक भाषा कहा जाता है; इनमें उपसमुच्चय के रूप में [[नियमित भाषा]]एं शामिल हैं। स्टोकेस्टिक भाषाओं की संख्या [[बेशुमार]] है।
-गणित और [[कंप्यूटर विज्ञान]] में, संभाव्य automaton (PA) गैर-नियतात्मक परिमित automaton का एक सामान्यीकरण है; इसमें परिमित राज्य मशीन में दिए गए संक्रमण की संभावना शामिल है, इसे [[स्टोकेस्टिक मैट्रिक्स]] में बदलना।<ref>{{Cite book |last=Paz |first=Azaria |url=https://www.worldcat.org/oclc/1027002902 |title=संभाव्य ऑटोमेटा का परिचय।|date=2014 |others= |isbn=9781483244655 |oclc=1027002902}}</ref><ref name=":0" />इस प्रकार, संभाव्य automaton भी एक [[मार्कोव श्रृंखला]] की अवधारणाओं और परिमित प्रकार के एक सबशिफ्ट का सामान्यीकरण करता है। संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त [[औपचारिक भाषा]] को स्टोकेस्टिक भाषा कहा जाता है; इनमें उपसमुच्चय के रूप में [[नियमित भाषा]]एं शामिल हैं। स्टोकेस्टिक भाषाओं की संख्या [[बेशुमार]] है।
-में माइकल ओ राबिन द्वारा अवधारणा पेश की गई थी;<ref name=":0">{{cite journal |last=Michael O. Rabin |author-link=Michael O. Rabin |date=1963 |title=संभाव्य ऑटोमेटा|journal=Information and Control |volume=6 |issue=3 |pages=230–245 |doi= 10.1016/s0019-9958(63)90290-0|doi-access=free }}</ref> एक निश्चित विशेष मामले को कभी-कभी राबिन ऑटोमेटन के रूप में जाना जाता है (ω-automaton#स्वीकृति की शर्तों के उपवर्ग के साथ भ्रमित नहीं होना चाहिए। ω-automata को राबिन ऑटोमेटा भी कहा जाता है)। हाल के वर्षों में, क्वांटम संभावनाओं, क्वांटम परिमित automaton के संदर्भ में एक संस्करण तैयार किया गया है।
+में माइकल ओ राबिन द्वारा अवधारणा पेश की गई थी;<ref name=":0">{{cite journal |last=Michael O. Rabin |author-link=Michael O. Rabin |date=1963 |title=संभाव्य ऑटोमेटा|journal=Information and Control |volume=6 |issue=3 |pages=230–245 |doi= 10.1016/s0019-9958(63)90290-0|doi-access=free }}</ref> निश्चित विशेष मामले को कभी-कभी राबिन ऑटोमेटन के रूप में जाना जाता है (ω-automaton#स्वीकृति की शर्तों के उपवर्ग के साथ भ्रमित नहीं होना चाहिए। ω-automata को राबिन ऑटोमेटा भी कहा जाता है)। हाल के वर्षों में, क्वांटम संभावनाओं, क्वांटम परिमित automaton के संदर्भ में संस्करण तैयार किया गया है।
 == अनौपचारिक विवरण ==
-किसी दिए गए प्रारंभिक राज्य और इनपुट चरित्र के लिए, एक [[नियतात्मक परिमित automaton]] (DFA) में ठीक एक अगला राज्य होता है, और एक nondeterministic परिमित automaton (NFA) में अगले राज्यों का एक सेट होता है। इसके बजाय एक संभाव्य automaton (PA) में अगले राज्यों का एक भारित सेट (या [[पंक्ति और स्तंभ वैक्टर]]) होता है, जहाँ वज़न 1 होना चाहिए और इसलिए इसे संभावनाओं के रूप में व्याख्या किया जा सकता है (इसे एक [[स्टोकेस्टिक वेक्टर]] बनाते हुए)। इन भारों के परिचय को प्रतिबिंबित करने के लिए धारणाएं बताती हैं और स्वीकृति को भी संशोधित किया जाना चाहिए। दिए गए कदम के रूप में मशीन की स्थिति को अब राज्यों के एक स्टोचैस्टिक वेक्टर द्वारा भी दर्शाया जाना चाहिए, और एक राज्य को स्वीकार किया जाता है यदि इसकी स्वीकृति स्थिति में होने की कुल संभावना कुछ कट-ऑफ से अधिक हो जाती है।
+किसी दिए गए प्रारंभिक राज्य और इनपुट चरित्र के लिए, [[नियतात्मक परिमित automaton]] (DFA) में ठीक अगला राज्य होता है, और nondeterministic परिमित automaton (NFA) में अगले राज्यों का सेट होता है। इसके बजाय संभाव्य automaton (PA) में अगले राज्यों का भारित सेट (या [[पंक्ति और स्तंभ वैक्टर]]) होता है, जहाँ वज़न 1 होना चाहिए और इसलिए इसे संभावनाओं के रूप में व्याख्या किया जा सकता है (इसे [[स्टोकेस्टिक वेक्टर]] बनाते हुए)। इन भारों के परिचय को प्रतिबिंबित करने के लिए धारणाएं बताती हैं और स्वीकृति को भी संशोधित किया जाना चाहिए। दिए गए कदम के रूप में मशीन की स्थिति को अब राज्यों के स्टोचैस्टिक वेक्टर द्वारा भी दर्शाया जाना चाहिए, और राज्य को स्वीकार किया जाता है यदि इसकी स्वीकृति स्थिति में होने की कुल संभावना कुछ कट-ऑफ से अधिक हो जाती है।
-एक पीए कुछ अर्थों में नियतात्मक से गैर-नियतात्मक तक एक आधा-अधूरा कदम है, क्योंकि यह अगले राज्यों के एक सेट की अनुमति देता है लेकिन उनके वजन पर प्रतिबंध के साथ। हालांकि, यह कुछ हद तक भ्रामक है, क्योंकि पीए वजन को परिभाषित करने के लिए वास्तविक संख्या की धारणा का उपयोग करता है, जो डीएफए और एनएफए दोनों की परिभाषा में अनुपस्थित है। यह अतिरिक्त स्वतंत्रता उन्हें उन भाषाओं को तय करने में सक्षम बनाती है जो नियमित नहीं हैं, जैसे कि अपरिमेय मापदंडों वाली पी-एडिक भाषाएँ। जैसे, पीए डीएफए और एनएफए दोनों (जो समान रूप से प्रसिद्ध हैं) की तुलना में अधिक शक्तिशाली हैं।
+पीए कुछ अर्थों में नियतात्मक से गैर-नियतात्मक तक आधा-अधूरा कदम है, क्योंकि यह अगले राज्यों के सेट की अनुमति देता है लेकिन उनके वजन पर प्रतिबंध के साथ। हालांकि, यह कुछ हद तक भ्रामक है, क्योंकि पीए वजन को परिभाषित करने के लिए वास्तविक संख्या की धारणा का उपयोग करता है, जो डीएफए और एनएफए दोनों की परिभाषा में अनुपस्थित है। यह अतिरिक्त स्वतंत्रता उन्हें उन भाषाओं को तय करने में सक्षम बनाती है जो नियमित नहीं हैं, जैसे कि अपरिमेय मापदंडों वाली पी-एडिक भाषाएँ। जैसे, पीए डीएफए और एनएफए दोनों (जो समान रूप से प्रसिद्ध हैं) की तुलना में अधिक शक्तिशाली हैं।
 == औपचारिक परिभाषा ==
-संभाव्य automaton को एक nondeterministic परिमित automaton के विस्तार के रूप में परिभाषित किया जा सकता है <math>(Q,\Sigma,\delta,q_0,F)</math>, दो संभावनाओं के साथ: संभावना <math>P</math> एक विशेष राज्य संक्रमण हो रहा है, और प्रारंभिक अवस्था के साथ <math>q_0</math> एक दिए गए प्रारंभिक अवस्था में ऑटोमेटन की संभावना देने वाले स्टोचैस्टिक वेक्टर द्वारा प्रतिस्थापित किया गया।
+संभाव्य automaton को nondeterministic परिमित automaton के विस्तार के रूप में परिभाषित किया जा सकता है <math>(Q,\Sigma,\delta,q_0,F)</math>, दो संभावनाओं के साथ: संभावना <math>P</math> विशेष राज्य संक्रमण हो रहा है, और प्रारंभिक अवस्था के साथ <math>q_0</math> दिए गए प्रारंभिक अवस्था में ऑटोमेटन की संभावना देने वाले स्टोचैस्टिक वेक्टर द्वारा प्रतिस्थापित किया गया।
 साधारण गैर-नियतात्मक परिमित automaton के लिए, किसी के पास है
-* राज्यों का एक परिमित [[सेट (गणित)]]। <math>Q</math>
+* राज्यों का परिमित [[सेट (गणित)]]। <math>Q</math>
-* [[इनपुट प्रतीक]]ों का एक परिमित सेट <math>\Sigma</math>
+* [[इनपुट प्रतीक]]ों का परिमित सेट <math>\Sigma</math>
-* एक संक्रमण समारोह <math>\delta:Q\times\Sigma \to \wp(Q)</math>
+*संक्रमण समारोह <math>\delta:Q\times\Sigma \to \wp(Q)</math>
-* राज्यों का एक समूह <math>F</math> स्वीकृत (या अंतिम) राज्यों के रूप में प्रतिष्ठित <math>F\subseteq Q</math>.
+* राज्यों का समूह <math>F</math> स्वीकृत (या अंतिम) राज्यों के रूप में प्रतिष्ठित <math>F\subseteq Q</math>.
-यहाँ, <math>\wp(Q)</math> के [[ सत्ता स्थापित ]] को दर्शाता है <math>Q</math>.
+यहाँ, <math>\wp(Q)</math> के [[ सत्ता स्थापित |सत्ता स्थापित]] को दर्शाता है <math>Q</math>.
-[[करी]]ंग के उपयोग से, संक्रमण समारोह <math>\delta:Q\times\Sigma \to \wp(Q)</math> एक गैर-नियतात्मक परिमित automaton को [[सदस्यता समारोह]] के रूप में लिखा जा सकता है
+[[करी]]ंग के उपयोग से, संक्रमण समारोह <math>\delta:Q\times\Sigma \to \wp(Q)</math> गैर-नियतात्मक परिमित automaton को [[सदस्यता समारोह]] के रूप में लिखा जा सकता है
 :<math>\delta:Q\times\Sigma \times Q\to \{0,1\}</math>
@@ Line 26: / Line 25: @@
 :<math>\left[\theta_a\right]_{qq^\prime}=\delta(q,a,q^\prime)</math>
-गणित का सवाल <math>\theta_a</math> तब एक वर्ग मैट्रिक्स है, जिसकी प्रविष्टियाँ शून्य या एक हैं, यह दर्शाता है कि संक्रमण है या नहीं <math>q\stackrel{a}{\rightarrow} q^\prime</math> एनएफए द्वारा अनुमति दी जाती है। इस तरह के एक संक्रमण मैट्रिक्स को हमेशा एक गैर-नियतात्मक परिमित automaton के लिए परिभाषित किया जाता है।
+गणित का सवाल <math>\theta_a</math> तब वर्ग मैट्रिक्स है, जिसकी प्रविष्टियाँ शून्य या एक हैं, यह दर्शाता है कि संक्रमण है या नहीं <math>q\stackrel{a}{\rightarrow} q^\prime</math> एनएफए द्वारा अनुमति दी जाती है। इस तरह के संक्रमण मैट्रिक्स को हमेशा गैर-नियतात्मक परिमित automaton के लिए परिभाषित किया जाता है।
-संभाव्य automaton इन matrices को स्टोकास्टिक मैट्रिक्स के परिवार द्वारा प्रतिस्थापित करता है <math>P_a</math>, वर्णमाला में प्रत्येक प्रतीक a के लिए <math>\Sigma</math> ताकि एक संक्रमण की संभावना द्वारा दिया जाता है
+संभाव्य automaton इन matrices को स्टोकास्टिक मैट्रिक्स के परिवार द्वारा प्रतिस्थापित करता है <math>P_a</math>, वर्णमाला में प्रत्येक प्रतीक a के लिए <math>\Sigma</math> ताकि संक्रमण की संभावना द्वारा दिया जाता है
 :<math>\left[P_a\right]_{qq^\prime}</math>
-किसी राज्य से किसी भी राज्य में एक राज्य परिवर्तन निश्चित रूप से प्रायिकता के साथ होना चाहिए, और इसलिए किसी के पास होना चाहिए
+किसी राज्य से किसी भी राज्य में राज्य परिवर्तन निश्चित रूप से प्रायिकता के साथ होना चाहिए, और इसलिए किसी के पास होना चाहिए
 :<math>\sum_{q^\prime}\left[P_a\right]_{qq^\prime}=1</math>
-सभी इनपुट पत्रों के लिए <math>a</math> और आंतरिक राज्य <math>q</math>. एक संभाव्य automaton की प्रारंभिक स्थिति एक [[पंक्ति वेक्टर]] द्वारा दी गई है <math>v</math>, जिनके घटक व्यक्तिगत प्रारंभिक अवस्थाओं की संभावनाएँ हैं <math>q</math>, जो 1 में जोड़ें:
+सभी इनपुट पत्रों के लिए <math>a</math> और आंतरिक राज्य <math>q</math>. संभाव्य automaton की प्रारंभिक स्थिति [[पंक्ति वेक्टर]] द्वारा दी गई है <math>v</math>, जिनके घटक व्यक्तिगत प्रारंभिक अवस्थाओं की संभावनाएँ हैं <math>q</math>, जो 1 में जोड़ें:
 :<math>\sum_{q}\left[v\right]_{q}=1</math>
@@ Line 40: / Line 39: @@
 :<math>v P_a P_b P_c</math>
-विशेष रूप से, एक संभाव्य automaton की स्थिति हमेशा एक स्टोकास्टिक वेक्टर होती है, क्योंकि किसी भी दो स्टोकास्टिक मैट्रिक्स का उत्पाद एक स्टोकास्टिक मैट्रिक्स होता है, और एक स्टोकास्टिक वेक्टर और स्टोकास्टिक मैट्रिक्स का उत्पाद फिर से एक स्टोकास्टिक वेक्टर होता है। इस सदिश को कभी-कभी राज्यों का वितरण कहा जाता है, यह बल देते हुए कि यह एक [[असतत संभाव्यता वितरण]] है।
+विशेष रूप से, संभाव्य automaton की स्थिति हमेशा स्टोकास्टिक वेक्टर होती है, क्योंकि किसी भी दो स्टोकास्टिक मैट्रिक्स का उत्पाद स्टोकास्टिक मैट्रिक्स होता है, और स्टोकास्टिक वेक्टर और स्टोकास्टिक मैट्रिक्स का उत्पाद फिर से स्टोकास्टिक वेक्टर होता है। इस सदिश को कभी-कभी राज्यों का वितरण कहा जाता है, यह बल देते हुए कि यह [[असतत संभाव्यता वितरण]] है।
-औपचारिक रूप से, एक संभाव्य ऑटोमेटन की परिभाषा के लिए गैर-नियतात्मक ऑटोमेटन के यांत्रिकी की आवश्यकता नहीं होती है, जिसके साथ विवाद हो सकता है। औपचारिक रूप से, एक संभाव्य automaton ''PA'' को tuple के रूप में परिभाषित किया गया है <math>(Q,\Sigma,P, v, F)</math>. एक राबिन automaton वह है जिसके लिए प्रारंभिक वितरण होता है <math>v</math> एक [[समन्वय वेक्टर]] है; अर्थात्, एक प्रविष्टि को छोड़कर सभी के लिए शून्य है, और शेष प्रविष्टि एक है।
+औपचारिक रूप से, संभाव्य ऑटोमेटन की परिभाषा के लिए गैर-नियतात्मक ऑटोमेटन के यांत्रिकी की आवश्यकता नहीं होती है, जिसके साथ विवाद हो सकता है। औपचारिक रूप से, संभाव्य automaton ''PA'' को tuple के रूप में परिभाषित किया गया है <math>(Q,\Sigma,P, v, F)</math>. राबिन automaton वह है जिसके लिए प्रारंभिक वितरण होता है <math>v</math> [[समन्वय वेक्टर]] है; अर्थात्, प्रविष्टि को छोड़कर सभी के लिए शून्य है, और शेष प्रविष्टि है।
 == स्टोकेस्टिक भाषाएँ ==
-संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त औपचारिक भाषा के सेट को स्टोकेस्टिक भाषा कहा जाता है। वे एक उपसमुच्चय के रूप में नियमित भाषाओं को शामिल करते हैं।
+संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त औपचारिक भाषा के सेट को स्टोकेस्टिक भाषा कहा जाता है। वे उपसमुच्चय के रूप में नियमित भाषाओं को शामिल करते हैं।
-होने देना <math>F=Q_\text{accept}\subseteq Q</math> ऑटोमेटन की स्वीकृति या अंतिम अवस्थाओं का सेट हो। अंकन के दुरुपयोग से, <math>Q_\text{accept}</math> कॉलम वेक्टर के रूप में भी समझा जा सकता है जो कि सदस्यता कार्य है <math>Q_\text{accept}</math>; अर्थात्, इसमें तत्वों के संगत स्थानों पर 1 है  <math>Q_\text{accept}</math>, और एक शून्य अन्यथा। इस वेक्टर को एक स्केलर (गणित) बनाने के लिए आंतरिक स्थिति संभावना के साथ अनुबंधित किया जा सकता है। एक विशिष्ट automaton द्वारा मान्यता प्राप्त भाषा को तब परिभाषित किया जाता है
+होने देना <math>F=Q_\text{accept}\subseteq Q</math> ऑटोमेटन की स्वीकृति या अंतिम अवस्थाओं का सेट हो। अंकन के दुरुपयोग से, <math>Q_\text{accept}</math> कॉलम वेक्टर के रूप में भी समझा जा सकता है जो कि सदस्यता कार्य है <math>Q_\text{accept}</math>; अर्थात्, इसमें तत्वों के संगत स्थानों पर 1 है <math>Q_\text{accept}</math>, और एक शून्य अन्यथा। इस वेक्टर को स्केलर (गणित) बनाने के लिए आंतरिक स्थिति संभावना के साथ अनुबंधित किया जा सकता है। विशिष्ट automaton द्वारा मान्यता प्राप्त भाषा को तब परिभाषित किया जाता है
 :<math>L_\eta = \{s\in\Sigma^* \vert vP_s Q_\text{accept} > \eta\}</math>
 कहाँ <math>\Sigma^*</math> [[वर्णमाला (कंप्यूटर विज्ञान)]] में सभी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] का सेट है <math>\Sigma</math> (ताकि * [[क्लेन स्टार]] हो)। भाषा कट-पॉइंट के मान पर निर्भर करती है <math>\eta</math>, आमतौर पर सीमा में होने के लिए लिया जाता है <math>0\le \eta<1</math>.
-एक भाषा को ''η'' कहा जाता है - स्टोचैस्टिक अगर और केवल अगर वहाँ कुछ पीए मौजूद है जो निश्चित रूप से भाषा को पहचानता है <math>\eta</math>. एक भाषा को स्टोकेस्टिक कहा जाता है अगर और केवल अगर कुछ है  <math>0\le \eta<1</math> जिसके लिए <math>L_\eta</math> η-स्टोकेस्टिक है।
+भाषा को ''η'' कहा जाता है - स्टोचैस्टिक अगर और केवल अगर वहाँ कुछ पीए मौजूद है जो निश्चित रूप से भाषा को पहचानता है <math>\eta</math>. भाषा को स्टोकेस्टिक कहा जाता है अगर और केवल अगर कुछ है <math>0\le \eta<1</math> जिसके लिए <math>L_\eta</math> η-स्टोकेस्टिक है।
-एक कट-प्वाइंट को 'पृथक कट-पॉइंट' कहा जाता है अगर और केवल अगर मौजूद हो <math>\delta>0</math> ऐसा है कि
+कट-प्वाइंट को 'पृथक कट-पॉइंट' कहा जाता है अगर और केवल अगर मौजूद हो <math>\delta>0</math> ऐसा है कि
 :<math>\vert vP(s)Q_\text{accept} - \eta \vert \ge \delta</math>
@@ Line 61: / Line 60: @@
 == गुण ==
-हर नियमित भाषा स्टोचैस्टिक है, और अधिक दृढ़ता से, हर नियमित भाषा η-स्टोकेस्टिक है। एक कमजोर आक्षेप यह है कि प्रत्येक 0-स्टोकेस्टिक भाषा नियमित है; हालाँकि, सामान्य बातचीत पकड़ में नहीं आती है: ऐसी स्टोकेस्टिक भाषाएँ हैं जो नियमित नहीं हैं।
+हर नियमित भाषा स्टोचैस्टिक है, और अधिक दृढ़ता से, हर नियमित भाषा η-स्टोकेस्टिक है। कमजोर आक्षेप यह है कि प्रत्येक 0-स्टोकेस्टिक भाषा नियमित है; हालाँकि, सामान्य बातचीत पकड़ में नहीं आती है: ऐसी स्टोकेस्टिक भाषाएँ हैं जो नियमित नहीं हैं।
 प्रत्येक η-स्टोकेस्टिक भाषा कुछ के लिए स्टोकेस्टिक है <math>0<\eta<1</math>.
@@ Line 67: / Line 66: @@
 प्रत्येक स्टोकेस्टिक भाषा को राबिन ऑटोमेटन द्वारा प्रदर्शित किया जा सकता है।
-अगर <math>\eta</math> एक पृथक कट-पॉइंट है, फिर <math>L_\eta</math> नियमित भाषा है।
+अगर <math>\eta</math> पृथक कट-पॉइंट है, फिर <math>L_\eta</math> नियमित भाषा है।
 ==p-adic भाषाएँ==
-पी-एडिक | पी-एडिक भाषाएं एक स्टोकास्टिक भाषा का उदाहरण प्रदान करती हैं जो नियमित नहीं है, और यह भी दिखाती है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। एक पी-एडिक भाषा को स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है
+पी-एडिक | पी-एडिक भाषाएं स्टोकास्टिक भाषा का उदाहरण प्रदान करती हैं जो नियमित नहीं है, और यह भी दिखाती है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। पी-एडिक भाषा को स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है
 :<math>L_{\eta}(p)=\{n_1n_2n_3 \ldots \vert 0\le n_k<p \text{ and }
@@ Line 76: / Line 75: @@
 पत्रों में <math>0,1,2,\ldots,(p-1)</math>.
-अर्थात्, एक p-adic भाषा केवल [0, 1] में वास्तविक संख्याओं का समुच्चय है, जिसे आधार-p में लिखा गया है, जैसे कि वे इससे अधिक हैं <math>\eta</math>. यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ स्टोकेस्टिक हैं।<ref>{{cite arXiv |eprint=2103.14423|author1=Merve Nur Cakir|last2=Saleemi|first2=Mehwish|last3=Zimmermann|first3=Karl-Heinz|title=स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर|year=2021|class=cs.FL}}</ref> विशेष रूप से, इसका तात्पर्य है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। एक पी-एडिक भाषा नियमित है अगर और केवल अगर <math>\eta</math> तर्कसंगत है।
+अर्थात्, p-adic भाषा केवल [0, 1] में वास्तविक संख्याओं का समुच्चय है, जिसे आधार-p में लिखा गया है, जैसे कि वे इससे अधिक हैं <math>\eta</math>. यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ स्टोकेस्टिक हैं।<ref>{{cite arXiv |eprint=2103.14423|author1=Merve Nur Cakir|last2=Saleemi|first2=Mehwish|last3=Zimmermann|first3=Karl-Heinz|title=स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर|year=2021|class=cs.FL}}</ref> विशेष रूप से, इसका तात्पर्य है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। पी-एडिक भाषा नियमित है अगर और केवल अगर <math>\eta</math> तर्कसंगत है।
 == सामान्यीकरण ==
-संभाव्य automaton की एक ज्यामितीय व्याख्या है: राज्य वेक्टर को एक बिंदु के रूप में समझा जा सकता है जो ऑर्थोगोनल कोने के विपरीत मानक [[संकेतन]] के चेहरे पर रहता है। ट्रांज़िशन मेट्रिसेस बिंदु पर अभिनय करते हुए एक [[मोनोइड]] बनाते हैं। यह बिंदु कुछ सामान्य [[टोपोलॉजिकल स्पेस]] से होने के कारण सामान्यीकृत हो सकता है, जबकि ट्रांज़िशन मेट्रिसेस को टोपोलॉजिकल स्पेस पर काम करने वाले ऑपरेटरों के एक संग्रह से चुना जाता है, इस प्रकार एक सेमीऑटोमेटन का निर्माण होता है। जब कट-पॉइंट को उपयुक्त रूप से सामान्यीकृत किया जाता है, तो एक [[टोपोलॉजिकल ऑटोमेटन]] होता है।
+संभाव्य automaton की ज्यामितीय व्याख्या है: राज्य वेक्टर को बिंदु के रूप में समझा जा सकता है जो ऑर्थोगोनल कोने के विपरीत मानक [[संकेतन]] के चेहरे पर रहता है। ट्रांज़िशन मेट्रिसेस बिंदु पर अभिनय करते हुए [[मोनोइड]] बनाते हैं। यह बिंदु कुछ सामान्य [[टोपोलॉजिकल स्पेस]] से होने के कारण सामान्यीकृत हो सकता है, जबकि ट्रांज़िशन मेट्रिसेस को टोपोलॉजिकल स्पेस पर काम करने वाले ऑपरेटरों के संग्रह से चुना जाता है, इस प्रकार सेमीऑटोमेटन का निर्माण होता है। जब कट-पॉइंट को उपयुक्त रूप से सामान्यीकृत किया जाता है, तो [[टोपोलॉजिकल ऑटोमेटन]] होता है।
-ऐसे सामान्यीकरण का एक उदाहरण क्वांटम परिमित ऑटोमेटन है; यहां, ऑटोमेटन राज्य को [[जटिल प्रक्षेप्य स्थान]] में एक बिंदु द्वारा दर्शाया गया है, जबकि संक्रमण मेट्रिसेस [[एकात्मक समूह]] से चुना गया एक निश्चित सेट है। कट-प्वाइंट को [[क्वांटम कोण]] के अधिकतम मान की सीमा के रूप में समझा जाता है।
+ऐसे सामान्यीकरण का उदाहरण क्वांटम परिमित ऑटोमेटन है; यहां, ऑटोमेटन राज्य को [[जटिल प्रक्षेप्य स्थान]] में बिंदु द्वारा दर्शाया गया है, जबकि संक्रमण मेट्रिसेस [[एकात्मक समूह]] से चुना गया निश्चित सेट है। कट-प्वाइंट को [[क्वांटम कोण]] के अधिकतम मान की सीमा के रूप में समझा जाता है।
 ==टिप्पणियाँ==

Anonymous

Search

संभाव्य ऑटोमेटन: Difference between revisions

Namespaces

More

Page actions

Revision as of 00:18, 5 June 2023

Contents

अनौपचारिक विवरण

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

स्टोकेस्टिक भाषाएँ

गुण

p-adic भाषाएँ

सामान्यीकरण

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संभाव्य ऑटोमेटन: Difference between revisions

Revision as of 00:18, 5 June 2023

अनौपचारिक विवरण

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

स्टोकेस्टिक भाषाएँ

गुण

p-adic भाषाएँ

सामान्यीकरण

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories