**Language of a Deterministic Finite Automaton**

A DFA defines a language. The set of all strings that result in a sequence of state transition from start state to an accepting state is the language defined by the DFA. The language is denoted as L(M) for a DFA M = (Q, Σ, δ, F q_{0}), and is defined by

_{0}, w) is in F}.

Here δ* is the extended transition function. The language represented by a DFA is regular. In order to accept a language L, the FA has to accept all the strings in L and reject all the strings in L'(compliment of a language, i.e. strings not in the language).

**Extended transition function**

An extended transition function takes two arguments. The first argument is a state q and the second argument is a string w. It returns a state just like the transition function discussed in the previous tutorials. It can be defined as the state in which the FA ends up, if it begins in state q and receives string x of input symbols.

We define δ* recursively as follows:

- For any q ϵ Q, δ*(q, є) = q
- For any q ϵ Q and a ϵ Σ,

δ*(q, ya) = δ(δ*(q,y), a)

Question: Design a DFA for the language L = {w ϵ (a,b)*: n_{b} mod 3 > 1}.

View Answer

**Answer:**n

_{b}represents the number of b in the string. n

_{b}mod 3 gives the remainder when n

_{b}is divided by 3. n

_{b}mod 3 > 1 implies that the remainder is 2. That means the number of b can be 2, 5, 8, …

Let M = (Q, Σ, δ, F q

_{0}) be the DFA

Σ = {a, b} is given.

For the automaton

Q = {q

_{0}, q

_{1}, q

_{2}}

F = {q

_{2}}

Question on designing and programming a DFA have been covered in the next tutorial.

**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.