ऑटोमेटा थ्योरी परिचय
ऑटोमेटा - यह क्या है?
"ऑटोमेटा" शब्द ग्रीक शब्द "ατμα "α" से लिया गया है जिसका अर्थ है "आत्म-अभिनय"। एक ऑटोमेटन (बहुवचन में ऑटोमेटा) एक अमूर्त स्व-चालित कंप्यूटिंग डिवाइस है जो स्वचालित रूप से संचालन के पूर्वनिर्धारित अनुक्रम का अनुसरण करता है।
राज्यों की एक परिमित संख्या के साथ एक ऑटोमेटन एक कहा जाता है Finite Automaton (एफए) या Finite State Machine (FSM)।
एक Finite Automaton की औपचारिक परिभाषा
एक ऑटोमेटन को 5-ट्यूपल (क्यू, represented, q, q 0 , F) द्वारा दर्शाया जा सकता है , जहां -
Q राज्यों का एक समुच्चय है।
∑ प्रतीकों का एक परिमित सेट है, जिसे कहा जाता है alphabet ऑटोमेटन का।
δ संक्रमण कार्य है।
q0वह प्रारंभिक अवस्था है जहां से किसी भी इनपुट को संसाधित किया जाता है (q 0 ) Q)।
F अंतिम स्थिति / Q (F। Q) के राज्यों का एक समूह है।
संबंधित शब्दावली
वर्णमाला
Definition - ए alphabet प्रतीकों के किसी भी सीमित सेट है।
Example - - = {ए, बी, सी, डी} एक है alphabet set जहाँ 'a', 'b', 'c', और 'd' हैं symbols।
तार
Definition - ए string ∑ से लिया गया प्रतीकों का एक परिमित क्रम है।
Example - 'कैबैड' वर्णमाला सेट valid = {a, b, c, d} पर एक वैध स्ट्रिंग है
एक स्ट्रिंग की लंबाई
Definition- यह एक स्ट्रिंग में मौजूद प्रतीकों की संख्या है। (द्वारा चिह्नित|S|)।
Examples -
य द S = 'कैबकैड'; | S | = 6
यदि - S | = 0, इसे कहा जाता है empty string (द्वारा चिह्नित λ या ε)
क्लेने स्टार
Definition - क्लेनी स्टार, ∑*, प्रतीकों या तारों के एक सेट पर एक अपर ऑपरेटर है, ∑, कि सभी संभव लंबाई के सभी संभव तार के अनंत सेट देता है ∑ समेत λ।
Representation- - * = ∑ 0 ∪ ∪ 1 ∑ ∪ 2। ……। जहां Σ पी लंबाई पी के सभी संभव तार का सेट है।
Example - अगर ∑ = {a, b}, = * = {λ, a, b, aa, ab, ba, bb, ……… ..}
क्लेन क्लोजर / प्लस
Definition - सेट ∑+ λ को छोड़कर सभी संभावित लंबाई के सभी संभावित तारों का अनंत सेट है।
Representation- - + = ∑ 1 ∪ ∪ 2 ∑ ∪ 3। ……।
∑ + = ∑ * - {λ}
Example- अगर ∑ = {a, b}, = + = {a, b, aa, ab, ba, bb,… …………}}
भाषा: हिन्दी
Definition- कुछ वर्णमाला के लिए एक भाषा ∑ * का सबसेट है। यह परिमित या अनंत हो सकता है।
Example - यदि भाषा लंबाई 2 के सभी संभव तारों को ∑ = {a, b} से ऊपर ले जाती है, तो L = {ab, aa, ba, bb}