Finite automata

  • Post author:
Download PDF
Advertisement

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,

Initial State

Final State:

The final state of DFA can be one or more than one.

Advertisement

The symbol of the final state is as follows,

Final State

Transition:

The movement from one state to another state is known as transition.

The symbol of transition is as follows,

Transition

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

Finite automata

Automata Theory

Advertisement