Finite automata

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

Zitoc

We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.