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 करें. धन्यवाद.
Achha laga. Notes banane ke liye badhya hai. Theory of computation ke sabhi topic par likhen. Thank you. M.Sc. mathematics me ye topic syllabus me hai. Upyogi rahega.
यहाँ ऊपर image में q0 initial state है और q2 final state है।
Final state को हमेशा double circle से represent करते है।
// CORRECTION
agar q2 final state hai to usse double circle me kyu nhi liya gya hai image me ??
Thanks for telling this… Mai ise sahi kar dunga…
Yes , bro please correct that mistake otherwise it can create a concussion for students…..
And it’s really helpful after get this there is no need to making notes for me….
Heartfelt thanks
yaha per q1 is q2 and q2 is q1 have step missing
mene to apne friends ko yehi site bati ha easy to learn in hindi , very helpfull and easy to explain every concept ,please my request all computer science subject solution or matter hindi me avialable ho. tnx…and loved this site love uuuu.
dhnywaad sanju… mujhe khushi hai ki aapko yah website pasand aayi..isi tarah padhte rahiye..
DFA में backtracking संभव होती है, जबकि NFA में backtracking हमेशा संभव नहीं होती है.
sir yaha bahut bahut helpful ha mara liya asa hee content upload karta raho full support of my side
Thanks Anil. aapke support ke liye dhnywaad.
Sir plz share the notes on this topic…
Universal turing machine
Turing machine ke baare me pahle se hi dala hua h aap search krke padhiye
Great. God bless you sir.
thanks shubhani. Glad u like it.
To ap q1 ko final state samjh li jiye
Tum mahan hovbhai tumhri wajh se hi me 2 nd year 4th sem pass ho paya yr ksm se tum bhut mst language me notes dete ho bro big fan yr bro
Sir ye jo symbol hai inke name bata dijiye tupple ke