Extended transition function of DFA


Extended transition function of DFA ( δ^)

  • An extended transition function takes two argument.
  • The first argument is state (q) and the second argument is string (w).
  • It returns a state just like a transition function.
  • Denoted as δ^(q ,w)
  • The definition proceeds by induction over the length of given string (w).

Induction Basis (w has length 0 OR (|W|= 0):

In this case, w is the empty string for which we write ɛ.

we define : δ^ (q, ɛ) = q

Induction Step (from length l to length I+1):

In this case, w which has length l+1 is of the form va,
where v – String of length l and a – ѕymbol.

we define ,
δ^ (q, va) = δ( δ^ (q, v), a)

* This works because, by induction hypothesis, δ^ (q, v) is already defined.

For example:

DFA state transition diagram for the set of all string that contains even number of a’s.



Final State F = { q0 }

For test, input (W) = aaaa

Extended Transition function : δ^(q ,w) = δ^(q0 ,aaaa)
= δ (δ^(q0 ,aaa),a)
= δ (δ (δ^( q0 ,aa),a),a)
= δ ( δ ( δ (δ^( q0 ,a),a),a),a)
= δ ( δ ( δ ( δ (δ^( q0 ,ɛ),a),a),a),a)
= δ ( δ ( δ ( δ ( q0 ,a),a),a),a)
= δ ( δ ( δ ( q1 ,a),a),a)
= δ ( δ ( q0 ,a),a)
= δ ( q1 ,a)
= q0

⁂ q0 ϵ F ( Given string is Accepted )

READ : Terminologies used in the Theory Of Computation (TOC)

Sudeep Mishra

Sudeep Mishra


%d bloggers like this: