A deterministic finite automaton is a 5-tulpe ( Q, Σ, δ, F, q_{0}), where

Q: is a non-empty finite set of states present in the finite control.

Σ: is a non-empty finite set of input symbols which can be passed on to the finite state machine

q_{0}: is a starting state, q_{0} ϵ Q

F: is a non-empty set of final states or accepting states, set of final states is a subset of Q.

δ: is a function called transition function that takes two arguments a state and an input symbol, it returns a single state. δ maps Q x Σ to Q.

For any element q of Q and any symbol a ϵ Σ, we interpret δ(q, a) as the state to which the FA moves, if it is in a state q and receives the input a.

There can be only one starting state, but there may be more than one final state.

**Processing of strings by Deterministic Finite Automata**

Suppose a_{1}, a_{2}, a_{3}, . . . ., a_{n} is a sequence of input symbols. We start out with deterministic finite automata having q_{0}, q_{1}, q_{2}, . . . ., q_{n} states where q_{0} is the initial state and q_{n} is the final state, the string is then processed by the transition function as follows

δ (q_{0}, a_{1}) = q_{1}

δ (q_{1}, a_{2}) = q_{k}

. .

. .

. .

δ (q_{x}, a_{}) = q_{n}

Input a_{1}, a_{2}, a_{3}, . . . ., a_{n} is said to be accepted since q_{n} is the member of the set of final states. If the last state reached is not in the set of final states then it is rejected. This concept is used to design the DFA and while deciding the final states and intermediate states of the DFA.

**Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.**

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

**Related Posts:**

- Buy Computer Science Books
- Buy Automata Theory Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Apply for Automata Theory Internship