GATE 1994 Theory Of Computation Topic -Finite Automataj9
GATE 1994 Theory Of Computation Topic -Finite Automata
The GATE 1994 exam included Theory of Computation, and one of the fundamental topics in this domain is Finite Automata. Let’s go through the key concepts related to Finite Automata (FA) that might be relevant to GATE questions.
Contents
What is Finite Automata (FA)?
A Finite Automaton is a mathematical model of a computation system that consists of:
- A finite set of states
- A finite input alphabet
- A transition function
- A start state
- A set of accepting (final) states
Types of Finite Automata
There are two main types of Finite Automata:
-
Deterministic Finite Automaton (DFA)
- For each state and input symbol, there is exactly one transition.
- Example: A DFA recognizing binary strings that end with
01.
-
Non-Deterministic Finite Automaton (NFA)
- For a given state and input symbol, there can be multiple transitions.
- Can have ε (epsilon) transitions (moves without consuming input).
- Example: An NFA recognizing binary strings containing
11anywhere in the string.
Formal Definition of DFA
A DFA is a 5-tuple:
(Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)
where:
- Q → Finite set of states
- Σ → Finite input alphabet
- δ → Transition function (δ: Q × Σ → Q)
- q₀ → Initial state (q₀ ∈ Q)
- F → Set of final (accepting) states (F ⊆ Q)
Example DFA
Let’s define a DFA that accepts binary strings ending with ’01’.
States:
q0(Start State)q1(Reads ‘0’)q2(Reads ’01’ – Final State)
| Current State | Input ‘0’ | Input ‘1’ |
|---|---|---|
| q0 (Start) | q1 | q0 |
| q1 | q1 | q2 (Final) |
| q2 (Final) | q1 | q0 |
NFA vs DFA
| Feature | DFA | NFA |
|---|---|---|
| Determinism | Unique transition per input | Multiple transitions per input |
| Epsilon (ε) transitions | Not allowed | Allowed |
| Complexity | Simpler, more efficient | More flexible, but harder to construct |
| Power | No more powerful than NFA | Can be converted to DFA |
Key Fact: Every NFA can be converted into an equivalent DFA (using the subset construction method).
Applications of Finite Automata
Lexical Analysis in Compilers
Pattern Matching (Regular Expressions, String Searching)
Protocol Design in Networking
Text Processing (e.g., Searching for keywords in a document)
GATE 1994 Sample Question (Finite Automata)
Question:
Which of the following statements is true?
A) Every NFA has an equivalent DFA.
B) DFA is more powerful than NFA.
C) NFA can recognize more languages than DFA.
D) Some regular languages cannot be recognized by DFA.
Answer: (A) Every NFA has an equivalent DFA.
Explanation: DFA and NFA recognize the same class of languages (Regular Languages), but DFA has unique transitions while NFA allows multiple transitions.
Would you like more GATE-style practice questions or explanations on converting NFA to DFA?