Table of Contents
hide
Introduction
- A language is regular if and only if it can be accepted by a finite automaton.
-
Finite Automata (FA) is the simplest computational model/abstract machine in the Theory of Computation (TOC).
- Finite Automata form TOC’s base, and are extended by Pushdown Automata (for context-free languages) and Turing Machines.
Definition
- A Finite Automaton (FA) is a mathematical model of computation with finite states and is used to recognize regular languages or patterns.
- Finite Automata are state machines that process strings symbol by symbol, changing states according to defined rules.
- A Finite Automaton is defined as a 5-tuple:
FA=(Q,Σ,δ,q0,F)
where
Q = Finite set of states
Σ (Sigma) = Input alphabets/symbols
δ (delta) = Transition function
q₀ = Initial (start) state
F = Set of final (accepting) states
The details of tuples are –
States (Q)
-
-
-
- This tuple represents the current situation of the automaton.
- It is finite in number
- For example, Q = {q0, q1, q2, q3}
-
-
Input Alphabet (Σ)
-
-
-
- This tuple represents the set of symbols the automaton can read.
- For example, Σ = {a, b,c}
-
-
Transition Function (δ)
-
-
-
- This tuple defines how the automaton moves from one state to another.
- For example, δ(q0, a) = q1
-
-
Start State (q₀)
-
-
-
- This tuple represents the state where computation begins.
- For example, q₀ = q0
-
-
Final States (F)
-
-
-
- It is accepting states.
- If input ends in one of these states, the string is accepted.
- For example, F = {q2}
-
-
Characteristics of Finite Automata
-
An FA consists of a finite number of states, transitions between states based on input symbols, a start state, and one or more (final) accepting states. If the automaton ends in an accepting state after reading the entire input, the string is accepted; otherwise, it is rejected. It processes input strings symbol by symbol.
- Regular languages are accepted by finite automata.
- Finite Automata are simple machines with no memory except the current state.
- The purpose of FA is to check whether a given string belongs to a regular language.
- Finite Automata provide the theoretical foundation for pattern recognition and regular language processing.
Representation of Finite Automata
Finite automata can be represented in the form of –
- State Transition Diagram
- Transition Table
- Formal Definition
Types of Finite Automata
There are two types of Finite Automata –
-
Deterministic Finite Automaton (DFA)
- A DFA is an FA where
- Exactly one transition exists for each state and input symbol.
- No ε-moves allowed.
- Properties
- One path for each input
- Easier to implement in compilers.
- Fast execution
- For example: δ(q0, a) = q1
- A DFA is an FA where
-
Non-Deterministic Finite Automaton (NFA)
-
An NFA is an FA where
-
For a state and input symbol, there may be multiple transitions or even ε‑transitions (without consuming input).
-
ε-transitions are allowed
-
- Properties
- More flexible
- Easier to design
- Can be converted to DFA
- Example:
-
δ(q0, a) = {q1, q2}
δ(q1, ε) = q2
Use/Applications of Finite Automata
The concept of Finite Automata is used in:-
- Foundation of Compiler Design (Lexical Analysis)
- To model and recognize regular languages
- Regular Expression matching
- Pattern matching in Editors and Search tools in Text Processing.
- The modeling of a sequential logic circuit
- Network Protocol Design and Verification
- Vending machines, Elevators
- Input Validation
- Simple decision-making models for AI.
Limitations of Finite Automata
The concept of Finite Automata can not be used in:-
- Nested structures
- They cannot handle languages requiring memory of arbitrary length (e.g., balanced parentheses).
- Memory-based languages
- Cannot recognize non-regular languages
0 Comments