ऑटोमेटा सिद्धांत: शब्दावली, और अनुप्रयोग

आज के तकनीकी युग में हार्डवेयर और सॉफ्टवेयर क्षेत्र दोनों में जबरदस्त विकास हुआ है। विकास के प्रमुख क्षेत्रों में से एक हार्डवेयर डिजाइन के तरीकों में देखा गया था। उसके साथ बढ़ती तकनीक हार्डवेयर की अवधारणा - सॉफ्टवेयर सह-डिजाइन को लागू करना संभव था। अलग-अलग तरीके विकसित किए जाते हैं, सॉफ्टवेयर का उपयोग करना एक पूरी तरह से डिजाइन और हार्डवेयर सिस्टम अनुकरण कर सकते हैं। ऐसे तरीकों में से एक है ऑटोमेटा थ्योरी। ऑटोमेटा सिद्धांत की शाखा है कंप्यूटर विज्ञान कंप्यूटिंग उपकरणों के सार मॉडल को डिजाइन करने से संबंधित है जो स्वचालित रूप से चरणों के पूर्वनिर्धारित अनुक्रम का पालन करते हैं। यह लेख ऑटोमेटा ट्यूटोरियल की संक्षिप्त जानकारी पर चर्चा करता है।

ऑटोमेटा थ्योरी क्या है?

ऑटोमेटा शब्द ग्रीक से लिया गया है, जिसका अर्थ है 'आत्म-अभिनय'। एक ऑटोमेटन मशीन का एक गणितीय मॉडल है। ऑटोमेटन में राज्य और संक्रमण शामिल हैं। जैसा कि इनपुट को ऑटोमेटन को दिया जाता है, यह संक्रमण फ़ंक्शन के आधार पर अगले राज्य में संक्रमण बनाता है। संक्रमण फ़ंक्शन के इनपुट वर्तमान स्थिति और हाल के प्रतीक हैं। यदि किसी ऑटोमेटन के पास राज्यों की एक सीमित संख्या है, तो इसे Finite Automata या के रूप में जाना जाता है परिमित अवस्था मशीन । परिमित ऑटोमेटा को 5-ट्यूपल (क्यू, are, are, qo, F) द्वारा दर्शाया जाता है।

कहा पे,

Q = राज्यों का समुच्चय।

∑ = प्रतीकों के परिमित सेट को ऑटोमेटा की वर्णमाला भी कहा जाता है।

δ = संक्रमण समारोह।

qo = इनपुट की प्रारंभिक स्थिति।

F = Q के अंतिम राज्यों का सेट।

ऑटोमेटा सिद्धांत की बुनियादी शब्दावली

ऑटोमेटा सिद्धांत की कुछ मूल शब्दावली हैं-

1 । वर्णमाला : ऑटोमेटा सिद्धांत में प्रतीकों के किसी भी परिमित सेट को वर्णमाला के रूप में जाना जाता है। लेटर द्वारा दर्शाए गए सेट के सेट {ए, बी, सी, डी, ई,} को अल्फाबेट सेट कहा जाता है, जबकि सेट 'ए', 'बी', 'सी', 'डी', 'ई' के अक्षरों को कहा जाता है प्रतीकों।

दो । तार : ऑटोमेटा में, एक स्ट्रिंग वर्णमाला सेट For से लिए गए प्रतीकों का एक परिमित अनुक्रम है, उदाहरण के लिए, स्ट्रिंग S = = adeaddadc 'वर्णमाला set∑ = {a, b, c, d, e,} पर मान्य है।

३ । स्ट्रिंग की लंबाई : स्ट्रिंग में मौजूद प्रतीकों की संख्या को स्ट्रिंग की लंबाई के रूप में जाना जाता है। स्ट्रिंग के लिए S = ‘adaada 'की लंबाई स्ट्रिंग है | S | = 6. यदि स्ट्रिंग की लंबाई 0 है, तो इसे रिक्त स्ट्रिंग कहा जाता है।

४ । क्लेन स्टार : यह प्रतीकों set के सेट पर एकरी संचालक है, जो सेट the पर सभी संभावित लंबाई के λ सहित सभी संभावित तारों के अनंत सेट देता है। इसका प्रतिनिधित्व किया। उदाहरण के लिए, सेट के लिए {= {c, d}, = * = {λ, c, d, cd, dc, cc, dd, ……}।

५ । क्लेन क्लोजर : यह λ को छोड़कर वर्णमाला सेट के सभी संभावित तारों का अनंत सेट है। इसके द्वारा निरूपित किया जाता है। सेट के लिए the = {a, d}, = + = {a, d, ad, da, aa, dd,… ..}।

६ । भाषा: हिन्दी : भाषा कुछ वर्णमाला सेट Alp के लिए क्लेन स्टार सेटो * का सबसेट है। भाषा परिमित या अनंत हो सकती है। उदाहरण के लिए यदि कोई भाषा the = {a, d} सेट पर लंबाई 2 के सभी संभावित तार लेती है, तो L = {aa, ad, da, dd}।

औपचारिक भाषा और ऑटोमेटा

ऑटोमेटा सिद्धांत में, औपचारिक भाषा स्ट्रिंग का एक सेट है, जहां प्रत्येक स्ट्रिंग है प्रतीकों से बना है परिमित वर्णमाला सेट से संबंधित है। आइए एक बिल्ली भाषा पर विचार करें, जिसमें नीचे के सेट से कोई तार हो सकता है ...
मेव!
मेव!
मेव्वा !! ……

बिल्ली भाषा के लिए वर्णमाला सेट Σ = {m, e, w,!} है। इस सेट को एक Finite State Automata Model-m के लिए उपयोग किया जाता है। तब मॉडल m की विशेषता औपचारिक भाषा द्वारा निरूपित की जाती है

एल (एम)
L (m) = {{mew! ', W meww!', Ew mewww ', ... ...}

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

नियतात्मक परिमित ऑटोमेटा

निर्धारक प्रकार के ऑटोमेटा में, जब एक इनपुट दिया जाता है, तो हम हमेशा यह निर्धारित कर सकते हैं कि संक्रमण किस राज्य में होगा। जैसा कि यह एक परिमित ऑटोमेटन है, इसे निर्धारक परिमित ऑटोमेटा कहा जाता है।

सचित्र प्रदर्शन

स्टेट डायग्राम डिक्टिनिस्ट फिनाइट ऑटोमेटा के ग्राफिकल प्रतिनिधित्व के लिए उपयोग किया जाने वाला डिग्राफ है। आइए एक उदाहरण से समझते हैं। नियतात्मक परिमित ऑटोमेटा होने दें ...
क्यू = {ए, बी, सी, डी}।
, = {0, 1}
= {a}
एफ = {डी} और संक्रमण कार्य हो

आलेखीय प्रतिनिधित्व सारणीबद्ध रूप

स्टेट डायग्राम

निर्धारक परिमित राज्य ऑटोमेटा का राज्य आरेख

राज्य के आरेख से

• राज्यों को वर्टिकल द्वारा दर्शाया जाता है।
• संक्रमण को इनपुट वर्णमाला के साथ लेबल किए गए चाप द्वारा दर्शाया जाता है।
• खाली सिंगल इनकमिंग आर्क प्रारंभिक अवस्था का प्रतिनिधित्व करता है।
• डबल सर्कल वाला राज्य अंतिम राज्य है।

गैर नियतात्मक परिमित ऑटोमेटा

ऑटोमेटा जहां दिए गए इनपुट के लिए आउटपुट स्थिति निर्धारित नहीं की जा सकती है, गैर-नियतात्मक ऑटोमेटा कहा जाता है। इसे गैर-नियतात्मक परिमित ऑटोमेटा भी कहा जाता है, क्योंकि इसमें राज्यों की संख्या कम है। गैर-नियतात्मक परिमित ऑटोमेटा का प्रतिनिधित्व 5 -टूपल के सेट के रूप में किया जाता है जहां (क्यू, Fin, Fin, qo, F)

क्यू = राज्यों का सीमित सेट।
∑ = वर्णमाला सेट।
δ = संक्रमण समारोह

कहां है : क्यूओ = पहली स्थिति।

सचित्र प्रदर्शन

गैर-नियतात्मक परिमित ऑटोमेटा को राज्य आरेख की मदद से दर्शाया जाता है। बता दें कि गैर-नियतात्मक परिमित ऑटोमेटा-

क्यू = {ए, बी, सी, डी}
, = {0,1}
qo = {a}
एफ = {डी}

संक्रमण हैं

आलेखीय प्रतिनिधित्व सारणीबद्ध रूप

स्टेट डायग्राम

गैर-नियतात्मक परिमित ऑटोमेटा के राज्य आरेख

ऑटोमेटा थ्योरी एप्लीकेशन

के अनुप्रयोग ऑटोमेटा सिद्धांत निम्नलिखित को शामिल कीजिए।

• अभिकलन, संकलक प्रस्तुतियों, AI, आदि के सिद्धांत के क्षेत्र में ऑटोमेटा सिद्धांत बहुत उपयोगी है।
• पाठ प्रसंस्करण संकलक और हार्डवेयर डिज़ाइन के लिए, परिमित ऑटोमेटा एक प्रमुख भूमिका निभाता है।
• एअर इंडिया और में अनुप्रयोगों के लिए प्रोग्रामिंग भाषा , प्रसंग-मुक्त व्याकरण बहुत उपयोगी है।
• जीव विज्ञान के क्षेत्र में, सेलुलर ऑटोमेटा उपयोगी हैं।
• परिमित क्षेत्रों के सिद्धांत में भी हम ऑटोमेटा के आवेदन को पा सकते हैं।

इस लेख में, हमने ऑटोमेटा सिद्धांत भाषाओं और अभिकलन का संक्षिप्त परिचय सीखा है। ऑटोमेटा प्रागैतिहासिक काल से आसपास रहा है। नई तकनीकों के आविष्कार से इस क्षेत्र में कई नए विकास देखने को मिलते हैं। आप किस प्रकार के ऑटोमेटा के साथ आए हैं?