NDFA से DFA रूपांतरण

समस्या का विवरण

चलो X = (Q_x, ∑, δ_x, q₀, F_x)एक NDFA बनें जो भाषा L (X) को स्वीकार करता है। हमें एक समतुल्य डीएफए डिजाइन करना होगाY = (Q_y, ∑, δ_y, q₀, F_y) ऐसा है कि L(Y) = L(X)। निम्नलिखित प्रक्रिया NDFA को उसके समकक्ष DFA में परिवर्तित करती है -

कलन विधि

Input - एक एनडीएफए

Output - समतुल्य डीएफए

Step 1 - दिए गए एनडीएफए से राज्य तालिका बनाएं।

Step 2 - समतुल्य डीएफए के लिए संभावित इनपुट अल्फाबेट्स के तहत एक खाली राज्य तालिका बनाएं।

Step 3 - q0 द्वारा DFA के प्रारंभ राज्य को चिह्नित करें (NDFA के रूप में भी)।

Step 4- प्रत्येक संभावित इनपुट वर्णमाला के लिए राज्यों {Q ₀ , Q ₁ , ..., Q _n } के संयोजन का पता लगाएं ।

Step 5 - हर बार जब हम इनपुट वर्णमाला कॉलम के तहत एक नया डीएफए राज्य उत्पन्न करते हैं, तो हमें चरण 4 को फिर से लागू करना होगा, अन्यथा चरण 6 पर जाएं।

Step 6 - जिन राज्यों में NDFA के अंतिम राज्यों में से कोई भी शामिल है, वे समान DFA के अंतिम राज्य हैं।

उदाहरण

आइए नीचे दिए गए आंकड़े में दिखाए गए एनडीएफए पर विचार करें।

क्ष	δ (क्यू, 0)	δ (क्यू, 1)
ए	{A, b, सी, डी, ई}	{डे}
ख	{सी}	{इ}
सी	∅	{B}
घ	{इ}	∅
इ	∅	∅

उपरोक्त एल्गोरिथ्म का उपयोग करते हुए, हम इसके समकक्ष डीएफए पाते हैं। डीएफए की राज्य तालिका नीचे दी गई है।

क्ष	δ (क्यू, 0)	δ (क्यू, 1)
[ए]	[ए, बी, सी, डी, ई]	[डे]
[ए, बी, सी, डी, ई]	[ए, बी, सी, डी, ई]	[ख, डी, ई]
[डे]	[इ]	∅
[ख, डी, ई]	[सी, ई]	[इ]
[इ]	∅	∅
[सी, ई]	∅	[ख]
[ख]	[सी]	[इ]
[सी]	∅	[ख]

डीएफए का राज्य चित्र इस प्रकार है -