GATE 1990 Subject – Theory Of Computation Topic -Finite Automata.
GATE 1990 Subject – Theory Of Computation Topic -Finite Automata.
बिलकुल! नीचे GATE 1990 के अनुसार Theory of Computation विषय में से Finite Automata (FA) टॉपिक का हिंदी में एक स्पष्ट और संक्षिप्त सारांश दिया गया है, जो तैयारी में मदद करेगा।
Contents [hide]
GATE 1990 – Theory of Computation
विषय (Topic): Finite Automata (FA)
भाषा: हिंदी
Finite Automata क्या है?
Finite Automaton (FA) एक गणनात्मक मॉडल है, जो इनपुट स्ट्रिंग को पढ़कर यह तय करता है कि वह किसी language का हिस्सा है या नहीं। यह सीमित संख्या में स्टेट्स के साथ काम करता है।
मुख्य प्रकार (Types of FA)
प्रकार | नाम | संक्षिप्त रूप |
---|---|---|
Deterministic Finite Automaton | DFA | |
Non-Deterministic Finite Automaton | NFA |
1. Deterministic Finite Automaton (DFA)
- हर इनपुट और हर स्टेट पर सिर्फ एक ट्रांज़िशन होता है।
- कोई अनिश्चितता नहीं होती।
Definition (DFA):
A DFA is a 5-tuple (Q, Σ, δ, q₀, F), where:
- Q = Finite set of states
- Σ = Input alphabet
- δ = Transition function (δ: Q × Σ → Q)
- q₀ = Start state
- F = Set of final/accepting states
2. Non-Deterministic Finite Automaton (NFA)
- एक इनपुट पर एक से अधिक संभावित ट्रांज़िशन हो सकते हैं।
- कभी-कभी ε (epsilon) ट्रांज़िशन भी होते हैं।
NFA में Acceptance:
अगर कोई एक भी path accepting state तक पहुंच जाए, तो input स्वीकार किया जाता है।
DFA और NFA में अंतर (Differences):
विशेषता | DFA | NFA |
---|---|---|
Determinism | हाँ | नहीं |
ट्रांज़िशन | एक ही | एक से अधिक |
सरलता | जटिल | आसान डिज़ाइन |
Execution | Fast | Theoretical fast |
हर NFA का एक समकक्ष DFA होता है (NFA ⇒ DFA Conversion संभव है)
GATE 1990 जैसे प्रश्नों के लिए सुझाव:
संभावित प्रश्न प्रकार:
- किसी DFA/NFA को देखकर यह बताना कि कौन सी language एक्सेप्ट होती है।
- NFA को DFA में बदलना।
- Regular Expression से FA बनाना।
- Language की पहचान: finite/infinite, regular/non-regular।
उदाहरण (Example DFA):
मान लीजिए, हमें उस language का DFA बनाना है जो सिर्फ even number of 1s को एक्सेप्ट करती है:
States:
- q0: Even number of 1s
- q1: Odd number of 1s
Transition Table:
State | Input 0 | Input 1 |
---|---|---|
q0 | q0 | q1 |
q1 | q1 | q0 |
Start state = q0
Accepting state = q0
Final Tips for GATE:
- DFA/NFA के diagrams को समझने और बनाने की प्रैक्टिस करें।
- Regular expressions से FA बनाना सीखें।
- Closure properties, language equivalence, और minimization अच्छे से पढ़ें।
क्या आप चाहेंगे कि मैं आपको GATE 1990 का original MCQ question on FA या उसका practice test भी दूं?