GATE 1991 Subject – Theory Of Computation Topic -Finite Automata.
GATE 1991 Subject – Theory Of Computation Topic -Finite Automata.
Contents [hide]
- 1 Finite Automata – GATE 1991 (Theory of Computation)
- 2 Definition of Finite Automata
- 3 Types of Finite Automata
- 4 Example of DFA
- 5 Language: Strings over {0,1} that end with 1.
- 6 DFA Representation:
- 7 Example of NFA
- 8 Language: Strings containing 10 as a substring.
- 9 NFA Representation:
- 10 GATE 1991 Question on Finite Automata
- 11 Summary
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:
Type | Description | Recognizes |
---|---|---|
DFA (Deterministic Finite Automata) | Exactly 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 |
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:
State | Input 0 |
Input 1 |
---|---|---|
q0 | q0 | q1 |
q1 | q1 | q1 |
Explanation:
-
Start at
q0
. -
If
1
is encountered, move toq1
. -
Stay in
q1
if more1
s 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 toq1
. -
If
0
follows, move toq2
(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?