8
क्या किसी के पास दो दिए गए डीएफए के संघ के निर्माण के लिए एल्गोरिदम का सीधा विवरण है? उदाहरण के लिए, कहते हैं कि हम दो DFA खत्म हो चुका है {0,1} है जहांआप दो डीएफए के संघ का निर्माण कैसे करते हैं?
{w|w has an odd number of characters}
w has states A and B
delta | 0 | 1
----------------
A | B | B
----------------
B | A | A
{x|x has an even number of 1s}
x has states a and b
delta | 0 | 1
----------------
a | a | b
----------------
b | b | a
मैं एक जिसके परिणामस्वरूप संक्रमण के रूप में संघ दिखा तालिका:
delta | 0 | 1
----------------
Aa | Ba | Bb
----------------
Ab | Bb | Ba
----------------
Ba | Aa | Ab
----------------
Bb | Ab | Aa
मैं अपने व्याख्यान नोट्स में एक सचित्र समाधान है, लेकिन देखना चाहते हैं कि दूसरे इसका वर्णन कैसे करेंगे। इससे, मैं देख सकता हूं कि हम अनिवार्य रूप से इन दो मूल सारणी को अपने राज्य मूल्यों का उपयोग करके "गुणा करें" जिसके परिणामस्वरूप एक बड़ी संक्रमण तालिका होती है। इस प्रकार डीएफए परिणामस्वरूप तालिका से खींचा जा सकता है। क्या यह सही लगता है और क्या यह सभी डीएफए मामलों के लिए काम करना चाहिए, या क्या मुझे कुछ याद आ रही है?
क्या आपको एक संक्रमण मिलता है जो ऑटोमाटा में असंभव है? –
आप automaton के लिए ई (त्रुटि) स्थिति जोड़ देंगे जिसमें असंभव संक्रमण है। वह automaton शेष इनपुट अनुक्रम के लिए उस स्थिति में रहेगा। मान लें कि यह पहला है। इसके बाद आप नए एबोनॉन में एए अब, बा, बीबी, ईए, ईबी राज्य करेंगे। – Nenad
मुझे लगता है कि यह समान होगा यदि एक automaton केवल इनपुट प्रतीक के रूप में {0,1} है, और दूसरे के पास इनपुट प्रतीक के रूप में {1,2} है। इसके बाद हमें त्रुटि राज्यों (दूसरे के लिए ई और दूसरे के लिए ई) के साथ दोनों automatons का विस्तार करना होगा, जहां पहला इनपुट होगा यदि 2 इनपुट होता है, और दूसरा इनपुट होता है तो 0 स्थिति में होता है। – Nenad