A deterministic finite automaton is a 5-tulpe ( Q, Σ, δ, F, q0), 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
q0: is a starting state, q0 ϵ 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 a1, a2, a3, . . . ., an is a sequence of input symbols. We start out with deterministic finite automata having q0, q1, q2, . . . ., qn states where q0 is the initial state and qn is the final state, the string is then processed by the transition function as follows
δ (q0, a1) = q1
δ (q1, a2) = qk
δ (qx, a) = qn
Input a1, a2, a3, . . . ., an is said to be accepted since qn 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.