GATE 1990 Subject – Theory Of Computation Topic -Finite Automata.

GATE 1990 Subject – Theory Of Computation Topic -Finite Automata.



play-rounded-fill play-rounded-outline play-sharp-fill play-sharp-outline
pause-sharp-outline pause-sharp-fill pause-rounded-outline pause-rounded-fill
00:00

बिलकुल! नीचे 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)

प्रकार नाम संक्षिप्त रूप
1️⃣ Deterministic Finite Automaton DFA
2️⃣ 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 जैसे प्रश्नों के लिए सुझाव:

🎯 संभावित प्रश्न प्रकार:

  1. किसी DFA/NFA को देखकर यह बताना कि कौन सी language एक्सेप्ट होती है।
  2. NFA को DFA में बदलना।
  3. Regular Expression से FA बनाना।
  4. 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 भी दूं?

GATE 1990 Subject – Theory Of Computation Topic -Finite Automata.

A Complexity Theory of Neural Networks – DTIC



Leave a Reply

Your email address will not be published. Required fields are marked *

error: