DIZNR INTERNATIONAL

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

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

https://www.gyanodhan.com/video/7B3.%20GATE%20CSEIT/Theory%20of%20Computation/628.%20CSEIT%20-%20GATE%201990%20%20%20Subject%20-%20Theory%20Of%20Computation%20%20%20Topic%20-Finite%20Automata....mp4

बिलकुल! नीचे GATE 1990 के अनुसार Theory of Computation विषय में से Finite Automata (FA) टॉपिक का हिंदी में एक स्पष्ट और संक्षिप्त सारांश दिया गया है, जो तैयारी में मदद करेगा।


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:


2. Non-Deterministic Finite Automaton (NFA)

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:

Transition Table:

State Input 0 Input 1
q0 q0 q1
q1 q1 q0

Start state = q0
Accepting state = q0


Final Tips for GATE:


क्या आप चाहेंगे कि मैं आपको 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