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

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

परिभाषा

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

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

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

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

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

δ (q, S) = δ (δ (q, S₁s₂...S_t-1), S_t).

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

a(n) = τ(δ(q₀,s(n))),

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

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

प्रतिस्थापन

मान लीजिए $\varphi$ मुक्त मोनॉइड $\Sigma ^{*}$ का k-समान आकारिकी है और $\tau$ एक कूटलेखन हो (यानी, a $1$-समान रूपवाद), जैसा कि स्वचल प्ररूप-सैद्धांतिक स्तिथि में है। यदि $w$ $\varphi$ का एक निश्चित बिंदु है - अर्थात, यदि $w=\varphi (w)$ तो $s=\tau (w)$ एक k-स्वचालित क्रम है। इसके विपरीत, प्रत्येक k-स्वचालित अनुक्रम इस तरह से प्राप्य है। यह परिणाम एलन कोभम (गणितज्ञ) के कारण है, और इसे साहित्य में कोभम की छोटी प्रमेय के रूप में संदर्भित किया जाता है।

के-कर्नेल

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

$K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.$

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

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

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

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

$\sum _{i\geq 0}\beta (u(i))X^{i}$

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

इतिहास

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

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

उदाहरण

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

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

File:ThueMorseAutomaton.png

डीएफएओ उभयज-मोर्स अनुक्रम उत्पन्न करता है

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

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

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

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

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

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

${\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}$

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

अन्य अनुक्रम

बॉम-स्वीट अनुक्रम दोनों (OEIS: A086747) और नियमित पेपरफोल्डिंग अनुक्रम (OEIS: A014577) स्वचालित हैं। इसके अतिरिक्त, वलय के आवधिक अनुक्रम के साथ सामान्य लेख फोल्डिंग अनुक्रम भी स्वचालित होता है।

गुण

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

• प्रत्येक स्वचालित अनुक्रम एक रूपात्मक शब्द है।
• k ≥ 2 और r ≥ 1 के लिए, एक अनुक्रम k-स्वचालित होता है यदि और केवल यदि यह k^r -स्वचालित है। यह परिणाम ईलेनबर्ग के कारण है।
• h और k गुणक स्वतंत्रता के लिए, एक अनुक्रम h-स्वचालित और k-स्वचालित दोनों होता है यदि और केवल यदि यह अंततः आवधिक होता है। यह परिणाम सेमेनोव के कारण बहुआयामी सामान्यीकरण के साथ कोभम के कारण है जिसे कोभम प्रमेय के नाम से भी जाना जाता है।
• यदि u(n) एक वर्णमाला Σ पर एक के-स्वचालित अनुक्रम है और f Σ से एक समान आकारिकी है^∗ दूसरे अक्षर Δ में^∗, तो f(u) Δ पर एक k-स्वचालित अनुक्रम है।
• यदि u(n) एक k-स्वचालित अनुक्रम है, तो अनुक्रम u(kⁿ) और u (kⁿ − 1) अंततः आवधिक हैं। इसके विपरीत, यदि u(n) एक अंततः आवधिक अनुक्रम है, तो अनुक्रम v v(kⁿ) = u(n) द्वारा परिभाषित किया गया है और अन्यथा शून्य k-स्वचालित है।

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

एक उम्मीदवार अनुक्रम $s=(s_{n})_{n\geq 0}$ दिया गया है, सामान्यतः इसकी स्वचालितता को सिद्ध करने की तुलना में इसका खंडन करना आसान होता है। k-स्वचालित अनुक्रमों के k-कर्नेल लक्षण वर्णन द्वारा, यह k-कर्नेल $K_{k}(s)$ में असीमित रूप से कई अलग-अलग तत्वों का उत्पादन करने के लिए पर्याप्त है उसे दिखाने के लिए $s$ k-स्वचालित नहीं है। स्वाभाविक रूप से, कोई k-कर्नेल में स्तिथियों के समझौते की जाँच करके स्वचालितता सिद्ध करने का प्रयास कर सकता है, लेकिन यह कभी-कभी गलत अनुमान लगा सकता है। उदाहरण के लिए, मान लीजिये

$t=011010011\dots$

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

$s=12112221\dots .$.

यह ज्ञात है कि $s$ रूपवाद का नियत बिन्दु $h^{\omega }(1)$ है

$h(1)=121,h(2)=12221.$

शब्द $s$ 2-स्वचालित नहीं है, लेकिन इसके 2-कर्नेल के कुछ तत्व कई परिस्तिथियों के लिए सहमत हैं। उदाहरण के लिए, $s_{16n+1}=s_{64n+1}{\text{ for }}0\leq n\leq 1864134$ लेकिन $n=1864135$ के लिए नहीं है। स्वचालित होने का अनुमान लगाने वाले अनुक्रम को देखते हुए, वास्तव में यह सिद्ध करने के लिए कुछ उपयोगी दृष्टिकोण हैं। एक दृष्टिकोण सीधे प्रक्षेपण के साथ एक नियतात्मक स्वचल प्ररूप का निर्माण करना है जो अनुक्रम देता है। मान लीजिये $(s_{n})_{n\geq 0}$ वर्णमाला में $\Delta$ लिखा है, और और मान लीजिए $(n)_{k}$ n के आधार-k प्रसार को निरूपित करता है। तब अनुक्रम $s=(s_{n})_{n\geq 0}$ k-स्वचालित है यदि और केवल प्रत्येक तंतु

$I_{k}(s,d):=\{(n)_{k}\mid s_{n}=d\}$

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

यदि $s_{k}(n)$ आधार में अंकों के योग को दर्शाता है-$k$ का विस्तार $n$ और $p(X)$ गैर-ऋणात्मक पूर्णांक गुणांक वाला एक बहुपद है, और यदि $k\geq 2$, $m\geq 1$ पूर्णांक हैं, तो क्रम

$(s_{k}(p(n)){\pmod {m}})_{n\geq 0}$

$k$-स्वचालित है यदि और केवल यदि $\deg p\leq 1$ या $m\mid k-1$होता है।

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

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

सामान्यीकरण

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

स्वचालित अनुक्रम के कार्यक्षेत्र को दो तरफा स्वचालित अनुक्रमों के माध्यम से प्राकृतिक संख्याओं से पूर्णांक तक बढ़ाया जा सकता है। यह इस तथ्य से उपजा है कि, दिए गए k ≥ 2, प्रत्येक पूर्णांक को $\sum _{0\leq i\leq r}a_{i}(-k)^{i},$ रूप में विशिष्ट रूप से दर्शाया जा सकता है जहाँ $a_{i}\in \{0,\dots ,k-1\}$ है। फिर एक दो तरफा अनंत अनुक्रम a(n)_{n $\in \mathbb {Z}$} (−k)-स्वचालित यदि और केवल यदि इसके बाद a(n)_{n ≥ 0} और एक (−n)_{n ≥ 0} k-स्वचालित हैं। k-स्वचालित अनुक्रम के वर्णमाला को k-नियमित अनुक्रमों के माध्यम से परिमित आकार से अनंत आकार तक बढ़ाया जा सकता है। k-नियमित अनुक्रमों को उन अनुक्रमों के रूप में वर्णित किया जा सकता है जिनके k-कर्नेल सूक्ष्म रूप से उत्पन्न होते हैं। प्रत्येक परिबद्ध k-नियमित अनुक्रम स्वचालित है।

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

कई 2-स्वचालित अनुक्रमों के लिए $s=(s_{n})_{n\geq 0}$, वो मानचित्र $n\mapsto s_{n}$ में वह गुण है जो प्रथम-क्रम सिद्धांत ${\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})$ निर्णायकता (तर्क) है। चूंकि स्वचालित अनुक्रमों के कई गैर-तुच्छ गुणों को प्रथम-क्रम तर्क में लिखा जा सकता है, इसलिए इन गुणों को यांत्रिक रूप से निर्णय प्रक्रिया को निष्पादित करके सिद्ध करना संभव है।

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

• उभयज-मोर्स शब्द अतिव्यापन-मुक्त है, यानी इसमें $cxcxc$ स्वरुप का कोई शब्द नहीं है, जहाँ $c$ एक अक्षर है और $w$ संभवतः खाली शब्द है।
• एक गैर-खाली शब्द $x$ यदि कोई गैर-खाली शब्द है तो सीमाबद्ध $w$ है और संभवतः खाली शब्द $y$ साथ $x=wyw$ है। उभयज-मोर्स शब्द में 1 से अधिक प्रत्येक लंबाई के लिए सीमाबद्ध कारक होता है।
• उभयज-मोर्स शब्द में लंबाई का एक असंबद्ध कारक $n$ है यदि और केवल यदि $(n)_{2}\notin 1(01^{*}0)^{*}10^{*}1$ जहाँ $(n)_{2}$ के द्विआधारी प्रतिनिधित्व को $n$ दर्शाता है।

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

यह भी देखें

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

संदर्भ

• Allouche, जीन-पॉल; Shallit, जेफरी (2003). स्वचालित अनुक्रम: सिद्धांत, अनुप्रयोग, सामान्यीकरण. कैम्ब्रिज यूनिवर्सिटी प्रेस. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
• Cobham, Alan (1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2): 164–192. doi:10.1007/BF01706087. S2CID 28356747.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 978-0-521-84802-2. Zbl 1133.68067.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 978-3-540-44141-0. Zbl 1014.11015.

अग्रिम पठन

• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
• Loxton, J. H. (1988). "13. Automata and transcendence". In Baker, A. (ed.). New Advances in Transcendence Theory. Cambridge University Press. pp. 215–228. ISBN 978-0-521-33545-4. Zbl 0656.10032.
• Rowland, Eric (2015). "What is ... an automatic sequence?". Notices of the American Mathematical Society. 62 (3): 274–276. doi:10.1090/noti1218.
• Shallit, Jeffrey (1999). "Number theory and formal languages". In Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. (eds.). Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996. The IMA volumes in mathematics and its applications. Vol. 109. Springer-Verlag. pp. 547–570. ISBN 978-0-387-98824-5.