#### RGPV 2015,14,02,03

Q. What do you understand by DFA (Deterministic Finite Automata) and how is it represented ?

Ans. A DFA means Deterministic finite automata or a finite state automata or a deterministic finite state machine (DFSM) or deterministic finite acceptor (DFA).

It is a 5 tuple machine,

M = (Q, Σ, δ, q0, F)

- Q is a finite non empty set of states.
- Σ is a finite non empty set of input symbols.
- δ is a transition function, QXΣ int to Q
- q0 is an initial state belong to Q.
- F is the set of final states belong to Q.

Lets take and example to under statnd DFA,

Construct a DFA for the language accepting strings starting with ‘01’ over input alphabets ∑ = {0, 1}.

Sol. Examples of strings accepted,

- 01
- 0101
- 01000000
- 01111111, etc

Here 01 consist 2 characters, so length is 2.

So minimum number of states required = 2+1 = 3.