finite automata in hindi and DFA, NFA in hindi

Finite Automata in hindi

Finite Automata , patterns को recognize करने के लिए एक सरल मशीन है. finite automata को states machine या finite-state machines (FSM) भी कहते है. finite automata एक गणितीय मॉडल है जिसका प्रयोग कंप्यूटर प्रोग्राम तथा क्रमबद्ध लॉजिक सर्किटों को डिजाईन करने में किया जाता है.

states की एक finite संख्या के साथ एक Automata को finite Automata कहते है।

एक finite Automata  में पांच tuples होते है

Q, Σ, q, F, δ (यह machine  का formal specification होता है।)

Q – यह states का finite समूह होता है

Σ – यह input symbols का समूह होता है

q – यह initial states होता है

F – यह final states  का समूह होता है

δ – यह transition function होता है ,

finite automata दो प्रकार का होता है:-

1:- Deterministic Finite Automato (DFA)

2:- nonDeterministic Finite Automato (NFA)

1:- Deterministic Finite Automato (DFA) in hindi

Deterministic finite Automata को DFA भी कहते है। एक DFA में , एक विशेष input character के लिए machine केवल एक state में  जाती है। एक transition function सभी  input symbols के लिए सभी state पर डिफाइन होते है.

इसके अलावा DFA में  NULL (या Σ) को move करना allow नहीं होता है अर्थात् DFA किसी भी input character के बिना state change नहीं कर सकती है।

DFA जो है वह 5 tuples के द्वारा प्रदर्शित होता है:-

Q – यह states का finite समूह होता है

Σ – यह input symbols का समूह होता है

q – यह initial states होता है

F – यह final states  का समूह होता है

δ – यह transition function होता है इसे निम्न प्रकार डिफाइन किया जाता है:- δ : Q X ∑ –> Q.

DFA in hindi finite automata

यहाँ ऊपर image में q0 initial state है और q2 final state है।

Final state को हमेशा double circle से represent करते है।

यहाँ इस diagram  का formal specification:-

Q – {q0 , q1 , q2}

δ – Q × Σ = Q

Σ – {0, 1}

q – q0

F – { q2 }

δ = ( q0,0) -> q1
(q1,1) -> q2

हम उन tuples को curly braces{}में लिखते है जो एक या उससे अधिक हो.

2:- Non deterministic finite Automata in hindi

Non deterministic finite Automata को NFA कहते है। NFA DFA की तरह ही same होता है। पर NFA में कुछ additional features होते है –

  • Null ( Σ ) को move करना allowed होता है । अर्थात् यह symbols को read किये बिना आगे move हो सकता है।
  • NFA में किसी एक विशेष input के लिए, मशीन किसी भी state में move हो सकती है. दूसरे शब्दों में कहें तो उस exact state को हम पहचान नहीं सकते जिसमें मशीन move करती है. क्योंकि वह किसी भी state में move हो सकती है.

NFA में कुछ additional features होते है फिर भी NFA में कोई भी पावर add नहीं होता है। NFA तथा DFA को हम यदि compare करे तो NAF और DFA दोनों की power equivalent होती है।

परन्तु NFA के पास एक अलग transition function होता है , बाकि सब DFA जैसा होता है। इसमें भी 5 tuples होते है केवल transition function अलग होता है.

Transition Function δ:  Q X (∑ U ϵ ) –> 2 ^ Q.

Transition function में, कोई भी input including null (or epsilon) के लिए NFA किसी भी states में जा सकता है।

nfa in hindi finite automata

NFA में , यदि एक input string के लिए कोई भी path एक final state की ओर जाता है , तो input string accept कर लिया जाता है।उदाहरण के लिए उपर वाले चित्र में अगर 00 तथा 11 किसी भी बाइनरी string की substring होती है तो उन्हें accept कर लिया जाता है.

कुछ महत्वपूर्ण बिंदु (DFA vs NFA in hindi) :-

  1. प्रत्येक DFA, NFA होता है पर प्रत्येक NFA, DFA नहीं होता है।
  2. DFA तथा NFA दोनों के पास समान power होता है और प्रत्येक NFA एक DFA में translate हो सकता है।
  3. DFA तथा NFA में बहुत सारें final states हो सकते है।
  4. DFA का प्रयोग compiler में lexical analysis के लिए किया जाता है।
  5. DFA में backtracking संभव होती है, जबकि NFA में backtracking हमेशा संभव नहीं होती है.
  6. DFA में space की ज्यादा जरुरत पड़ती है जबकि NFA में कम space की जरुरत पड़ती है.

निवेदन:- आपको finite automata की यह पोस्ट कैसी लगी मुझे कमेंट के द्वारा बताइए तथा इसे अपने दोस्तों के साथ share करें. धन्यवाद.

Leave a Comment