Unknown Conversion of NDFA to DFA in Hindi | My Project HD | My Project HD
X

Conversion of NDFA to DFA in Hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation



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' में जोड़ें।

 conversion of NDFA to DFA in Hindi

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

 



More Tutorials

Web Technology Tutorials in Hindi

Web Technology Tutorials in Hindi

Read More
Diploma engineering tutorial for polytechnic collage

Diploma Engineering Tutorial

Read More
Final Year Projects for Computer Science with Source Code

Final Year Projects for Computer Science with Source Code

Read More