Conversion of NDFA to DFA in Hindi

Unit 2

Types of Finite Automata

Topic 3 : Conversion of NDFA to DFA in Hindi

NDFA में, जब एक spacial input current state को दिया जाता है, तो machine कई states में जाती है। इसमें दिए गए input symbol पर zero, एक या एक से अधिक move हो सकते हैं। दूसरी ओर, DFA में, जब Current State को एक spacial input दिया जाता है, तो machine केवल एक state में जाती है। DFA के पास दिए गए input symbol पर केवल एक Move होता है।

Conversion from NFA to DFA

मान लीजिए कि एक NFA N है जो एक Language L को पहचानता है। तब DFA D का निर्माण Language के रूप में किया जा सकता है:

Step 1: Initially Q’ = ɸ.

Step 2: Add q0 to Q’.

Step 3 : Q 'में प्रत्येक State के लिए, NFA के transition function का उपयोग करके प्रत्येक input symbol के लिए states का possible set ढूंढें। यदि states का यह set Q 'में नहीं है, तो इसे Q' में जोड़ें।

NFA के लिए विभिन्न Parameters निम्नलिखित हैं।

Q = { q0, q1, q2 }

∑ = ( a, b )

F = { q2 }

δ (Transition Function of NFA)

State	a	b
Q0	Q0, Q1	Q0
Q1		Q2
Q2

Step 1: Q’ = ɸ

Step 2: Q’ = {q0}

Step 3: Q 'में प्रत्येक state के लिए, प्रत्येक input symbol के लिए states को खोजें। वर्तमान में, Q 'में स्थिति q0 है, NFA के Transition function का उपयोग करते हुए input symbol a और b पर q0 से Move प्राप्त करें और DFA के Transition Table को Update करें।

δ’ (Transition Function of DFA)

State	a	b
Q0	{Q0, Q1}	Q0

अब {q0, q1} को single state माना जाएगा। जैसा कि इसकी प्रविष्टि (entry) Q 'में नहीं है, इसे Q' में जोड़ें। तो Q '= {q0, {q0, q1}}

अब, अलग input symbol पर state {q0, q1} से ले जाता है, DFA के Transition Table में मौजूद नहीं है, हम इसकी गणना करेंगे:

δ’ ( { q0, q1 }, a ) = δ ( q0, a ) ∪ δ ( q1, a ) = { q0, q1 }

δ’ ( { q0, q1 }, b ) = δ ( q0, b ) ∪ δ ( q1, b ) = { q0, q2 }

अब हम DFA की Transition Table को Update करेंगे।

δ’ (Transition Function of DFA)

State	a	B
Q0	{Q0, Q1}	Q0
{Q0, Q1}	{Q0, Q1}	{Q0, Q2}

अब {q0, q2} को Single State माना जाएगा। जैसा कि इसकी Entry Q 'में नहीं है, इसे Q' में जोड़ें।

Q '= {q0, {q0, q1}, {q0, q2}}

अब, विभिन्न input symbol पर state {q0, q2} से moves होता है, जो DFA की Transition Table में मौजूद नहीं हैं, हम इसकी गणना करेंगे:

δ’ ( { q0, q2 }, a ) = δ ( q0, a ) ∪ δ ( q2, a ) = { q0, q1 }

δ’ ( { q0, q2 }, b ) = δ ( q0, b ) ∪ δ ( q2, b ) = { q0 }

अब हम DFA की Transition Table को Update करेंगे।

δ’ (Transition Function of DFA)

State	a	B
Q0	{Q0, Q1}	Q0
{Q0, Q1}	{Q0, Q1}	{Q0, Q2}
{Q0, Q2}	{Q0, Q1}	Q0