स्वचालित अनुक्रम: Difference between revisions

From Vigyanwiki
(Created page with "गणित और सैद्धांतिक कंप्यूटर विज्ञान में, एक स्वचालित अनुक्रम (ज...")
 
No edit summary
Line 1: Line 1:
गणित और [[सैद्धांतिक कंप्यूटर विज्ञान]] में, एक स्वचालित [[अनुक्रम]] (जिसे ''k''-स्वचालित अनुक्रम या ''k''-पहचान योग्य अनुक्रम भी कहा जाता है, जब कोई यह इंगित करना चाहता है कि उपयोग किए गए अंकों का आधार ''k'' है ) एक [[परिमित automaton]] की विशेषता वाले शब्दों का एक अनंत क्रम है। एक स्वचालित अनुक्रम ''a''(''n'') का ''n''-वाँ शब्द अंतिम अवस्था का मानचित्रण है, जो कुछ में संख्या ''n'' के अंकों को स्वीकार करने वाले परिमित ऑटोमेटन में पहुंचा है। निश्चित [[मूलांक]] ''क''।<ref name=as1>Allouche & Shallit (2003) p.&nbsp;152</ref><ref name=BLRS78>Berstel et al (2009) p.&nbsp;78</ref>
गणित और [[सैद्धांतिक कंप्यूटर विज्ञान]] में, एक स्वचालित [[अनुक्रम]] (जिसे ''k''-स्वचालित अनुक्रम या ''k''-पहचानने योग्य अनुक्रम भी कहा जाता है, जब कोई यह इंगित करना चाहता है कि उपयोग किए गए अंकों का आधार ''k'' है ) एक [[परिमित automaton|परिमित स्वचल प्ररूप]] की विशेषता वाले शब्दों का एक अनंत क्रम है। एक स्वचालित अनुक्रम ''a''(''n'') का ''n''-वाँ शब्द अंतिम अवस्था का मानचित्रण है, जो कुछ में संख्या ''n'' के अंकों को स्वीकार करने वाले परिमित स्वचल प्ररूप में पहुंचा है। निश्चित [[मूलांक]] ''क''।<ref name=as1>Allouche & Shallit (2003) p.&nbsp;152</ref><ref name=BLRS78>Berstel et al (2009) p.&nbsp;78</ref>
एक स्वचालित सेट गैर-ऋणात्मक पूर्णांक ''S'' का एक सेट है, जिसके लिए इसकी विशेषता फ़ंक्शन χ के मानों का क्रम होता है<sub>''S''</sub> एक स्वचालित अनुक्रम है; अर्थात्, यदि χ है तो S k-स्वचालित है<sub>''S''</sub>(एन) के-स्वचालित है, जहां χ<sub>''S''</sub>(एन) = 1 अगर एन<math>\in</math>एस और 0 अन्यथा।<ref>Allouche & Shallit (2003) p.&nbsp;168</ref><ref name=PF13/>
एक स्वचालित सम्मुच्चय गैर-ऋणात्मक पूर्णांक ''S'' का एक सम्मुच्चय है, जिसके लिए इसकी विशेषता फलन χ<sub>''S''</sub> के मानों का क्रम एक स्वचालित अनुक्रम है; अर्थात्, यदि χ<sub>''S''</sub>(n) है तो S k-स्वचालित है, जहां χ<sub>''S''</sub>(n) = 1 अगर n <math>\in</math> s और अन्यथा 0 है।<ref>Allouche & Shallit (2003) p.&nbsp;168</ref><ref name=PF13/>




Line 7: Line 7:
स्वचालित अनुक्रमों को कई तरीकों से परिभाषित किया जा सकता है, जो सभी समतुल्य हैं। चार सामान्य परिभाषाएँ इस प्रकार हैं।
स्वचालित अनुक्रमों को कई तरीकों से परिभाषित किया जा सकता है, जो सभी समतुल्य हैं। चार सामान्य परिभाषाएँ इस प्रकार हैं।


=== ऑटोमेटा-सैद्धांतिक ===
=== स्वचल प्ररूप-सैद्धांतिक ===
मान लीजिए k एक धनात्मक [[पूर्णांक]] है, और मान लीजिए D = (Q, Σ<sub>''k''</sub>, डी, क्यू<sub>0</sub>, Δ, τ) आउटपुट के साथ एक निर्धारक परिमित automaton बनें, जहां
मान लीजिए k एक धनात्मक [[पूर्णांक]] है, और मान लीजिए D = (Q, Σ<sub>''k''</sub>, δ, q<sub>0</sub>, Δ, τ) प्रक्षेपण के साथ एक निर्धारक परिमित स्वचल प्ररूप बनें, जहां
* क्यू राज्यों का परिमित [[सेट (गणित)]] है;
* q स्थिति का परिमित [[सेट (गणित)|सम्मुच्चय (गणित)]] है;
* इनपुट वर्णमाला Σ<sub>''k''</sub> रेडिक्स-के नोटेशन में संभावित अंकों के सेट {0,1,...,k-1} शामिल हैं;
* निविष्ट वर्णमाला Σ<sub>''k''</sub> मूलांक-के चिन्हांकन में संभावित अंकों के सम्मुच्चय {0,1,...,k-1} सम्मिलित हैं;
*δ : क्यू × Σ<sub>''k''</sub> → क्यू संक्रमण समारोह है;
*δ : q × Σ<sub>''k''</sub> → q संक्रमण फलन है;
*क्यू<sub>0</sub>∈ क्यू प्रारंभिक अवस्था है;
*q<sub>0</sub>∈ q प्रारंभिक अवस्था है;
*आउटपुट अल्फाबेट Δ एक परिमित सेट है; और
*प्रक्षेपण वर्णक्रम Δ एक परिमित सम्मुच्चय है; और
*τ : क्यू → Δ आंतरिक राज्यों के सेट से आउटपुट वर्णमाला में आउटपुट फ़ंक्शन मैपिंग है।
*τ : q → Δ आंतरिक स्थिति के सम्मुच्चय से प्रक्षेपण वर्णमाला में प्रक्षेपण फलन प्रतिचित्रण है।


एक स्ट्रिंग s पर δ की क्रिया को परिभाषित करके संक्रमण फ़ंक्शन δ को एकल अंकों पर अभिनय से अंकों के तारों पर अभिनय करने तक बढ़ाएं।<sub>1</sub>s<sub>2</sub>...एस<sub>''t''</sub> जैसा:
एक श्रृंखला s<sub>1</sub>s<sub>2</sub>...s<sub>''t''</sub> पर δ की क्रिया को परिभाषित करके फलन δ को एकल अंकों पर अभिनय से अंकों के तारों पर अभिनय करने तक बढ़ाएं। जैसे:


: δ (क्यू, एस) = δ (δ (क्यू, एस<sub>1</sub>s<sub>2</sub>...एस<sub>''t''-1</sub>), एस<sub>''t''</sub>).
: δ (q, S) = δ (δ (q, S<sub>1</sub>s<sub>2</sub>...S<sub>''t''-1</sub>), S<sub>''t''</sub>).


एक फ़ंक्शन को सकारात्मक पूर्णांक के सेट से आउटपुट वर्णमाला Δ में निम्नानुसार परिभाषित करें:
एक फलन को सकारात्मक पूर्णांक के सम्मुच्चय से प्रक्षेपण वर्णमाला Δ में निम्नानुसार परिभाषित करें:


: (एन) = τ (δ (क्यू<sub>0</sub>, एस (एन))),
: ''a''(''n'') = τ(δ(''q<sub>0</sub>'',''s''(''n''))),


जहाँ s(n) को आधार k में लिखा गया है। तब अनुक्रम a = a(1)a(2)a(3)... एक k-स्वचालित अनुक्रम है।<ref name=as1/>
जहाँ s(n) को आधार k में लिखा गया है। तब अनुक्रम a = a(1)a(2)a(3)... एक k-स्वचालित अनुक्रम है।<ref name=as1/>


सबसे महत्वपूर्ण अंक से शुरू होने वाले s(n) के आधार k अंकों को पढ़ने वाला ऑटोमेटन डायरेक्ट रीडिंग कहा जाता है, जबकि कम से कम महत्वपूर्ण अंक से शुरू होने वाला ऑटोमेटन रिवर्स रीडिंग है।<ref name=PF13>Pytheas Fogg (2002) p.&nbsp;13</ref> उपरोक्त परिभाषा यह मानती है कि s(n) प्रत्यक्ष या विपरीत पठन है या नहीं।<ref name=PF15>Pytheas Fogg (2002) p.&nbsp;15</ref>
सबसे महत्वपूर्ण अंक से प्रारम्भ होने वाले s(n) के आधार k अंकों को पढ़ने वाला स्वचल प्ररूप प्रत्यक्ष पठन कहा जाता है, जबकि कम से कम महत्वपूर्ण अंक से प्रारम्भ होने वाला स्वचल प्ररूप पंट पठन है। <ref name=PF13>Pytheas Fogg (2002) p.&nbsp;13</ref> उपरोक्त परिभाषा यह मानती है कि s(n) प्रत्यक्ष या विपरीत पठन है या नहीं है।<ref name=PF15>Pytheas Fogg (2002) p.&nbsp;15</ref>




=== प्रतिस्थापन ===
=== प्रतिस्थापन ===
होने देना <math>\varphi</math> मुक्त मोनॉइड का k-वर्दी आकारिकी हो <math>\Sigma^*</math> और जाने <math>\tau</math> एक कोडिंग हो (यानी, a <math>1</math>-समान रूपवाद), जैसा कि ऑटोमेटा-सैद्धांतिक मामले में है। अगर <math>w</math> का एक [[निश्चित बिंदु (गणित)]] है <math>\varphi</math>- यानी अगर <math>w = \varphi(w)</math>-तब <math>s = \tau(w)</math> एक के-स्वचालित अनुक्रम है।<ref name=AS175>Allouche & Shallit (2003) p.&nbsp;175</ref> इसके विपरीत, प्रत्येक के-स्वचालित अनुक्रम इस तरह से प्राप्य है।<ref name=PF13/>यह परिणाम एलन कोभम (गणितज्ञ) के कारण है, और इसे साहित्य में कोभम की छोटी प्रमेय के रूप में संदर्भित किया जाता है।<ref name=BLRS78/><ref name=C72>Cobham (1972)</ref>
मान लीजिए <math>\varphi</math> मुक्त मोनॉइड <math>\Sigma^*</math> का k-समान आकारिकी है और <math>\tau</math> एक कूटलेखन हो (यानी, a <math>1</math>-समान रूपवाद), जैसा कि स्वचल प्ररूप-सैद्धांतिक स्तिथि में है। यदि <math>w</math> <math>\varphi</math> का एक निश्चित बिंदु है - अर्थात, यदि <math>w = \varphi(w)</math> तो <math>s = \tau(w)</math> एक k-स्वचालित क्रम है। <ref name=AS175>Allouche & Shallit (2003) p.&nbsp;175</ref> इसके विपरीत, प्रत्येक k-स्वचालित अनुक्रम इस तरह से प्राप्य है। <ref name=PF13/> यह परिणाम एलन कोभम (गणितज्ञ) के कारण है, और इसे साहित्य में कोभम की छोटी प्रमेय के रूप में संदर्भित किया जाता है।<ref name=BLRS78/><ref name=C72>Cobham (1972)</ref>




=== के-कर्नेल ===
=== के-कर्नेल ===
मान लीजिए k ≥ 2. अनुक्रम s(n) का k-कर्नेल अनुक्रमों का समूह है
मान लीजिए k ≥ 2 है। अनुक्रम s(n) का k-कर्नेल अनुगामी का समुच्चय है
:<math>K_{k}(s) = \{s(k^e n + r) : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}.</math>
:<math>K_{k}(s) = \{s(k^e n + r) : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}.</math>
ज्यादातर मामलों में, अनुक्रम का के-कर्नेल अनंत है। हालाँकि, यदि k-कर्नेल परिमित है, तो अनुक्रम s(n) k-स्वचालित है, और इसका विलोम भी सत्य है। यह ईलेनबर्ग के कारण है।<ref name=AS185>Allouche & Shallit (2003) p.&nbsp;185</ref><ref name=ApCOw527>Lothaire (2005) p.&nbsp;527</ref><ref name=BR91>Berstel & Reutenauer (2011) p.&nbsp;91</ref>
अधिकतर स्तिथियों में, अनुक्रम का k-कर्नेल अनंत है। हालाँकि, यदि k-कर्नेल परिमित है, तो अनुक्रम s(n) k-स्वचालित है, और इसका विलोम भी सत्य है। यह ईलेनबर्ग के कारण है।<ref name=AS185>Allouche & Shallit (2003) p.&nbsp;185</ref><ref name=ApCOw527>Lothaire (2005) p.&nbsp;527</ref><ref name=BR91>Berstel & Reutenauer (2011) p.&nbsp;91</ref>
यह इस प्रकार है कि एक के-स्वचालित अनुक्रम आवश्यक रूप से एक परिमित वर्णमाला पर एक अनुक्रम है।
 
यह इस प्रकार है कि एक k-स्वचालित अनुक्रम आवश्यक रूप से एक परिमित वर्णमाला पर एक अनुक्रम है।


=== औपचारिक शक्ति श्रृंखला ===
=== औपचारिक शक्ति श्रृंखला ===
चलो u(n) एक वर्णमाला Σ पर अनुक्रम हो और मान लें कि Σ से सीमित क्षेत्र 'एफ' तक एक [[इंजेक्शन समारोह]] β है<sub>''q''</sub>, जहां क्यू = पी<sup>n</sup> कुछ अभाज्य p के लिए। संबंधित [[औपचारिक शक्ति श्रृंखला]] है
मान लीजिए u(n) एक वर्णमाला Σ पर अनुक्रम है और मान लें कि Σ से सीमित क्षेत्र F<sub>''q''</sub> तक एक [[इंजेक्शन समारोह|अंतःक्षेपक फलन]] β है, जहां कुछ अभाज्य p के लिए q = p<sup>n</sup> है। संबंधित [[औपचारिक शक्ति श्रृंखला]] निम्न है
:<math> \sum_{i \geq 0} \beta(u(i)) X^i . </math> तब अनुक्रम u q-स्वचालित है यदि और केवल यदि यह औपचारिक शक्ति श्रृंखला 'F' पर [[बीजगणितीय कार्य]] है<sub>''q''</sub>(एक्स)यह परिणाम क्रिस्टोल के कारण है, और इसे साहित्य में क्रिस्टोल के प्रमेय के रूप में जाना जाता है।<ref>{{cite journal | first=G. | last=Christol | title=Ensembles presque périodiques ''k''-reconnaissables | journal=Theoret. Comput. Sci. | volume=9 | year=1979 | pages=141–145 | doi=10.1016/0304-3975(79)90011-2 | doi-access=free }}</ref>
:<math> \sum_{i \geq 0} \beta(u(i)) X^i </math>  
:तब अनुक्रम u q-स्वचालित है यदि और केवल यदि यह औपचारिक शक्ति श्रृंखला '''F'''<sub>''q''</sub>(''X'') पर [[बीजगणितीय कार्य]] है। यह परिणाम क्रिस्टोल के कारण है, और इसे साहित्य में क्रिस्टोल के प्रमेय के रूप में जाना जाता है।<ref>{{cite journal | first=G. | last=Christol | title=Ensembles presque périodiques ''k''-reconnaissables | journal=Theoret. Comput. Sci. | volume=9 | year=1979 | pages=141–145 | doi=10.1016/0304-3975(79)90011-2 | doi-access=free }}</ref>




== इतिहास ==
== इतिहास ==
1960 में जूलियस रिचर्ड बुची|बुची द्वारा स्वचालित अनुक्रम पेश किए गए,<ref>{{cite book | first=J. R. | last=Büchi | title=The Collected Works of J. Richard Büchi | chapter=Weak second-order arithmetic and finite automata | journal=Z. Math. Logik Grundlagen Math. | volume=6 | year=1960 | pages=66–92 | doi=10.1007/978-1-4613-8928-6_22 | isbn=978-1-4613-8930-9 }}</ref> हालांकि उनके पेपर ने इस मामले में अधिक तार्किक-सैद्धांतिक दृष्टिकोण अपनाया और इस लेख में पाई जाने वाली शब्दावली का उपयोग नहीं किया। 1972 में कोभम द्वारा स्वचालित अनुक्रमों की धारणा का और अध्ययन किया गया, जिन्होंने इन अनुक्रमों को एकसमान [[टैग प्रणाली]] कहा।<ref name=C72/>
1960 में जूलियस रिचर्ड बुची द्वारा स्वचालित अनुक्रम प्रस्तुत किए गए,<ref>{{cite book | first=J. R. | last=Büchi | title=The Collected Works of J. Richard Büchi | chapter=Weak second-order arithmetic and finite automata | journal=Z. Math. Logik Grundlagen Math. | volume=6 | year=1960 | pages=66–92 | doi=10.1007/978-1-4613-8928-6_22 | isbn=978-1-4613-8930-9 }}</ref> हालांकि उनके लेख ने इस स्तिथि में अधिक तार्किक-सैद्धांतिक दृष्टिकोण अपनाया और इस लेख में पाई जाने वाली शब्दावली का उपयोग नहीं किया। 1972 में कोभम द्वारा स्वचालित अनुक्रमों की धारणा का और अध्ययन किया गया, जिन्होंने इन अनुक्रमों को एकसमान [[टैग प्रणाली]] कहा था।<ref name=C72/>


स्वत: अनुक्रम शब्द पहली बार देशोइलर्स के एक पेपर में दिखाई दिया।<ref>{{cite journal | first=J.-M. | last=Deshouillers | title=La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini | journal=Séminaire de Théorie des Nombres de Bordeaux | year=1979–1980 | pages=5.01–5.22 }}</ref>
स्वत: अनुक्रम शब्द पहली बार देशोइलर्स के एक लेख में दिखाई दिया।<ref>{{cite journal | first=J.-M. | last=Deshouillers | title=La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini | journal=Séminaire de Théorie des Nombres de Bordeaux | year=1979–1980 | pages=5.01–5.22 }}</ref>




Line 54: Line 56:


===थू-मोर्स क्रम===
===थू-मोर्स क्रम===
[[File:ThueMorseAutomaton.png|thumb|डीएफएओ थू-मोर्स अनुक्रम उत्पन्न करता है]]थू-मोर्स अनुक्रम टी(एन) ({{OEIS2C|id=A010060}}) रूपवाद 0 → 01, 1 → 10 का निश्चित बिंदु (गणित) है। चूंकि थ्यू-मोर्स अनुक्रम का n-वाँ पद n के आधार-2 प्रतिनिधित्व में [[मोडुलो ऑपरेशन]] 2 की संख्या की गणना करता है, यह यहाँ चित्रित आउटपुट के साथ दो-राज्य नियतात्मक परिमित ऑटोमेटन द्वारा उत्पन्न होता है, जहाँ राज्य q में होता है<sub>0</sub> इंगित करता है कि n के प्रतिनिधित्व में और राज्य q में होने की संख्या भी है<sub>1</sub> इंगित करता है कि विषम संख्याएँ हैं।
[[File:ThueMorseAutomaton.png|thumb|डीएफएओ थू-मोर्स अनुक्रम उत्पन्न करता है]]'''थू-मोर्स अनुक्रम''' टी(एन) ({{OEIS2C|id=A010060}}) रूपवाद 0 → 01, 1 → 10 का निश्चित बिंदु (गणित) है। चूंकि थ्यू-मोर्स अनुक्रम का n-वाँ पद n के आधार-2 प्रतिनिधित्व में [[मोडुलो ऑपरेशन]] 2 की संख्या की गणना करता है, यह यहाँ चित्रित प्रक्षेपण के साथ दो-राज्य नियतात्मक परिमित स्वचल प्ररूप द्वारा उत्पन्न होता है, जहाँ राज्य q में होता है<sub>0</sub> इंगित करता है कि n के प्रतिनिधित्व में और राज्य q में होने की संख्या भी है<sub>1</sub> इंगित करता है कि विषम संख्याएँ हैं।
इसलिए, थ्यू-मोर्स अनुक्रम 2-स्वचालित है।
इसलिए, थ्यू-मोर्स अनुक्रम 2-स्वचालित है।


=== अवधि-दोहरीकरण अनुक्रम ===
=== अवधि-दोहरीकरण अनुक्रम ===
अवधि-दोहरीकरण अनुक्रम का n-वाँ पद d(n) ({{OEIS2C|id=A096268}}) 2 विभाजक n की उच्चतम शक्ति के घातांक की समानता से निर्धारित होता है। यह आकृतिवाद 0 → 01, 1 → 00 का निश्चित बिंदु भी है।<ref name=AS176>Allouche & Shallit (2003) p.&nbsp;176</ref> प्रारंभिक शब्द w = 0 से शुरू करना और 2-समान आकारिकी φ को w पर पुनरावृत्त करना जहां φ(0) = 01 और φ(1) = 00, यह स्पष्ट है कि अवधि-दोहरीकरण अनुक्रम φ का निश्चित-बिंदु है ( डब्ल्यू) और इस प्रकार यह 2-स्वचालित है।
अवधि-दोहरीकरण अनुक्रम का n-वाँ पद d(n) ({{OEIS2C|id=A096268}}) 2 विभाजक n की उच्चतम शक्ति के घातांक की समानता से निर्धारित होता है। यह आकृतिवाद 0 → 01, 1 → 00 का निश्चित बिंदु भी है।<ref name=AS176>Allouche & Shallit (2003) p.&nbsp;176</ref> प्रारंभिक शब्द w = 0 से प्रारम्भ करना और 2-समान आकारिकी φ को w पर पुनरावृत्त करना जहां φ(0) = 01 और φ(1) = 00, यह स्पष्ट है कि अवधि-दोहरीकरण अनुक्रम φ का निश्चित-बिंदु है ( डब्ल्यू) और इस प्रकार यह 2-स्वचालित है।


=== रुडिन-शापिरो अनुक्रम ===
=== रुडिन-शापिरो अनुक्रम ===
Line 74: Line 76:


=== अन्य अनुक्रम ===
=== अन्य अनुक्रम ===
बॉम-स्वीट सीक्वेंस दोनों<ref name=AS156>Allouche & Shallit (2003) p.&nbsp;156</ref> ({{OEIS2C|id=A086747}}) और [[नियमित पेपरफोल्डिंग अनुक्रम]]<ref name=BR92>Berstel & Reutenauer (2011) p.&nbsp;92</ref><ref name=AS155>Allouche & Shallit (2003) p.&nbsp;155</ref><ref name=LotIII526>Lothaire (2005) p.&nbsp;526</ref> ({{OEIS2C|id=A014577}}) स्वचालित हैं। इसके अलावा, फोल्ड के आवधिक अनुक्रम के साथ सामान्य पेपर फोल्डिंग अनुक्रम भी स्वचालित होता है।<ref name=AS183>Allouche & Shallit (2003) p.&nbsp;183</ref>
बॉम-स्वीट सीक्वेंस दोनों<ref name=AS156>Allouche & Shallit (2003) p.&nbsp;156</ref> ({{OEIS2C|id=A086747}}) और [[नियमित पेपरफोल्डिंग अनुक्रम]]<ref name=BR92>Berstel & Reutenauer (2011) p.&nbsp;92</ref><ref name=AS155>Allouche & Shallit (2003) p.&nbsp;155</ref><ref name=LotIII526>Lothaire (2005) p.&nbsp;526</ref> ({{OEIS2C|id=A014577}}) स्वचालित हैं। इसके अलावा, फोल्ड के आवधिक अनुक्रम के साथ सामान्य लेख फोल्डिंग अनुक्रम भी स्वचालित होता है।<ref name=AS183>Allouche & Shallit (2003) p.&nbsp;183</ref>




Line 91: Line 93:
एक उम्मीदवार अनुक्रम दिया <math>s = (s_n)_{n \ge 0}</math>, आमतौर पर इसकी स्वचालितता को साबित करने की तुलना में इसका खंडन करना आसान होता है। के-स्वचालित अनुक्रमों के के-कर्नेल लक्षण वर्णन द्वारा, यह के-कर्नेल में असीमित रूप से कई अलग-अलग तत्वों का उत्पादन करने के लिए पर्याप्त है <math>K_k(s)</math> उसे दिखाने के लिए <math>s</math> के-स्वचालित नहीं है। स्वाभाविक रूप से, कोई के-कर्नेल में शर्तों के समझौते की जाँच करके स्वचालितता साबित करने का प्रयास कर सकता है, लेकिन यह कभी-कभी गलत अनुमान लगा सकता है। उदाहरण के लिए, चलो
एक उम्मीदवार अनुक्रम दिया <math>s = (s_n)_{n \ge 0}</math>, आमतौर पर इसकी स्वचालितता को साबित करने की तुलना में इसका खंडन करना आसान होता है। के-स्वचालित अनुक्रमों के के-कर्नेल लक्षण वर्णन द्वारा, यह के-कर्नेल में असीमित रूप से कई अलग-अलग तत्वों का उत्पादन करने के लिए पर्याप्त है <math>K_k(s)</math> उसे दिखाने के लिए <math>s</math> के-स्वचालित नहीं है। स्वाभाविक रूप से, कोई के-कर्नेल में शर्तों के समझौते की जाँच करके स्वचालितता साबित करने का प्रयास कर सकता है, लेकिन यह कभी-कभी गलत अनुमान लगा सकता है। उदाहरण के लिए, चलो
:<math>t = 011010011\dots</math>
:<math>t = 011010011\dots</math>
थ्यू-मोर्स शब्द हो। होने देना <math>s</math> रन-लेंथ के क्रम में क्रमिक शब्दों को जोड़कर दिया गया शब्द हो <math>t</math>. तब <math>s</math> शुरू करना
थ्यू-मोर्स शब्द हो। होने देना <math>s</math> रन-लेंथ के क्रम में क्रमिक शब्दों को जोड़कर दिया गया शब्द हो <math>t</math>. तब <math>s</math> प्रारम्भ करना
:<math>s = 12112221\dots.</math>.
:<math>s = 12112221\dots.</math>.


Line 99: Line 101:
<math>s_{16n+1} = s_{64n+1} \text{ for } 0 \le n \le 1864134</math>
<math>s_{16n+1} = s_{64n+1} \text{ for } 0 \le n \le 1864134</math>
लेकिन के लिए नहीं <math>n = 1864135</math>.<ref>{{cite journal |last1=Allouche |first1=G. |last2=Allouche |first2=J.-P. |last3=Shallit |first3=J. |title=Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde |journal=Annales de l'Institut Fourier |date=2006 |volume=56 |issue=7 |page=2126|doi=10.5802/aif.2235 |url=http://www.numdam.org/item/AIF_2006__56_7_2115_0/ }}</ref>
लेकिन के लिए नहीं <math>n = 1864135</math>.<ref>{{cite journal |last1=Allouche |first1=G. |last2=Allouche |first2=J.-P. |last3=Shallit |first3=J. |title=Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde |journal=Annales de l'Institut Fourier |date=2006 |volume=56 |issue=7 |page=2126|doi=10.5802/aif.2235 |url=http://www.numdam.org/item/AIF_2006__56_7_2115_0/ }}</ref>
स्वचालित होने का अनुमान लगाने वाले अनुक्रम को देखते हुए, वास्तव में यह साबित करने के लिए कुछ उपयोगी दृष्टिकोण हैं। एक दृष्टिकोण सीधे आउटपुट के साथ एक नियतात्मक automaton का निर्माण करना है जो अनुक्रम देता है। होने देना <math>(s_n)_{n \ge 0}</math> वर्णमाला में लिखा है <math>\Delta</math>, और जाने <math>(n)_k</math> आधार को निरूपित करें-<math>k</math> का विस्तार <math>n</math>. फिर क्रम <math>s = (s_n)_{n \ge 0}</math> है <math>k</math>-स्वचालित अगर और केवल प्रत्येक फाइबर
स्वचालित होने का अनुमान लगाने वाले अनुक्रम को देखते हुए, वास्तव में यह साबित करने के लिए कुछ उपयोगी दृष्टिकोण हैं। एक दृष्टिकोण सीधे प्रक्षेपण के साथ एक नियतात्मक स्वचल प्ररूप का निर्माण करना है जो अनुक्रम देता है। होने देना <math>(s_n)_{n \ge 0}</math> वर्णमाला में लिखा है <math>\Delta</math>, और जाने <math>(n)_k</math> आधार को निरूपित करें-<math>k</math> का विस्तार <math>n</math>. फिर क्रम <math>s = (s_n)_{n \ge 0}</math> है <math>k</math>-स्वचालित अगर और केवल प्रत्येक फाइबर
:<math>I_k(s,d) := \{(n)_k \mid s_n = d\}</math>
:<math>I_k(s,d) := \{(n)_k \mid s_n = d\}</math>
नियमित भाषा है।<ref>Allouche and Shallit (2003) p. 160</ref> तंतुओं की नियमितता की जाँच अक्सर नियमित भाषाओं के लिए पम्पिंग लेम्मा का उपयोग करके की जा सकती है।
नियमित भाषा है।<ref>Allouche and Shallit (2003) p. 160</ref> तंतुओं की नियमितता की जाँच अक्सर नियमित भाषाओं के लिए पम्पिंग लेम्मा का उपयोग करके की जा सकती है।
Line 109: Line 111:


==1-स्वचालित अनुक्रम ==
==1-स्वचालित अनुक्रम ==
k-स्वचालित क्रम सामान्य रूप से केवल k ≥ 2 के लिए परिभाषित किए जाते हैं।<ref name=as1/>1-स्वचालित अनुक्रम को एक अनुक्रम के रूप में परिभाषित करके अवधारणा को k = 1 तक बढ़ाया जा सकता है जिसका n-वाँ पद n के लिए एकात्मक अंक प्रणाली पर निर्भर करता है; अर्थात्, (1)<sup>एन</sup>. चूंकि एक परिमित राज्य automaton अंततः पहले देखी गई स्थिति में वापस आना चाहिए, सभी 1-स्वचालित अनुक्रम अंततः आवधिक होते हैं।
k-स्वचालित क्रम सामान्य रूप से केवल k ≥ 2 के लिए परिभाषित किए जाते हैं।<ref name=as1/>1-स्वचालित अनुक्रम को एक अनुक्रम के रूप में परिभाषित करके अवधारणा को k = 1 तक बढ़ाया जा सकता है जिसका n-वाँ पद n के लिए एकात्मक अंक प्रणाली पर निर्भर करता है; अर्थात्, (1)<sup>एन</sup>. चूंकि एक परिमित राज्य स्वचल प्ररूप अंततः पहले देखी गई स्थिति में वापस आना चाहिए, सभी 1-स्वचालित अनुक्रम अंततः आवधिक होते हैं।


== सामान्यीकरण ==
== सामान्यीकरण ==
परिभाषा या इनपुट अनुक्रम में भिन्नता के खिलाफ स्वचालित अनुक्रम मजबूत होते हैं। उदाहरण के लिए, जैसा कि ऑटोमेटा-सैद्धांतिक परिभाषा में उल्लेख किया गया है, एक दिया गया अनुक्रम इनपुट अनुक्रम के प्रत्यक्ष और रिवर्स रीडिंग दोनों के तहत स्वचालित रहता है। जब अंकों के एक वैकल्पिक सेट का उपयोग किया जाता है या जब आधार को नकारा जाता है तो अनुक्रम भी स्वचालित रहता है; वह है, जब इनपुट अनुक्रम को आधार k के बजाय आधार -k में दर्शाया जाता है।<ref name=AS157>Allouche & Shallit (2003) p.&nbsp;157</ref> हालांकि, अंकों के वैकल्पिक सेट का उपयोग करने के विपरीत, आधार में परिवर्तन अनुक्रम की स्वचालितता को प्रभावित कर सकता है।
परिभाषा या निविष्ट अनुक्रम में भिन्नता के खिलाफ स्वचालित अनुक्रम मजबूत होते हैं। उदाहरण के लिए, जैसा कि स्वचल प्ररूप-सैद्धांतिक परिभाषा में उल्लेख किया गया है, एक दिया गया अनुक्रम निविष्ट अनुक्रम के प्रत्यक्ष और पंट पठन दोनों के तहत स्वचालित रहता है। जब अंकों के एक वैकल्पिक सम्मुच्चय का उपयोग किया जाता है या जब आधार को नकारा जाता है तो अनुक्रम भी स्वचालित रहता है; वह है, जब निविष्ट अनुक्रम को आधार k के बजाय आधार -k में दर्शाया जाता है।<ref name=AS157>Allouche & Shallit (2003) p.&nbsp;157</ref> हालांकि, अंकों के वैकल्पिक सम्मुच्चय का उपयोग करने के विपरीत, आधार में परिवर्तन अनुक्रम की स्वचालितता को प्रभावित कर सकता है।


स्वचालित अनुक्रम के डोमेन को दो तरफा स्वचालित अनुक्रमों के माध्यम से प्राकृतिक संख्याओं से पूर्णांक तक बढ़ाया जा सकता है। यह इस तथ्य से उपजा है कि, दिए गए k ≥ 2, प्रत्येक पूर्णांक को रूप में विशिष्ट रूप से दर्शाया जा सकता है <math> \sum_{0 \leq i \leq r} a_{i}(-k)^{i} , </math> कहाँ <math>a_{i} \in \{0, \dots, k-1\}</math>. फिर एक दो तरफा अनंत अनुक्रम a(n)<sub>''n''&nbsp;<math>\in \mathbb{Z}</math></sub> is (−k)-स्वचालित अगर और केवल अगर इसके बाद a(n)<sub>n ≥ 0</sub> और एक (−n)<sub>n ≥ 0</sub> के-स्वचालित हैं।<ref name=AS162>Allouche & Shallit (2003) p.&nbsp;162</ref>
स्वचालित अनुक्रम के डोमेन को दो तरफा स्वचालित अनुक्रमों के माध्यम से प्राकृतिक संख्याओं से पूर्णांक तक बढ़ाया जा सकता है। यह इस तथ्य से उपजा है कि, दिए गए k ≥ 2, प्रत्येक पूर्णांक को रूप में विशिष्ट रूप से दर्शाया जा सकता है <math> \sum_{0 \leq i \leq r} a_{i}(-k)^{i} , </math> कहाँ <math>a_{i} \in \{0, \dots, k-1\}</math>. फिर एक दो तरफा अनंत अनुक्रम a(n)<sub>''n''&nbsp;<math>\in \mathbb{Z}</math></sub> is (−k)-स्वचालित अगर और केवल अगर इसके बाद a(n)<sub>n ≥ 0</sub> और एक (−n)<sub>n ≥ 0</sub> के-स्वचालित हैं।<ref name=AS162>Allouche & Shallit (2003) p.&nbsp;162</ref>

Revision as of 19:30, 5 May 2023

गणित और सैद्धांतिक कंप्यूटर विज्ञान में, एक स्वचालित अनुक्रम (जिसे k-स्वचालित अनुक्रम या k-पहचानने योग्य अनुक्रम भी कहा जाता है, जब कोई यह इंगित करना चाहता है कि उपयोग किए गए अंकों का आधार k है ) एक परिमित स्वचल प्ररूप की विशेषता वाले शब्दों का एक अनंत क्रम है। एक स्वचालित अनुक्रम a(n) का n-वाँ शब्द अंतिम अवस्था का मानचित्रण है, जो कुछ में संख्या n के अंकों को स्वीकार करने वाले परिमित स्वचल प्ररूप में पहुंचा है। निश्चित मूलांक [1][2] एक स्वचालित सम्मुच्चय गैर-ऋणात्मक पूर्णांक S का एक सम्मुच्चय है, जिसके लिए इसकी विशेषता फलन χS के मानों का क्रम एक स्वचालित अनुक्रम है; अर्थात्, यदि χS(n) है तो S k-स्वचालित है, जहां χS(n) = 1 अगर n s और अन्यथा 0 है।[3][4]


परिभाषा

स्वचालित अनुक्रमों को कई तरीकों से परिभाषित किया जा सकता है, जो सभी समतुल्य हैं। चार सामान्य परिभाषाएँ इस प्रकार हैं।

स्वचल प्ररूप-सैद्धांतिक

मान लीजिए k एक धनात्मक पूर्णांक है, और मान लीजिए D = (Q, Σk, δ, q0, Δ, τ) प्रक्षेपण के साथ एक निर्धारक परिमित स्वचल प्ररूप बनें, जहां

  • q स्थिति का परिमित सम्मुच्चय (गणित) है;
  • निविष्ट वर्णमाला Σk मूलांक-के चिन्हांकन में संभावित अंकों के सम्मुच्चय {0,1,...,k-1} सम्मिलित हैं;
  • δ : q × Σk → q संक्रमण फलन है;
  • q0∈ q प्रारंभिक अवस्था है;
  • प्रक्षेपण वर्णक्रम Δ एक परिमित सम्मुच्चय है; और
  • τ : q → Δ आंतरिक स्थिति के सम्मुच्चय से प्रक्षेपण वर्णमाला में प्रक्षेपण फलन प्रतिचित्रण है।

एक श्रृंखला s1s2...st पर δ की क्रिया को परिभाषित करके फलन δ को एकल अंकों पर अभिनय से अंकों के तारों पर अभिनय करने तक बढ़ाएं। जैसे:

δ (q, S) = δ (δ (q, S1s2...St-1), St).

एक फलन को सकारात्मक पूर्णांक के सम्मुच्चय से प्रक्षेपण वर्णमाला Δ में निम्नानुसार परिभाषित करें:

a(n) = τ(δ(q0,s(n))),

जहाँ s(n) को आधार k में लिखा गया है। तब अनुक्रम a = a(1)a(2)a(3)... एक k-स्वचालित अनुक्रम है।[1]

सबसे महत्वपूर्ण अंक से प्रारम्भ होने वाले s(n) के आधार k अंकों को पढ़ने वाला स्वचल प्ररूप प्रत्यक्ष पठन कहा जाता है, जबकि कम से कम महत्वपूर्ण अंक से प्रारम्भ होने वाला स्वचल प्ररूप पंट पठन है। [4] उपरोक्त परिभाषा यह मानती है कि s(n) प्रत्यक्ष या विपरीत पठन है या नहीं है।[5]


प्रतिस्थापन

मान लीजिए मुक्त मोनॉइड का k-समान आकारिकी है और एक कूटलेखन हो (यानी, a -समान रूपवाद), जैसा कि स्वचल प्ररूप-सैद्धांतिक स्तिथि में है। यदि का एक निश्चित बिंदु है - अर्थात, यदि तो एक k-स्वचालित क्रम है। [6] इसके विपरीत, प्रत्येक k-स्वचालित अनुक्रम इस तरह से प्राप्य है। [4] यह परिणाम एलन कोभम (गणितज्ञ) के कारण है, और इसे साहित्य में कोभम की छोटी प्रमेय के रूप में संदर्भित किया जाता है।[2][7]


के-कर्नेल

मान लीजिए k ≥ 2 है। अनुक्रम s(n) का k-कर्नेल अनुगामी का समुच्चय है

अधिकतर स्तिथियों में, अनुक्रम का k-कर्नेल अनंत है। हालाँकि, यदि k-कर्नेल परिमित है, तो अनुक्रम s(n) k-स्वचालित है, और इसका विलोम भी सत्य है। यह ईलेनबर्ग के कारण है।[8][9][10]

यह इस प्रकार है कि एक k-स्वचालित अनुक्रम आवश्यक रूप से एक परिमित वर्णमाला पर एक अनुक्रम है।

औपचारिक शक्ति श्रृंखला

मान लीजिए u(n) एक वर्णमाला Σ पर अनुक्रम है और मान लें कि Σ से सीमित क्षेत्र Fq तक एक अंतःक्षेपक फलन β है, जहां कुछ अभाज्य p के लिए q = pn है। संबंधित औपचारिक शक्ति श्रृंखला निम्न है

तब अनुक्रम u q-स्वचालित है यदि और केवल यदि यह औपचारिक शक्ति श्रृंखला Fq(X) पर बीजगणितीय कार्य है। यह परिणाम क्रिस्टोल के कारण है, और इसे साहित्य में क्रिस्टोल के प्रमेय के रूप में जाना जाता है।[11]


इतिहास

1960 में जूलियस रिचर्ड बुची द्वारा स्वचालित अनुक्रम प्रस्तुत किए गए,[12] हालांकि उनके लेख ने इस स्तिथि में अधिक तार्किक-सैद्धांतिक दृष्टिकोण अपनाया और इस लेख में पाई जाने वाली शब्दावली का उपयोग नहीं किया। 1972 में कोभम द्वारा स्वचालित अनुक्रमों की धारणा का और अध्ययन किया गया, जिन्होंने इन अनुक्रमों को एकसमान टैग प्रणाली कहा था।[7]

स्वत: अनुक्रम शब्द पहली बार देशोइलर्स के एक लेख में दिखाई दिया।[13]


उदाहरण

निम्नलिखित क्रम स्वचालित हैं:

थू-मोर्स क्रम

File:ThueMorseAutomaton.png
डीएफएओ थू-मोर्स अनुक्रम उत्पन्न करता है

थू-मोर्स अनुक्रम टी(एन) (OEISA010060) रूपवाद 0 → 01, 1 → 10 का निश्चित बिंदु (गणित) है। चूंकि थ्यू-मोर्स अनुक्रम का n-वाँ पद n के आधार-2 प्रतिनिधित्व में मोडुलो ऑपरेशन 2 की संख्या की गणना करता है, यह यहाँ चित्रित प्रक्षेपण के साथ दो-राज्य नियतात्मक परिमित स्वचल प्ररूप द्वारा उत्पन्न होता है, जहाँ राज्य q में होता है0 इंगित करता है कि n के प्रतिनिधित्व में और राज्य q में होने की संख्या भी है1 इंगित करता है कि विषम संख्याएँ हैं।

इसलिए, थ्यू-मोर्स अनुक्रम 2-स्वचालित है।

अवधि-दोहरीकरण अनुक्रम

अवधि-दोहरीकरण अनुक्रम का n-वाँ पद d(n) (OEISA096268) 2 विभाजक n की उच्चतम शक्ति के घातांक की समानता से निर्धारित होता है। यह आकृतिवाद 0 → 01, 1 → 00 का निश्चित बिंदु भी है।[14] प्रारंभिक शब्द w = 0 से प्रारम्भ करना और 2-समान आकारिकी φ को w पर पुनरावृत्त करना जहां φ(0) = 01 और φ(1) = 00, यह स्पष्ट है कि अवधि-दोहरीकरण अनुक्रम φ का निश्चित-बिंदु है ( डब्ल्यू) और इस प्रकार यह 2-स्वचालित है।

रुडिन-शापिरो अनुक्रम

रुडिन-शापिरो अनुक्रम का n-वाँ पद r(n) (OEISA020985) n के आधार-2 प्रतिनिधित्व में लगातार लोगों की संख्या से निर्धारित होता है। रुडिन-शापिरो अनुक्रम का 2-कर्नेल[15] है

चूँकि 2-कर्नेल में केवल r(n), r(2n + 1), r(4n + 3), और r(8n + 3) होते हैं, यह परिमित है और इस प्रकार रुडिन-शापिरो अनुक्रम 2-स्वचालित है।

अन्य अनुक्रम

बॉम-स्वीट सीक्वेंस दोनों[16] (OEISA086747) और नियमित पेपरफोल्डिंग अनुक्रम[17][18][19] (OEISA014577) स्वचालित हैं। इसके अलावा, फोल्ड के आवधिक अनुक्रम के साथ सामान्य लेख फोल्डिंग अनुक्रम भी स्वचालित होता है।[20]


गुण

स्वचालित अनुक्रम कई दिलचस्प गुण प्रदर्शित करते हैं। इन संपत्तियों की एक गैर-संपूर्ण सूची नीचे प्रस्तुत की गई है।

  • प्रत्येक स्वचालित अनुक्रम एक रूपात्मक शब्द है।[21]
  • k ≥ 2 और r ≥ 1 के लिए, एक अनुक्रम k-स्वचालित होता है यदि और केवल यदि यह k हैआर-स्वचालित। यह परिणाम ईलेनबर्ग के कारण है।[22]
  • एच और के गुणक स्वतंत्रता के लिए, एक अनुक्रम एच-स्वचालित और के-स्वचालित दोनों होता है यदि और केवल यदि यह अंततः आवधिक होता है।[23] यह परिणाम Cobham के कारण है जिसे Cobham's theorem के नाम से भी जाना जाता है,[24] सेमेनोव के कारण बहुआयामी सामान्यीकरण के साथ।[25][26]
  • यदि यू(एन) एक वर्णमाला Σ पर एक के-स्वचालित अनुक्रम है और एफ Σ से एक समान आकारिकी है दूसरे अक्षर Δ में, तो f(u) Δ पर एक k-स्वचालित अनुक्रम है।[27]
  • यदि यू(एन) एक के-स्वचालित अनुक्रम है, तो अनुक्रम यू(केएन) और यू (केn − 1) अंततः आवधिक हैं।[28] इसके विपरीत, यदि यू(एन) एक अंततः आवधिक अनुक्रम है, तो अनुक्रम वी वी(के) द्वारा परिभाषित किया गया हैn) = u(n) और अन्यथा शून्य k-स्वचालित है।[29]


स्वचलितता को सिद्ध और अस्वीकृत करना

एक उम्मीदवार अनुक्रम दिया , आमतौर पर इसकी स्वचालितता को साबित करने की तुलना में इसका खंडन करना आसान होता है। के-स्वचालित अनुक्रमों के के-कर्नेल लक्षण वर्णन द्वारा, यह के-कर्नेल में असीमित रूप से कई अलग-अलग तत्वों का उत्पादन करने के लिए पर्याप्त है उसे दिखाने के लिए के-स्वचालित नहीं है। स्वाभाविक रूप से, कोई के-कर्नेल में शर्तों के समझौते की जाँच करके स्वचालितता साबित करने का प्रयास कर सकता है, लेकिन यह कभी-कभी गलत अनुमान लगा सकता है। उदाहरण के लिए, चलो

थ्यू-मोर्स शब्द हो। होने देना रन-लेंथ के क्रम में क्रमिक शब्दों को जोड़कर दिया गया शब्द हो . तब प्रारम्भ करना

.

ह ज्ञात है कि नियत बिन्दु है रूपवाद का

शब्द 2-स्वचालित नहीं है, लेकिन इसके 2-कर्नेल के कुछ तत्व कई शर्तों के लिए सहमत हैं। उदाहरण के लिए, लेकिन के लिए नहीं .[30] स्वचालित होने का अनुमान लगाने वाले अनुक्रम को देखते हुए, वास्तव में यह साबित करने के लिए कुछ उपयोगी दृष्टिकोण हैं। एक दृष्टिकोण सीधे प्रक्षेपण के साथ एक नियतात्मक स्वचल प्ररूप का निर्माण करना है जो अनुक्रम देता है। होने देना वर्णमाला में लिखा है , और जाने आधार को निरूपित करें- का विस्तार . फिर क्रम है -स्वचालित अगर और केवल प्रत्येक फाइबर

नियमित भाषा है।[31] तंतुओं की नियमितता की जाँच अक्सर नियमित भाषाओं के लिए पम्पिंग लेम्मा का उपयोग करके की जा सकती है।

अगर आधार में अंकों के योग को दर्शाता है- का विस्तार और गैर-ऋणात्मक पूर्णांक गुणांक वाला एक बहुपद है, और यदि , पूर्णांक हैं, तो क्रम

है -स्वचालित अगर और केवल अगर या .[32]


1-स्वचालित अनुक्रम

k-स्वचालित क्रम सामान्य रूप से केवल k ≥ 2 के लिए परिभाषित किए जाते हैं।[1]1-स्वचालित अनुक्रम को एक अनुक्रम के रूप में परिभाषित करके अवधारणा को k = 1 तक बढ़ाया जा सकता है जिसका n-वाँ पद n के लिए एकात्मक अंक प्रणाली पर निर्भर करता है; अर्थात्, (1)एन. चूंकि एक परिमित राज्य स्वचल प्ररूप अंततः पहले देखी गई स्थिति में वापस आना चाहिए, सभी 1-स्वचालित अनुक्रम अंततः आवधिक होते हैं।

सामान्यीकरण

परिभाषा या निविष्ट अनुक्रम में भिन्नता के खिलाफ स्वचालित अनुक्रम मजबूत होते हैं। उदाहरण के लिए, जैसा कि स्वचल प्ररूप-सैद्धांतिक परिभाषा में उल्लेख किया गया है, एक दिया गया अनुक्रम निविष्ट अनुक्रम के प्रत्यक्ष और पंट पठन दोनों के तहत स्वचालित रहता है। जब अंकों के एक वैकल्पिक सम्मुच्चय का उपयोग किया जाता है या जब आधार को नकारा जाता है तो अनुक्रम भी स्वचालित रहता है; वह है, जब निविष्ट अनुक्रम को आधार k के बजाय आधार -k में दर्शाया जाता है।[33] हालांकि, अंकों के वैकल्पिक सम्मुच्चय का उपयोग करने के विपरीत, आधार में परिवर्तन अनुक्रम की स्वचालितता को प्रभावित कर सकता है।

स्वचालित अनुक्रम के डोमेन को दो तरफा स्वचालित अनुक्रमों के माध्यम से प्राकृतिक संख्याओं से पूर्णांक तक बढ़ाया जा सकता है। यह इस तथ्य से उपजा है कि, दिए गए k ≥ 2, प्रत्येक पूर्णांक को रूप में विशिष्ट रूप से दर्शाया जा सकता है कहाँ . फिर एक दो तरफा अनंत अनुक्रम a(n)n  is (−k)-स्वचालित अगर और केवल अगर इसके बाद a(n)n ≥ 0 और एक (−n)n ≥ 0 के-स्वचालित हैं।[34] के-स्वचालित अनुक्रम के वर्णमाला को के-नियमित अनुक्रम | के-नियमित अनुक्रमों के माध्यम से परिमित आकार से अनंत आकार तक बढ़ाया जा सकता है।[35] के-नियमित अनुक्रमों को उन अनुक्रमों के रूप में वर्णित किया जा सकता है जिनके के-कर्नेल सूक्ष्म रूप से उत्पन्न होते हैं। प्रत्येक घिरा हुआ के-नियमित अनुक्रम स्वचालित है।[36]


तार्किक दृष्टिकोण

कई 2-स्वचालित अनुक्रमों के लिए , वो नक्शा संपत्ति है कि प्रथम-क्रम सिद्धांत निर्णायकता (तर्क) है। चूंकि स्वचालित अनुक्रमों के कई गैर-तुच्छ गुणों को प्रथम-क्रम तर्क में लिखा जा सकता है, इसलिए इन गुणों को यांत्रिक रूप से निर्णय प्रक्रिया को निष्पादित करके सिद्ध करना संभव है।[37] उदाहरण के लिए, थ्यू-मोर्स शब्द के निम्नलिखित गुणों को यांत्रिक रूप से इस तरह से सत्यापित किया जा सकता है:

  • थू-मोर्स शब्द ओवरलैप-फ्री है, यानी इसमें फॉर्म का कोई शब्द नहीं है कहाँ एक अक्षर है और संभवतः खाली शब्द है।
  • एक गैर-खाली शब्द अगर कोई गैर-खाली शब्द है तो सीमाबद्ध है और संभवतः खाली शब्द साथ . थ्यू-मोर्स शब्द में 1 से अधिक प्रत्येक लंबाई के लिए सीमाबद्ध कारक होता है।[38]
  • लंबाई का एक असंबद्ध कारक है थ्यू-मोर्स शब्द में अगर और केवल अगर कहाँ के द्विआधारी प्रतिनिधित्व को दर्शाता है .[39]

सॉफ्टवेयर अखरोट,[40][41] Hamoon Mousavi द्वारा विकसित, कुछ स्वचालित शब्दों के कई गुणों को तय करने के लिए एक निर्णय प्रक्रिया को लागू करता है, जैसे कि थ्यू-मोर्स शब्द। यह कार्यान्वयन स्वचालित अनुक्रमों के तार्किक दृष्टिकोण पर उपरोक्त कार्य का परिणाम है।

यह भी देखें

  • अंकगणित पुस्तक

टिप्पणियाँ

  1. 1.0 1.1 1.2 Allouche & Shallit (2003) p. 152
  2. 2.0 2.1 Berstel et al (2009) p. 78
  3. Allouche & Shallit (2003) p. 168
  4. 4.0 4.1 4.2 Pytheas Fogg (2002) p. 13
  5. Pytheas Fogg (2002) p. 15
  6. Allouche & Shallit (2003) p. 175
  7. 7.0 7.1 Cobham (1972)
  8. Allouche & Shallit (2003) p. 185
  9. Lothaire (2005) p. 527
  10. Berstel & Reutenauer (2011) p. 91
  11. Christol, G. (1979). "Ensembles presque périodiques k-reconnaissables". Theoret. Comput. Sci. 9: 141–145. doi:10.1016/0304-3975(79)90011-2.
  12. Büchi, J. R. (1960). "Weak second-order arithmetic and finite automata". The Collected Works of J. Richard Büchi. pp. 66–92. doi:10.1007/978-1-4613-8928-6_22. ISBN 978-1-4613-8930-9. {{cite book}}: |journal= ignored (help)
  13. Deshouillers, J.-M. (1979–1980). "La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini". Séminaire de Théorie des Nombres de Bordeaux: 5.01–5.22.
  14. Allouche & Shallit (2003) p. 176
  15. Allouche & Shallit (2003) p. 186
  16. Allouche & Shallit (2003) p. 156
  17. Berstel & Reutenauer (2011) p. 92
  18. Allouche & Shallit (2003) p. 155
  19. Lothaire (2005) p. 526
  20. Allouche & Shallit (2003) p. 183
  21. Lothaire (2005) p. 524
  22. Eilenberg, Samuel (1974). ऑटोमेटा, भाषाएं और मशीनें. Vol. A. Orlando: Academic Press. ISBN 978-0-122-34001-7.
  23. Allouche & Shallit (2003) pp. 345–350
  24. Cobham, A. (1969). "परिमित ऑटोमेटा द्वारा पहचानने योग्य संख्याओं के सेट के आधार-निर्भरता पर". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527. S2CID 19792434.
  25. Semenov, A. L. (1977). "दो संख्या प्रणालियों में नियमित रूप से विधेय की प्रेस्बर्गरनेस". Sibirsk. Mat. Zh. (in Russian). 18: 403–418.{{cite journal}}: CS1 maint: unrecognized language (link)
  26. Point, F.; Bruyère, V. (1997). "कोभम-सेमेनोव प्रमेय पर". Theory of Computing Systems. 30 (2): 197–220. doi:10.1007/BF02679449. S2CID 31270341.
  27. Lothaire (2005) p. 532
  28. Lothaire (2005) p. 529
  29. Berstel & Reutenauer (2011) p. 103
  30. Allouche, G.; Allouche, J.-P.; Shallit, J. (2006). "Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde". Annales de l'Institut Fourier. 56 (7): 2126. doi:10.5802/aif.2235.
  31. Allouche and Shallit (2003) p. 160
  32. Allouche and Shallit (2003) p. 197
  33. Allouche & Shallit (2003) p. 157
  34. Allouche & Shallit (2003) p. 162
  35. Allouche, J.-P.; Shallit, J. (1992). "के की अंगूठी - नियमित क्रम". Theoret. Comput. Sci. 98 (2): 163–197. doi:10.1016/0304-3975(92)90001-v.
  36. Shallit, Jeffrey. "The Logical Approach to Automatic Sequences, Part 1: Automatic Sequences and k-Regular Sequences" (PDF). Retrieved April 1, 2020.
  37. Shallit, J. "The Logical Approach to Automatic Sequences: Part 1" (PDF). Retrieved April 1, 2020.
  38. Shallit, J. "The Logical Approach to Automatic Sequences: Part 3" (PDF). Retrieved April 1, 2020.
  39. Shallit, J. "The Logical Approach to Automatic Sequences: Part 3" (PDF). Retrieved April 1, 2020.
  40. Shallit, J. "अखरोट सॉफ्टवेयर।". Retrieved April 1, 2020.
  41. Mousavi, H. (2016). "अखरोट में स्वचालित प्रमेय साबित करना". arXiv:1603.06017 [cs.FL].


संदर्भ


अग्रिम पठन