Finite Automata in Hindi
Finite Automata , patterns को recognize करने के लिए एक सरल मशीन है. Finite automata को states machine या finite-state machines (FSM) भी कहते है. यह एक गणितीय मॉडल है जिसका प्रयोग कंप्यूटर प्रोग्राम तथा क्रमबद्ध लॉजिक सर्किटों को डिजाईन करने में किया जाता है.
“वह Automata जिसमें states की संख्या finite (सीमित) होती है उसे 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 के प्रकार
Finite automata दो प्रकार का होता है:-
- Deterministic Finite Automata (DFA)
- nonDeterministic Finite Automata (NFA)
Deterministic Finite Automata (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.
यहाँ ऊपर 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{}में लिखते है जो एक या उससे अधिक हो.
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 में , यदि एक input string के लिए कोई भी path एक final state की ओर जाता है , तो input string accept कर लिया जाता है।उदाहरण के लिए उपर वाले चित्र में अगर 00 तथा 11 किसी भी बाइनरी string की substring होती है तो उन्हें accept कर लिया जाता है.
कुछ महत्वपूर्ण बिंदु (DFA vs NFA in hindi) :-
- प्रत्येक DFA, NFA होता है पर प्रत्येक NFA, DFA नहीं होता है।
- DFA तथा NFA दोनों के पास समान power होता है और प्रत्येक NFA एक DFA में translate हो सकता है।
- DFA तथा NFA में बहुत सारें final states हो सकते है।
- DFA का प्रयोग compiler में lexical analysis के लिए किया जाता है।
- DFA में backtracking संभव होती है, जबकि NFA में backtracking हमेशा संभव नहीं होती है.
- DFA में space की ज्यादा जरुरत पड़ती है जबकि NFA में कम space की जरुरत पड़ती है.
निवेदन:- आपको finite automata की यह पोस्ट कैसी लगी मुझे कमेंट के द्वारा बताइए तथा इसे अपने दोस्तों के साथ share करें. धन्यवाद.