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

Question

संयोजन मैं इस सामान के लिए वास्तव में नया हूं इसलिए मैं यहां नोबिशनेस के लिए क्षमा चाहता हूं।

निम्नलिखित भाषा पहचानने एक Deterministic Finite Automaton DFA का निर्माण: इस (at least 2 a's, odd # of b's) के प्रत्येक भाग के लिए

L= { w : w has at least two a's and an odd number of b's}. 

स्वचालित अलग से बनाने के लिए आसान कर रहे हैं ... किसी को भी उन्हें एक में गठबंधन करने के लिए एक व्यवस्थित तरीके से समझाने सकते हैं? धन्यवाद।

Answer 1

यह दो ऑटोमाटा के product का उपयोग करके किया गया है।

Answer 2

भाषा L जहां a कम से कम दो और b अजीब एक नियमित भाषा है। इसके DFA रूप में नीचे है:

इस DFA में मैं दो DFS रों धारणात्मक संयुक्त कर दिया है!

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram) 
DFA-2 = for >= two a   (placed Horizontally two times in diagram) 

_{DFA भी रोगसूचक और सरल है तो मैं शब्द है कि कैसे दोनों DFAs}

गठबंधन करने के लिए में कोई जरूरत नहीं मानते हैं कि यह DFA आप हमेशा ट्रैक रखने रहे हैं कि कितने b रों या तो आ गई है आकर्षित करने के लिए बराबर या विषम। States 0, 2 and 4 का अर्थ है b की संख्या भी आ गई है। तो आप इस डीएफए को दो हिस्सों में लंबवत रूप से विभाजित कर सकते हैं जहां नीचे b एस और ऊपरी राज्यों में विषम स्थितिएं हैं।

यदि अजीब b अजीब स्थिति को अंतिम राज्य में होना चाहिए तो अंतिम स्थिति को स्वीकार किया जाना चाहिए।

न केवल b एस की स्थिति है, लेकिन a कम से कम 2 होना चाहिए। तो आप इस डीएफए को क्षैतिज रूप से तीन हिस्सों में विभाजित कर सकते हैं जहां a एसपरएस state-2 and 3 और a एस state-4 and 5 पर 2 हैं। पहले दो a एस के बाद a एस की किसी भी संख्या को स्ट्रिंग में अनुमति दी गई है, इसलिए राज्य और q5 पर स्वयं लूप है। राज्य के

_{नंबर की आवश्यकता छह है, क्योंकि के लिए 2 राज्य अजीब भी b और hould के रूप में कम से कम 2 तो 3 राज्यों एक = 0, एक = 1, एक = 2, इसलिए 2 * 3 = 6}

Answer 3

हो,

संयुक्त डीएफए बनाने के लिए आप निम्न सरल चरणों का उपयोग कर सकते हैं।

चलो Σ = {एक , एक , ..., एक _{कश्मीर}}।
1 कदम: दोनों भाषाओं के लिए डिजाइन DFA और नाम उनके राज्य क्यू , क्यू ...

2 कदम: दोनों DFA विशिष्ट अर्थात में हर राज्य का नाम बदलेंक्यू के रूप में DFA के सभी राज्यों का नाम बदलने, क्यू , क्यू , क्यू ... यह मानते हुए कि आप सबस्क्रिप्ट 0 के साथ शुरू कर दिया है; इसका मतलब है कि राज्य में से कोई भी नाम नहीं होगा।

3 कदम: निर्माण संक्रमण तालिका (δ) के लिए निम्न चरणों का उपयोग कर

      3 ए से। शुरू संयुक्त DFA के राज्य:
            लो दोनों DFAs (DFA1 और DFA2) के राज्य शुरू करने और उन्हें क्यू _{[i, j]} मैं कहाँ और जे के शुरू होने से राज्य की सबस्क्रिप्ट हैं के रूप में नाम क्रमशः डीएफए 1 और डीएफए 2; अर्थात क्यू _मैं 1 DFA और क्यू के राज्य शुरू है _जे 2 DFA और निशान क्यू _{के राज्य शुरू है [i, j]} संयुक्त DFA के शुरू होने से राज्य के रूप में।

      3 बी। के रूप में
                      दोनों DFAs की मानचित्र राज्य अगर δ (क्यू _मैं, एक _{कश्मीर}) = क्यू _p1 और δ (क्यू _जे, एक _{कश्मीर}) = क्यू _{पी 2}, जहां क्यू _{पी 1} डीएफए 1 और क्यू _{पी 2 012 से संबंधित हैDFA2 के अंतर्गत आता है तो   δ (क्यू [i, j], एक कश्मीर) = क्यू [P1, P2]}

      3c। संक्रमण तालिका में शेष कोई क्यू _{[i, j]} कोई भी तालिका भरें।

      3 डी। संयुक्त DFA के अंतिम राज्य:
            AND मामले के लिए अंतिम अवस्था सब क्यू _{[i, j]} जहां क्यू _मैं और क्यू _जे क्रमशः DFA1 और DFA2 की अंतिम अवस्था हैं होगा।
            OR मामले के लिए अंतिम अवस्था सब क्यू _{[i, j]} जहां या तो क्यू _मैं या क्यू _जे DFA1 और DFA2 की अंतिम अवस्था है किया जाएगा।

4 कदम: नाम बदलें सब क्यू _{[i, j]} (विशिष्ट) और आकर्षित DFA यह आपके परिणाम होंगे।

उदाहरण:

L= {w: w has at least two a's and an odd number of b's}. 

Step1: ख की की विषम संख्या के लिए
DFA।

कम से कम 2 ए के लिए डीएफए।

चरण 2:
DFA1
की stae

चरण 3 का नाम बदलें (क, ख, ग):
निर्माण संक्रमण तालिका के रूप में किया जाएगा।

Step3d:
जब से हम लेने के लिए और दोनों DFA तो अंतिम अवस्था के लिए क्यू _[2,4] होगा, क्योंकि यह दोनों DFA की अंतिम अवस्था में शामिल किया है।
हम लेने के लिए या दोनों DFA की अंतिम अवस्था क्यू _{होगा है, तो [0,4]}, क्यू _[2,3], क्यू _[1,4], क्यू _{[2, 4]}।
अंतिम तालिका जोड़ने के बाद संक्रमण तालिका इसे पसंद करेगी।

चरण 4:
सभी का नाम बदलें कहा गया है क्यू _{[i, j]}
क्यू _{[0.3] क्यू 0 करने के लिए}
क्यू _{[1, 3]} क्यू
क्यू _[0,4] क्यू _{करने के लिए 1}
क्यू [2,4] क्यू <sub>5 करने के लिए [2,3] क्यू क्यू करने के लिए 4
क्यू [1,4] क्यू करने के लिए 3

तो अंतिम डीएफए नीचे जैसा दिखता है।</sub>