The word “deterministic” refers to the fact that the transition is deterministic. There is only one state to which an automaton can transit from the current state each input. The word “finite” implies that number of state are finite. A finite automata consists of five parts:

- 1. A finite set of states, represented as Q.
- 2. A finite set of alphabet, represented as Σ.
- 3. An initial state, represented as
**q**_{0}. - A set of accepting states. An accepting state or final state is for ‘Yes’ answer. It is a subset of Q and is represented as F.
- F ⊆ Q
- 5. A next state function or a transition function. Next state depends on the current state and the current input. It is a function from Q X Σ to Q. It is repesented as δ .

**Definition of DFA**

Finite automata,

M = (Q, Σ, δ, **q**_{0}, F), where

Q is a set of states.

Σ is a set of alphabet.

**q**_{0} ϵ Q is the initial state

F ⊆ Q is the set final states, and δ, the transition function, is a function from Q X Σ to Q.

**Representation of a DFA**

Let the machine M be a deterministic finite automata.

M = {Q, Σ, δ, **q**_{0}, F}, where

Q = {q_{0, }q_{1}}

Σ = (0, 1)

F = {q_{1}}.

q_{0} is the starting state and δ is the transition function as given below:

δ(q_{0}, 0) ⇒ q_{0}

δ(q_{0}, 1) ⇒ q_{1}

δ(q_{1}, 0) ⇒ q_{1}

δ(q_{1}, 1) ⇒ q_{0} .

The above representation of transition function is not very readable. Conventionally, there are two representations for transition function:

- 1. State transition table. 2. State transition diagram.

**State transition table**

The transition table shows the state transition table of the transition function discussed in this section.

- In the state transition table, there is a row for every state q
_{1}ϵ Q. - In the state transition table, there is a column for every alphabet A
_{i}ϵ Σ . - The starting state is marked as ‘
**→**‘. - The final state is marked as ‘
*****‘.

**State transition diagram**

The figure show the state transition diagram of the transition function discussed in this section.

**Language of the above DFA**

It is easy to see that machine remain in same state on input 0.

The machine transitions from **q**_{0} to **q**_{1} and **q**_{1} to **q**_{0} , when the input is 1.

Machine will be in state **q**_{1} (final state). after reading odd number of 1’s.

Thus we can conclude that the DFA accepts a string if and only if the number of 1’s is odd.

The language L accepted by M, the given DFA, is the set of all string having odd number of 1’s.

**Recommended:**

- Automata Theory and Formal Languages
- Kleene Closure
- Recursive Definition of a Language
- Finite Representation of language
- Introduction to Finite Automata