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

**TRANSITION DIAGRAM**

**TRANSITION TABLE**

Final State F = { q_{0} }

For test, input (W) = aaaa

Extended Transition function : δ^{^}(q ,w) = δ^{^}(q_{0} ,aaaa)

= δ (δ^{^}(q_{0} ,aaa),a)

= δ (δ (δ^( q_{0} ,aa),a),a)

= δ ( δ ( δ (δ^( q_{0} ,a),a),a),a)

= δ ( δ ( δ ( δ (δ^( q_{0} ,ɛ),a),a),a),a)

= δ ( δ ( δ ( δ ( q_{0} ,a),a),a),a)

= δ ( δ ( δ ( q_{1} ,a),a),a)

= δ ( δ ( q_{0} ,a),a)

= δ ( q_{1} ,a)

= q_{0}

**⁂ q _{0} ϵ F ( Given string is Accepted )**

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

Healing