Deterministic finite automata

Deterministic finite automata:

A Deterministic finite automata can be represented by a 5-tuple M = (Q, ∑, δ, q₀, F) where

i.                   Q is a finite nonempty set of states

ii.                 ∑ is a finite nonempty set of input symbols

iii.              δ is a function mapping from Q x ∑  à Q  and is usually called a direct transition function. This is the unction which describes the change of states during the transition. This mapping is usually represented by a transition table or a transition diagram.

iv.              q₀ Є Q is the initial state.

v.                 F C Q is the set of final states. It is assumed here that there may be more than one final state.

Example:

Let M be the deterministic finite automaton (Q, ∑, δ, q₀, F),

where     Q={q₀,q₁}

∑= {0,1}

δ= q₀

F={ q₀} and δ  function table below

States	Input symbols
	0	1
q0	q0	q1
q1	q1	q0

It is easy to see that L(M) is the set of all strings in {0,1}^* that have an even number of  1’s. For M passes from state q₀ to q₁with 01 is read, but M essentially ignores 0’s always remaining in its current state when an 0 is read. Thus M counts 1’s module 2, and since q₀ is also the sole final state, M accepts a string if and only if the number of 1’s is even.

If M is given the input 0110,its initial configuration is (q_0,00110). Then

(q_0, 00110) |- M (q_0, 0110)

                   |- M (q_0, 110)

                   |- M (q_1,10)

                   |- M(q_0,0)

                   |- M(q_0,Є)

There fore (q_0, 0110) |-^* M (q_0, Є) and so 00110 is accepted by M.

 Transition Diagram: