GATE 1992 Theory Of Computation Topic -Finite Automata

Finite Automata (FA) is a fundamental concept in Theory of Computation (TOC) and plays a key role in recognizing patterns and designing compilers. It is the simplest model of computation used to recognize Regular Languages.

Definition of Finite Automata (FA)

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

Q → Finite set of states.
Σ → Finite set of input symbols (Alphabet).
δ (Transition Function) → Mapping from (State × Input) → State.
q₀ (Start State) → The initial state of the automaton.
F (Final States) → Set of accepting states.

Types of Finite Automata

Finite Automata are classified into two types:

Type	Description	Recognizes
DFA (Deterministic Finite Automata)	One transition per input symbol from each state	Regular Languages
NFA (Nondeterministic Finite Automata)	Multiple transitions for the same input symbol or ε-moves	Regular Languages

DFA and NFA are equivalent in power (both recognize the same set of 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:

State	Input `0`	Input `1`
q0	q0	q1
q1	q1	q1

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:

State	Input `0`	Input `1`
q0	q0	q1
q1	q2	–
q2	q2	q2

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.

Key Differences Between DFA & NFA

Feature	DFA	NFA
Determinism	One transition per input symbol	Multiple transitions possible
Empty Moves (ε-transitions)	Not allowed	Allowed
Complexity	More states required	Fewer states
Conversion	Easy to implement	Can be converted to DFA

DFA is always more structured but may require more states than an equivalent NFA.

Applications of Finite Automata

Lexical Analysis in Compilers (Token Recognition).
Pattern Matching (Regular Expressions).
Text Searching Algorithms (e.g., KMP Algorithm).
Hardware Circuit Design (Sequential Circuits).

GATE 1992 Question on Finite Automata

Q: Which of the following is true?
(A) Every DFA is an NFA.
(B) Every NFA is a DFA.
(C) NFA can recognize more languages than DFA.
(D) DFA and NFA recognize different languages.

Correct Answer: (A) Every DFA is an NFA.
Explanation: DFA is a special case of NFA where each state has only one transition per input. However, both DFA and NFA recognize the same set of Regular Languages.

Summary

Finite Automata is a basic computational model that 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.

Would you like more solved GATE questions or examples?