Finite Automata In TOC
Finite Automata (FA) is a machine in TOC that accepts all the regular languages. These abstract machines operate within a finite set of states and transition between these states based on inputs from a finite alphabet. Finite automata have some finite states and rules for moving from one state to another, but it depends upon the given input symbol.
Formal definition of a Finite Automaton
A Finite Automata contains five tuples { Q, Σ, q, F, δ }. Where
- Q is a set of finite states.
- ∑ represents a finite set of symbols or alphabets.
- δ represents the transition function.
- q0 is the initial state (q0 ∈ Q).
- F is a set of final states of Q (F ⊆ Q).
States, Alphabet, Transition Function, Initial State, and Final States are the Key components of finite automata.
Working Of Finite Automata
Every automata takes a language as input, processes it through some automata machines, and gives an output in the form of a set of states. The following descriptive diagram
Types Of Finite Automata in TOC
Following are two types of finite automata.
1. Deterministic Finite Automata (DFA)
In a DFA,
- For a particular input symbol, the machine goes to one state only.
- A null (ε) move is not allowed. It means the state cannot change without an input symbol.
DFA contains 5 tuples {Q, Σ, q, F, δ}.
- Q: Set of all states.
- Σ: Set of input symbols.
- δ: Transition Function, δ: Q X Σ →Q
- q: Initial state.
- F: Set of final state.
2. Nondeterministic Finite Automata (NFA)
NFA is similar to DFA except for the Null (or ε) move. In NFA, a Null move is allowed. It means the state can change without an input symbol. NFA also has similar five tuples {Q, Σ, q, F, δ} like DFA except for the transition function. The following is the NFA Transition Function.
δ: Q X (Σ U ε ) → 2 ^ Q.
Some Important Points About DFA and NFA
- Every DFA is NFA, but NFA is not DFA.
- In NFA and DFA, there can be multiple final states.
- DFA is used in Lexical Analysis in Compiler.
- NFA is mainly used as a theoretical concept.