Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में L = {a(2*m)c(4*n)dnbm | m,n = 0} के लिए पुशडाउन ऑटोमेटा बनाना


हमें एक भाषा "L" दी गई है और कार्य दिए गए भाषा के लिए एक पुशडाउन ऑटोमेटा बनाना है जो बताता है कि वर्ण 'a' की घटनाएं वर्ण 'b' की घटनाओं से दोगुनी होनी चाहिए और वर्ण 'c' की घटनाएं 'd' से चौगुनी होनी चाहिए और सभी वर्णों की घटनाएं न्यूनतम 1 होनी चाहिए जो स्ट्रिंग को NULL भी बना सकती हैं और इसे ऑटोमेटा द्वारा स्वीकार किया जाना चाहिए।

पुशडाउन ऑटोमेटा क्या है?

एक पुशडाउन ऑटोमेटा या पुशडाउन ऑटोमेटन या PDA एक तकनीक है जिसका उपयोग संदर्भ-मुक्त व्याकरण को लागू करने के लिए किया जाता है, उसी तरह जैसे हम नियमित व्याकरण के लिए डिटरमिनिस्टिक फाइनाइट ऑटोमेटन या DFA डिज़ाइन करते हैं। एक DFA परिमित डेटा पर काम कर सकता है, लेकिन एक PDA अनंत डेटा पर काम कर सकता है। हम पुशडाउन ऑटोमेटा को "फाइनाइट स्टेट मशीन" और एक "स्टैक" के संयोजन के रूप में समझ सकते हैं।

एक पुशडाउन ऑटोमेटन के तीन घटक होते हैं:

  • एक इनपुट टेप,

  • एक कंट्रोल यूनिट, और

  • अनंत आकार का एक स्टैक।

एक PDA को औपचारिक रूप से 7-टपल (Q, Σ, S, δ, q0, I, F) के रूप में वर्णित किया जा सकता है:

  • Q अवस्थाओं की परिमित संख्या है

  • Σ इनपुट वर्णमाला है

  • S स्टैक प्रतीक हैं

  • δ संक्रमण फ़ंक्शन है: Q × (Σ ∪ {ε}) × S × Q × S*

  • q0 प्रारंभिक अवस्था है (q0 ∈ Q)

  • I प्रारंभिक स्टैक टॉप प्रतीक है (I ∈ S)

  • F स्वीकार करने वाली अवस्थाओं का समूह है (F ∈ Q)

आइए दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा बनाते हैं:

C++ में L = {a(2*m)c(4*n)dnbm | m,n = 0} के लिए पुशडाउन ऑटोमेटा बनाना

इस PDA द्वारा स्वीकार्य स्ट्रिंग्स निम्न रूप की हैं:

  • c4ndn - ccccd, ccccccccdd, आदि। cs की संख्या ds की संख्या से 4 गुना है। जब m 0 है तो हमारे पास कोई as और bs नहीं होंगे। cs को पुश करते रहें और जैसे ही पहला d मिले तो स्टैक से 4 c पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुंचते हैं और कोई c नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।

  • a2mbm - aab, aaaabb, आदि। as की संख्या bs की संख्या से 2 गुना है। जब n 0 है तो हमारे पास कोई cs और ds नहीं होंगे। as को पुश करते रहें और जैसे ही पहला b मिले तो स्टैक से 2 a पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुंचते हैं और कोई a नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।

  • a2mc4ndnbm - aaccccdb, aaaaccccccccddbb। as की संख्या bs की संख्या से 2 गुना है और cs ds की संख्या से 4 गुना बराबर है। as और cs को पुश करते रहें। जैसे ही पहला d मिले तो अगर शीर्ष पर c है तो 4 cs पॉप करें और फिर शेष bs के लिए 2 as पॉप करें। यदि हम अंत तक पहुंचते हैं और कोई a नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।

  • NULL स्ट्रिंग भी स्वीकार की जाती है। a0c0d0b0।

आइए मशीन को समझते हैं

  • अवस्था q0 के लिए संक्रमण:

    • ( a, I/a,I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक a है तो a को स्टैक के शीर्ष पर पुश करें और q0 पर रहें। स्टैक aI... बन जाता है।

    • ( c, I/c,I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक c है तो c को स्टैक के शीर्ष पर पुश करें और q0 पर रहें। स्टैक cI... बन जाता है।

    • ( a, a/a,a ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक भी a है तो a को स्टैक के शीर्ष पर पुश करें और q0 पर रहें। स्टैक aa.... बन जाता है। अगले c या b तक as को पुश करते रहें।

    • ( c, c/c,c ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक भी c है तो c को स्टैक के शीर्ष पर पुश करें और q0 पर रहें। स्टैक cc.... बन जाता है। अगले d तक cs को पुश करते रहें।

    • ( b, a/e,aa ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक b है तो स्टैक से 2 as पॉप करें और q3 पर जाएं।

    • (c, a/c,a ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक c है तो c को स्टैक के शीर्ष पर पुश करें और q1 पर जाएं। स्टैक ca... बन जाता है।

    • ( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q4 पर जाएं।

    • ( $, I/I, I) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और q5 पर जाएं। NULL स्ट्रिंग के लिए।

  • अवस्था q1 के लिए संक्रमण:

    • ( c, c/c,c ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक भी c है तो c को स्टैक के शीर्ष पर पुश करें और q1 पर रहें। स्टैक cc.... बन जाता है। अगले d तक cs को पुश करते रहें।

    • ( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q2 पर जाएं।

  • अवस्था q2 के लिए संक्रमण:

    • ( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q2 पर रहें।

    • ( b, a/e,aa ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक b है तो स्टैक से 2 as पॉप करें और q3 पर जाएं।

  • अवस्था q3 के लिए संक्रमण:

    • ( b, a/e,aa ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक b है तो स्टैक से 2 as पॉप करें और q3 पर रहें।

    • ( $, I/I, I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और q5 पर जाएं। NULL स्ट्रिंग के लिए।

  • अवस्था q4 के लिए संक्रमण:

    • ( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q4 पर रहें।

    • ( $, I/I, I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और q5 पर जाएं। NULL स्ट्रिंग के लिए।


  1. C++ में L = {an bm a(n+m) - n,m≥1} के लिए ट्यूरिंग मशीन का निर्माण C++ में L = {an bm a(n+m) - n,m≥1} के लिए ट्यूरिंग मशीन का निर्माण

    ट्यूरिंग मशीन: एक ट्यूरिंग मशीन टाइप 0 व्याकरण द्वारा उत्पन्न भाषा के शब्दों को स्वीकार करने के लिए उपयोग किया जाने वाला उपकरण है। एक ट्यूरिंग मशीन (TM) एक गणितीय मॉडल है जिसमें अनंत लंबाई का एक टेप होता है जिसे सेल में विभाजित किया जाता है जिस पर इनपुट दिया जाता है। इसमें एक हेड होता है जो इनपुट टे

  1. C++ STL में स्टैक (3.5) C++ STL में स्टैक (3.5)

    C++ STL में, स्टैक का उपयोग एक कंटेनर के रूप में किया जाता है जिसे LIFO संरचना के रूप में कार्यान्वित किया जाता है। LIFO का अर्थ है लास्ट इन फर्स्ट आउट। स्टैक को किताबों के ढेर के रूप में देखा जा सकता है जिसमें किताबें एक के ऊपर एक व्यवस्थित होती हैं और अंत में डाली गई किताब सबसे पहले हटाई जाएगी इसल

  1. C++ में DAG के लिए रैंडम लीनियर एक्सटेंशन बनाना C++ में DAG के लिए रैंडम लीनियर एक्सटेंशन बनाना

    यहां हम डायरेक्टेड एसाइक्लिक ग्राफ (DAG) के रैंडम लीनियर एक्सटेंशन बनाने का तरीका देखेंगे। लीनियर एक्सटेंशन मूल रूप से DAG की टोपोलॉजिकल सॉर्टिंग है। आइए मान लें कि ग्राफ नीचे जैसा है - डायरेक्टेड एसाइक्लिक ग्राफ के लिए टोपोलॉजिकल सॉर्टिंग वर्टेक्स की लीनियर ऑर्डरिंग है। डायरेक्टेड ग्राफ के प्रत्