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

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

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

 Finite Automata – GATE 1991 (Theory of Computation)

Finite Automata (FA) is a key topic in Theory of Computation (TOC) and is used to recognize Regular Languages. It is one of the fundamental models of computation.

 Definition of Finite Automata

A Finite Automaton (FA) is formally defined as a 5-tuple (Q, Σ, δ, q₀, F), where:

• Q → A finite set of states.

• Σ → A finite set of input symbols (Alphabet).

• δ (Transition Function) → Defines transitions between states.

• q₀ (Start State) → The initial state.

• F (Final States) → A set of accepting states.

 Types of Finite Automata

Finite Automata can be classified into two main types:

Both DFA and NFA recognize the same class of languages (Regular Languages).

 Example of DFA

Language: Strings over {0,1} that end with 1.

DFA Representation:

States: {q0, q1}
Alphabet: {0,1}
Start State: q0
Final State: q1
Transitions:

Explanation:

• Start at q0.

• If 1 is encountered, move to q1.

• Stay in q1 if more 1s are encountered.

• Any string ending in 1 is accepted.

 Example of NFA

Language: Strings containing 10 as a substring.

NFA Representation:

States: {q0, q1, q2}
Alphabet: {0,1}
Start State: q0
Final State: q2
Transitions:

Explanation:

• Start at q0.

• If 1 appears, move to q1.

• If 0 follows, move to q2 (accepting state).

• Once in q2, stay there for any input.

 GATE 1991 Question on Finite Automata

Q: Which of the following statements is true?
(A) Every NFA can be converted to an equivalent DFA.
(B) NFA can recognize more languages than DFA.
(C) There exists an NFA for which no equivalent DFA exists.
(D) DFA and NFA recognize different sets of languages.

Correct Answer: (A) Every NFA can be converted to an equivalent DFA.
Explanation: DFA and NFA are equivalent in power, meaning any language recognized by an NFA can also be recognized by a DFA. The subset construction algorithm is used to convert an NFA to an equivalent DFA.

 Summary

Finite Automata recognizes Regular Languages.
DFA has unique transitions, while NFA allows multiple transitions.
Both DFA and NFA are equivalent in power but differ in complexity.
Used in compilers, text searching, and pattern recognition.

 Do you need more solved GATE questions or examples?