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

NP Complete Problem in Hindi

NP-Complete problems एक महत्वपूर्ण वर्ग हैं जो computational complexity the...

Multihead Turing Machine और Multidimensional Turing Machine की विशेषताएँ और अंतर

Multihead Turing Machine एक प्रकार की Turing Machine है जिसमें एक से अ�...

Universal Turing Machine and Multitape in Hindi

Universal Turing Machine (UTM) एक ऐसी ट्यूरिंग मशीन है, जो किसी भ...

Techniques for Turing Machine Construction in Hindi

Turing Machine कंप्यूटर विज्ञान में एक theoretical model है, जो क�...

Petri Net Model in Hindi | Theory of Computation (TOC) Explained

Petri Net एक mathematical model है जो systems के behavior को graphically represent करने �...

Conversion of NDFA to DFA in Hindi