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 −

Its graphical representation would be as follows

Automata Theory