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

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 5 users not shown)
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> के मानों का क्रम एक स्वचालित अनुक्रम है; अर्थात्, यदि χ<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/>
 


एक '''स्वचालित सम्मुच्चय''' गैर-ऋणात्मक पूर्णांक ''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 55: Line 54:
निम्नलिखित क्रम स्वचालित हैं:
निम्नलिखित क्रम स्वचालित हैं:


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


=== रुडिन-शापिरो अनुक्रम ===
=== रुडिन-शापिरो अनुक्रम ===
रुडिन-शापिरो अनुक्रम का n-वाँ पद r(n) ({{OEIS2C|id=A020985}}) n के आधार-2 प्रतिनिधित्व में लगातार लोगों की संख्या से निर्धारित होता है। रुडिन-शापिरो अनुक्रम का 2-कर्नेल<ref name=AS154>Allouche & Shallit (2003) p.&nbsp;186</ref> है
रुडिन-शापिरो अनुक्रम का n-वाँ पद r(n) ({{OEIS2C|id=A020985}}) n के आधार-2 प्रतिनिधित्व में क्रमागत लोगों की संख्या से निर्धारित होता है। रुडिन-शापिरो अनुक्रम का 2-कर्नेल<ref name=AS154>Allouche & Shallit (2003) p.&nbsp;186</ref> है
:<math>
:<math>
\begin{align}
\begin{align}
Line 76: Line 75:


=== अन्य अनुक्रम ===
=== अन्य अनुक्रम ===
बॉम-स्वीट सीक्वेंस दोनों<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 83: Line 82:


* प्रत्येक स्वचालित अनुक्रम एक रूपात्मक शब्द है।<ref name=LotIII524>Lothaire (2005) p.&nbsp;524</ref>
* प्रत्येक स्वचालित अनुक्रम एक रूपात्मक शब्द है।<ref name=LotIII524>Lothaire (2005) p.&nbsp;524</ref>
*k ≥ 2 और r ≥ 1 के लिए, एक अनुक्रम k-स्वचालित होता है यदि और केवल यदि यह k है<sup>आर</sup>-स्वचालित। यह परिणाम ईलेनबर्ग के कारण है।<ref>{{cite book | last=Eilenberg | first=Samuel | title=ऑटोमेटा, भाषाएं और मशीनें| volume=A | location=Orlando | publisher=[[Academic Press]] | year=1974 | isbn=978-0-122-34001-7 }}</ref>
*k ≥ 2 और r ≥ 1 के लिए, एक अनुक्रम k-स्वचालित होता है यदि और केवल यदि यह ''k<sup>r</sup>'' -स्वचालित है। यह परिणाम ईलेनबर्ग के कारण है। <ref>{{cite book | last=Eilenberg | first=Samuel | title=ऑटोमेटा, भाषाएं और मशीनें| volume=A | location=Orlando | publisher=[[Academic Press]] | year=1974 | isbn=978-0-122-34001-7 }}</ref>
*एच और के गुणक स्वतंत्रता के लिए, एक अनुक्रम एच-स्वचालित और के-स्वचालित दोनों होता है यदि और केवल यदि यह अंततः आवधिक होता है।<ref name=as345>Allouche & Shallit (2003) pp.&nbsp;345–350</ref> यह परिणाम Cobham के कारण है जिसे Cobham's theorem के नाम से भी जाना जाता है,<ref>{{cite journal | first=A. | last=Cobham | title=परिमित ऑटोमेटा द्वारा पहचानने योग्य संख्याओं के सेट के आधार-निर्भरता पर| journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 | s2cid=19792434 }}</ref> सेमेनोव के कारण बहुआयामी सामान्यीकरण के साथ।<ref>{{cite journal | first=A. L. | last=Semenov | title=दो संख्या प्रणालियों में नियमित रूप से विधेय की प्रेस्बर्गरनेस| language=Russian | journal=Sibirsk. Mat. Zh. | volume=18 | year=1977 | pages=403–418 }}</ref><ref>{{ cite journal | journal=Theory of Computing Systems | date=1997 | volume=30 | number=2 | pages=197–220 | title=कोभम-सेमेनोव प्रमेय पर| first1=F. | last1=Point | first2=V. | last2=Bruyère  | author2-link = Véronique Bruyère | doi=10.1007/BF02679449 | s2cid=31270341 }}</ref>
*h और k गुणक स्वतंत्रता के लिए, एक अनुक्रम h-स्वचालित और k-स्वचालित दोनों होता है यदि और केवल यदि यह अंततः आवधिक होता है। <ref name=as345>Allouche & Shallit (2003) pp.&nbsp;345–350</ref> यह परिणाम सेमेनोव के कारण बहुआयामी सामान्यीकरण के साथ कोभम के कारण है जिसे कोभम प्रमेय के नाम से भी जाना जाता है। <ref>{{cite journal | first=A. | last=Cobham | title=परिमित ऑटोमेटा द्वारा पहचानने योग्य संख्याओं के सेट के आधार-निर्भरता पर| journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 | s2cid=19792434 }}</ref><ref>{{cite journal | first=A. L. | last=Semenov | title=दो संख्या प्रणालियों में नियमित रूप से विधेय की प्रेस्बर्गरनेस| language=Russian | journal=Sibirsk. Mat. Zh. | volume=18 | year=1977 | pages=403–418 }}</ref><ref>{{ cite journal | journal=Theory of Computing Systems | date=1997 | volume=30 | number=2 | pages=197–220 | title=कोभम-सेमेनोव प्रमेय पर| first1=F. | last1=Point | first2=V. | last2=Bruyère  | author2-link = Véronique Bruyère | doi=10.1007/BF02679449 | s2cid=31270341 }}</ref>
*यदि यू(एन) एक वर्णमाला Σ पर एक के-स्वचालित अनुक्रम है और एफ Σ से एक समान आकारिकी है<sup>∗</sup> दूसरे अक्षर Δ में<sup>∗</sup>, तो f(u) Δ पर एक k-स्वचालित अनुक्रम है।<ref name=ApCoW532>Lothaire (2005) p.&nbsp;532</ref>
*यदि u(n) एक वर्णमाला Σ पर एक के-स्वचालित अनुक्रम है और f Σ से एक समान आकारिकी है<sup>∗</sup> दूसरे अक्षर Δ में<sup>∗</sup>, तो f(u) Δ पर एक k-स्वचालित अनुक्रम है।<ref name=ApCoW532>Lothaire (2005) p.&nbsp;532</ref>
*यदि यू(एन) एक के-स्वचालित अनुक्रम है, तो अनुक्रम यू(के<sup>एन</sup>) और यू (के<sup>n</sup> − 1) अंततः आवधिक हैं।<ref name=ApCoW529>Lothaire (2005) p.&nbsp;529</ref> इसके विपरीत, यदि यू(एन) एक अंततः आवधिक अनुक्रम है, तो अनुक्रम वी वी(के) द्वारा परिभाषित किया गया है<sup>n</sup>) = u(n) और अन्यथा शून्य k-स्वचालित है।<ref name=BR103>Berstel & Reutenauer (2011) p.&nbsp;103</ref>
*यदि u(n) एक k-स्वचालित अनुक्रम है, तो अनुक्रम u(k<sup>n</sup>) और u (k<sup>n</sup> − 1) अंततः आवधिक हैं। <ref name=ApCoW529>Lothaire (2005) p.&nbsp;529</ref> इसके विपरीत, यदि u(n) एक अंततः आवधिक अनुक्रम है, तो अनुक्रम v v(k<sup>n</sup>) = u(n) द्वारा परिभाषित किया गया है और अन्यथा शून्य k-स्वचालित है।<ref name=BR103>Berstel & Reutenauer (2011) p.&nbsp;103</ref>




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


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


ज्ञात है कि <math>s</math> नियत बिन्दु है <math>h^{\omega}(1)</math> रूपवाद का
यह ज्ञात है कि <math>s</math> रूपवाद का नियत बिन्दु <math>h^{\omega}(1)</math> है 
:<math>h(1) = 121, h(2) = 12221.</math>
:<math>h(1) = 121, h(2) = 12221.</math>
शब्द <math>s</math> 2-स्वचालित नहीं है, लेकिन इसके 2-कर्नेल के कुछ तत्व कई शर्तों के लिए सहमत हैं। उदाहरण के लिए,
शब्द <math>s</math> 2-स्वचालित नहीं है, लेकिन इसके 2-कर्नेल के कुछ तत्व कई परिस्तिथियों के लिए सहमत हैं। उदाहरण के लिए, <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>(s_n)_{n \ge 0}</math> वर्णमाला में <math>\Delta</math> लिखा है, और और मान लीजिए <math>(n)_k</math> n के आधार-k प्रसार को निरूपित करता है। तब अनुक्रम <math>s = (s_n)_{n \ge 0}</math> k-स्वचालित है यदि और केवल प्रत्येक तंतु
<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>(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> तंतुओं की नियमितता की जाँच प्रायः नियमित भाषाओं के लिए पंपन प्रमेयिका का उपयोग करके की जा सकती है।


अगर <math>s_k(n)</math> आधार में अंकों के योग को दर्शाता है-<math>k</math> का विस्तार <math>n</math> और <math>p(X)</math> गैर-ऋणात्मक पूर्णांक गुणांक वाला एक बहुपद है, और यदि <math>k \ge 2</math>, <math> m \ge 1</math> पूर्णांक हैं, तो क्रम
यदि <math>s_k(n)</math> आधार में अंकों के योग को दर्शाता है-<math>k</math> का विस्तार <math>n</math> और <math>p(X)</math> गैर-ऋणात्मक पूर्णांक गुणांक वाला एक बहुपद है, और यदि <math>k \ge 2</math>, <math> m \ge 1</math> पूर्णांक हैं, तो क्रम
:<math>(s_k(p(n)) \pmod{m})_{n \ge 0}</math>
:<math>(s_k(p(n)) \pmod{m})_{n \ge 0}</math>
है <math>k</math>-स्वचालित अगर और केवल अगर <math>\deg p \le 1</math> या <math>m \mid k-1</math>.<ref>Allouche and Shallit (2003) p. 197</ref>
<math>k</math>-स्वचालित है यदि और केवल यदि <math>\deg p \le 1</math> या <math>m \mid k-1</math>होता है। <ref>Allouche and Shallit (2003) p. 197</ref>




==1-स्वचालित अनुक्रम ==
==1-स्वचालित अनुक्रम ==
k-स्वचालित क्रम सामान्य रूप से केवल k ≥ 2 के लिए परिभाषित किए जाते हैं।<ref name=as1/>1-स्वचालित अनुक्रम को एक अनुक्रम के रूप में परिभाषित करके अवधारणा को k = 1 तक बढ़ाया जा सकता है जिसका n-वाँ पद n के लिए एकात्मक अंक प्रणाली पर निर्भर करता है; अर्थात्, (1)<sup>एन</sup>. चूंकि एक परिमित राज्य स्वचल प्ररूप अंततः पहले देखी गई स्थिति में वापस आना चाहिए, सभी 1-स्वचालित अनुक्रम अंततः आवधिक होते हैं।
k-स्वचालित क्रम सामान्य रूप से केवल k ≥ 2 के लिए परिभाषित किए जाते हैं। <ref name=as1/>1-स्वचालित अनुक्रम को एक अनुक्रम के रूप में परिभाषित करके अवधारणा को k = 1 तक बढ़ाया जा सकता है जिसका n-वाँ पद n के लिए एकात्मक अंक प्रणाली पर निर्भर करता है; अर्थात्, (1)<sup>n</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> (−k)-स्वचालित यदि और केवल यदि इसके बाद a(n)<sub>n ≥ 0</sub> और एक (−n)<sub>n ≥ 0</sub> k-स्वचालित हैं। <ref name=AS162>Allouche & Shallit (2003) p.&nbsp;162</ref> k-स्वचालित अनुक्रम के वर्णमाला को k-नियमित अनुक्रमों के माध्यम से परिमित आकार से अनंत आकार तक बढ़ाया जा सकता है।<ref>{{cite journal | last1 = Allouche | first1 = J.-P. | last2 = Shallit | first2 = J. | title = ''के'' की अंगूठी - नियमित क्रम| journal = Theoret. Comput. Sci. | volume = 98 | issue = 2 | year = 1992 | pages = 163–197 | doi=10.1016/0304-3975(92)90001-v| doi-access = free }}</ref> k-नियमित अनुक्रमों को उन अनुक्रमों के रूप में वर्णित किया जा सकता है जिनके k-कर्नेल सूक्ष्म रूप से उत्पन्न होते हैं। प्रत्येक परिबद्ध k-नियमित अनुक्रम स्वचालित है।<ref>{{cite web |last1=Shallit |first1=Jeffrey |title=The Logical Approach to Automatic Sequences, Part 1: Automatic Sequences and ''k''-Regular Sequences |url=https://cs.uwaterloo.ca/~shallit/Talks/linz1a.pdf |accessdate=April 1, 2020}}</ref>
के-स्वचालित अनुक्रम के वर्णमाला को के-नियमित अनुक्रम | के-नियमित अनुक्रमों के माध्यम से परिमित आकार से अनंत आकार तक बढ़ाया जा सकता है।<ref>{{cite journal | last1 = Allouche | first1 = J.-P. | last2 = Shallit | first2 = J. | title = ''के'' की अंगूठी - नियमित क्रम| journal = Theoret. Comput. Sci. | volume = 98 | issue = 2 | year = 1992 | pages = 163–197 | doi=10.1016/0304-3975(92)90001-v| doi-access = free }}</ref> के-नियमित अनुक्रमों को उन अनुक्रमों के रूप में वर्णित किया जा सकता है जिनके के-कर्नेल सूक्ष्म रूप से उत्पन्न होते हैं। प्रत्येक घिरा हुआ के-नियमित अनुक्रम स्वचालित है।<ref>{{cite web |last1=Shallit |first1=Jeffrey |title=The Logical Approach to Automatic Sequences, Part 1: Automatic Sequences and ''k''-Regular Sequences |url=https://cs.uwaterloo.ca/~shallit/Talks/linz1a.pdf |accessdate=April 1, 2020}}</ref>




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


कई 2-स्वचालित अनुक्रमों के लिए <math>s = (s_n)_{n \ge 0}</math>, वो नक्शा <math>n \mapsto s_n</math> संपत्ति है कि प्रथम-क्रम सिद्धांत <math>\text{FO}(\mathbb{N},+,0,1,n \mapsto s_n)</math> [[निर्णायकता (तर्क)]] है। चूंकि स्वचालित अनुक्रमों के कई गैर-तुच्छ गुणों को प्रथम-क्रम तर्क में लिखा जा सकता है, इसलिए इन गुणों को यांत्रिक रूप से निर्णय प्रक्रिया को निष्पादित करके सिद्ध करना संभव है।<ref>{{cite web |last1=Shallit |first1=J. |title=The Logical Approach to Automatic Sequences: Part 1 |url=https://cs.uwaterloo.ca/~shallit/Talks/linz1a.pdf |accessdate=April 1, 2020}}</ref>
कई 2-स्वचालित अनुक्रमों के लिए <math>s = (s_n)_{n \ge 0}</math>, वो मानचित्र <math>n \mapsto s_n</math> में वह गुण है जो प्रथम-क्रम सिद्धांत <math>\text{FO}(\mathbb{N},+,0,1,n \mapsto s_n)</math> [[निर्णायकता (तर्क)]] है। चूंकि स्वचालित अनुक्रमों के कई गैर-तुच्छ गुणों को प्रथम-क्रम तर्क में लिखा जा सकता है, इसलिए इन गुणों को यांत्रिक रूप से निर्णय प्रक्रिया को निष्पादित करके सिद्ध करना संभव है।<ref>{{cite web |last1=Shallit |first1=J. |title=The Logical Approach to Automatic Sequences: Part 1 |url=https://cs.uwaterloo.ca/~shallit/Talks/linz1a.pdf |accessdate=April 1, 2020}}</ref>  
उदाहरण के लिए, थ्यू-मोर्स शब्द के निम्नलिखित गुणों को यांत्रिक रूप से इस तरह से सत्यापित किया जा सकता है:
 
*थू-मोर्स शब्द ओवरलैप-फ्री है, यानी इसमें फॉर्म का कोई शब्द नहीं है <math>cxcxc</math> कहाँ <math>c</math> एक अक्षर है और <math>w</math> संभवतः खाली शब्द है।
उदाहरण के लिए, उभयज-मोर्स शब्द के निम्नलिखित गुणों को यांत्रिक रूप से इस तरह से सत्यापित किया जा सकता है:
* एक गैर-खाली शब्द <math>x</math> अगर कोई गैर-खाली शब्द है तो सीमाबद्ध है <math>w</math> और संभवतः खाली शब्द <math>y</math> साथ <math>x = wyw</math>. थ्यू-मोर्स शब्द में 1 से अधिक प्रत्येक लंबाई के लिए सीमाबद्ध कारक होता है।<ref>{{cite web |last1=Shallit |first1=J. |title=The Logical Approach to Automatic Sequences: Part 3 |url=https://cs.uwaterloo.ca/~shallit/Talks/linz3b.pdf |accessdate=April 1, 2020}}</ref>
*उभयज-मोर्स शब्द अतिव्यापन-मुक्त है, यानी इसमें <math>cxcxc</math> स्वरुप का कोई शब्द नहीं है, जहाँ <math>c</math> एक अक्षर है और <math>w</math> संभवतः खाली शब्द है।
*लंबाई का एक असंबद्ध कारक है <math>n</math> थ्यू-मोर्स शब्द में अगर और केवल अगर <math>(n)_2 \notin 1(01^*0)^*10^*1</math> कहाँ <math>(n)_2</math> के द्विआधारी प्रतिनिधित्व को दर्शाता है <math>n</math>.<ref>{{cite web |last1=Shallit |first1=J. |title=The Logical Approach to Automatic Sequences: Part 3 |url=https://cs.uwaterloo.ca/~shallit/Talks/linz3b.pdf |accessdate=April 1, 2020}}</ref>
* एक गैर-खाली शब्द <math>x</math> यदि कोई गैर-खाली शब्द है तो सीमाबद्ध <math>w</math> है और संभवतः खाली शब्द <math>y</math> साथ <math>x = wyw</math> है। उभयज-मोर्स शब्द में 1 से अधिक प्रत्येक लंबाई के लिए सीमाबद्ध कारक होता है।<ref>{{cite web |last1=Shallit |first1=J. |title=The Logical Approach to Automatic Sequences: Part 3 |url=https://cs.uwaterloo.ca/~shallit/Talks/linz3b.pdf |accessdate=April 1, 2020}}</ref>
सॉफ्टवेयर अखरोट,<ref>{{cite web |last1=Shallit |first1=J. |title=अखरोट सॉफ्टवेयर।|url=https://cs.uwaterloo.ca/~shallit/walnut.html |accessdate=April 1, 2020}}</ref><ref>{{cite arXiv |last1=Mousavi |first1=H. |title=अखरोट में स्वचालित प्रमेय साबित करना|year=2016 |class=cs.FL |eprint=1603.06017 }}</ref> Hamoon Mousavi द्वारा विकसित, कुछ स्वचालित शब्दों के कई गुणों को तय करने के लिए एक निर्णय प्रक्रिया को लागू करता है, जैसे कि थ्यू-मोर्स शब्द। यह कार्यान्वयन स्वचालित अनुक्रमों के तार्किक दृष्टिकोण पर उपरोक्त कार्य का परिणाम है।
*उभयज-मोर्स शब्द में लंबाई का एक असंबद्ध कारक <math>n</math> है  यदि और केवल यदि <math>(n)_2 \notin 1(01^*0)^*10^*1</math> जहाँ <math>(n)_2</math> के द्विआधारी प्रतिनिधित्व को <math>n</math> दर्शाता है। <ref>{{cite web |last1=Shallit |first1=J. |title=The Logical Approach to Automatic Sequences: Part 3 |url=https://cs.uwaterloo.ca/~shallit/Talks/linz3b.pdf |accessdate=April 1, 2020}}</ref>
सॉफ्टवेयर अखरोट,<ref>{{cite web |last1=Shallit |first1=J. |title=अखरोट सॉफ्टवेयर।|url=https://cs.uwaterloo.ca/~shallit/walnut.html |accessdate=April 1, 2020}}</ref><ref>{{cite arXiv |last1=Mousavi |first1=H. |title=अखरोट में स्वचालित प्रमेय साबित करना|year=2016 |class=cs.FL |eprint=1603.06017 }}</ref> हामून मौसवी द्वारा विकसित, कुछ स्वचालित शब्दों के कई गुणों को तय करने के लिए एक निर्णय प्रक्रिया को लागू करता है, जैसे कि उभयज-मोर्स शब्द। यह कार्यान्वयन स्वचालित अनुक्रमों के तार्किक दृष्टिकोण पर उपरोक्त कार्य का परिणाम है।


== यह भी देखें ==
== यह भी देखें ==
Line 137: Line 133:


==संदर्भ==
==संदर्भ==
*{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = [[Cambridge University Press]] | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
*{{cite book | last1 = Allouche | first1 = जीन-पॉल | last2 = Shallit | first2 = जेफरी | author2-link = जेफरी शालिट | isbn = 978-0-521-82332-6 | publisher = [[कैम्ब्रिज यूनिवर्सिटी प्रेस]] | title = स्वचालित अनुक्रम: सिद्धांत, अनुप्रयोग, सामान्यीकरण | year = 2003 | zbl=1086.11015 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=https://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=https://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }}
Line 151: Line 147:
*{{cite book | editor1-first=Dennis A. | editor1-last=Hejhal | editor1-link=Dennis Hejhal | editor2-last=Friedman | editor2-first=Joel | editor3-last=Gutzwiller | editor3-first=Martin C. | editor3-link=Martin Gutzwiller | editor4-last=Odlyzko | editor4-first=Andrew M. | editor4-link=Andrew Odlyzko | title=Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996 | series=The IMA volumes in mathematics and its applications | volume=109 | publisher=[[Springer-Verlag]] | year=1999 | isbn=978-0-387-98824-5 | last=Shallit | first=Jeffrey | author1-link=Jeffrey Shallit | chapter=Number theory and formal languages | pages=547–570 }}
*{{cite book | editor1-first=Dennis A. | editor1-last=Hejhal | editor1-link=Dennis Hejhal | editor2-last=Friedman | editor2-first=Joel | editor3-last=Gutzwiller | editor3-first=Martin C. | editor3-link=Martin Gutzwiller | editor4-last=Odlyzko | editor4-first=Andrew M. | editor4-link=Andrew Odlyzko | title=Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996 | series=The IMA volumes in mathematics and its applications | volume=109 | publisher=[[Springer-Verlag]] | year=1999 | isbn=978-0-387-98824-5 | last=Shallit | first=Jeffrey | author1-link=Jeffrey Shallit | chapter=Number theory and formal languages | pages=547–570 }}


{{DEFAULTSORT:Automatic Sequence}}[[Category: शब्दों पर कॉम्बिनेटरिक्स]] [[Category: ऑटोमेटा (गणना)]] [[Category: पूर्णांक अनुक्रम]]
{{DEFAULTSORT:Automatic Sequence}}
 
 


[[Category: Machine Translated Page]]
[[Category:CS1 maint]]
[[Category:Created On 01/05/2023]]
[[Category:Created On 01/05/2023|Automatic Sequence]]
[[Category:Machine Translated Page|Automatic Sequence]]
[[Category:Pages with broken file links|Automatic Sequence]]
[[Category:Pages with script errors|Automatic Sequence]]
[[Category:Templates Vigyan Ready|Automatic Sequence]]
[[Category:ऑटोमेटा (गणना)|Automatic Sequence]]
[[Category:पूर्णांक अनुक्रम|Automatic Sequence]]
[[Category:शब्दों पर कॉम्बिनेटरिक्स|Automatic Sequence]]

Latest revision as of 12:35, 7 November 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]


उदाहरण

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

उभयज-मोर्स क्रम

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

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

अवधि-दोहरीकरण अनुक्रम का n-वाँ पद d(n) (OEISA096268) 2 विभाजक n की उच्चतम शक्ति के घातांक की समानता से निर्धारित होता है। यह आकृतिवाद 0 → 01, 1 → 00 का निश्चित बिंदु भी है। [14] प्रारंभिक शब्द w = 0 से प्रारम्भ करना और 2-समान आकारिकी φ को w पर पुनरावृत्त करना जहां φ(0) = 01 और φ(1) = 00, यह स्पष्ट है कि अवधि-दोहरीकरण अनुक्रम φ का निश्चित-बिंदु है (w) और इस प्रकार यह 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-स्वचालित होता है यदि और केवल यदि यह kr -स्वचालित है। यह परिणाम ईलेनबर्ग के कारण है। [22]
  • h और k गुणक स्वतंत्रता के लिए, एक अनुक्रम h-स्वचालित और k-स्वचालित दोनों होता है यदि और केवल यदि यह अंततः आवधिक होता है। [23] यह परिणाम सेमेनोव के कारण बहुआयामी सामान्यीकरण के साथ कोभम के कारण है जिसे कोभम प्रमेय के नाम से भी जाना जाता है। [24][25][26]
  • यदि u(n) एक वर्णमाला Σ पर एक के-स्वचालित अनुक्रम है और f Σ से एक समान आकारिकी है दूसरे अक्षर Δ में, तो f(u) Δ पर एक k-स्वचालित अनुक्रम है।[27]
  • यदि u(n) एक k-स्वचालित अनुक्रम है, तो अनुक्रम u(kn) और u (kn − 1) अंततः आवधिक हैं। [28] इसके विपरीत, यदि u(n) एक अंततः आवधिक अनुक्रम है, तो अनुक्रम v v(kn) = u(n) द्वारा परिभाषित किया गया है और अन्यथा शून्य k-स्वचालित है।[29]


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

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

उभयज-मोर्स शब्द है। मान लीजिये, t की प्रवाह-लम्बाई के अनुक्रम में क्रमिक शब्दों को जोड़कर दिया गया शब्द है। तब प्रारम्भ होता है

.

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

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

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

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

-स्वचालित है यदि और केवल यदि या होता है। [32]


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

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

सामान्यीकरण

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

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


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

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

उदाहरण के लिए, उभयज-मोर्स शब्द के निम्नलिखित गुणों को यांत्रिक रूप से इस तरह से सत्यापित किया जा सकता है:

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

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

यह भी देखें

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

टिप्पणियाँ

  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].


संदर्भ


अग्रिम पठन