Finite automata
Finite automata can be described into two types.
1: Deterministic Finite Automata (DFA).
2: Non Deterministic Finite Automata (NDFA).
Deterministic Finite Automata:
DFA can be described as
- The total number of the alphabet should be finite.
- The total number of states should be finite.
- The total number of transitions should be finite.
- It is required that the number of transition expecting from the states must be equal to the total number of the alphabet.
Graphical Representation of DFA:
States:
There are two types of states.
1: Initial State
2: Final State
Initial State:
There must be one initial state of automata. The initial state is the state from which our language starts.
The symbol of Initial State is as follows,
Final State:
The final state of DFA can be one or more than one.
The symbol of the final state is as follows,
Transition:
The movement from one state to another state is known as transition.
The symbol of transition is as follows,
Example
Let a deterministic finite automaton be as follows
- P = [x, y, z],
- ∑ = [0, 1],
- Initial = [x],
- Final = [c], and
Transition function δ as shown by the following table −
| Present State | Next State for Input 0 | Next State for Input 1 |
| x | X | y |
| y | Z | x |
| z | Y | z |
Its graphical representation would be as follows
