GATE 1992 Theory Of Computation Topic -Finite Automata
GATE 1992 Theory Of Computation Topic -Finite Automata
Contents
- 1 Finite Automata – GATE 1992 (Theory of Computation)
- 1.0.1 Definition of Finite Automata (FA)
- 1.0.2 Types of Finite Automata
- 1.0.3 Example of DFA
- 1.0.4 Language: Strings over {0,1} that end with 1.
- 1.0.5 DFA Representation:
- 1.0.6 Example of NFA
- 1.0.7 Language: Strings containing 10 as a substring.
- 1.0.8 NFA Representation:
- 1.0.9 Key Differences Between DFA & NFA
- 1.0.10 Applications of Finite Automata
- 1.0.11 GATE 1992 Question on Finite Automata
- 1.0.12 Summary
- 1.0.13 Evolutionary Search for Cellular Automata Logic Gates with …
- 1.0.14 GATE 1992 Theory Of Computation Topic -Finite Automata
Finite Automata – GATE 1992 (Theory of Computation)
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
1is encountered, move toq1. -
Stay in
q1if more1s are encountered. -
Any string ending in
1is 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
1appears, move toq1. -
If
0follows, move toq2(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?