What is an extended transition function?

Extended transition function

An extended transition function $\hat δ$ traces the path of an automaton and determines the final state when an initial state $q$ and an input string $x$ are passed through it.

The difference between a simple transition function and the extended transition function is that the former performs a transition of a single character/instance. In contrast, the latter performs the transitions on a complete string.

Steps of the recursive algorithm

A recursive algorithm is used to reach the final state, which is as follows:

1. Base condition:

2. Recursion rule:

Here, $x ∈ \Sigma^* \space and \space a ∈ \Sigma$. Also,$x$ is a string of characters belonging to the set of the input symbols and $a$ is a single character.

The input string is reduced from the right side, character by character, until the base condition—when all the strings are reduced and we are left with a null character (epsilon)—is reached. Then simple transitions are applied to the broken down string.

A transition table is formed to show each transition in the DFA. If the output is a final state, the given string will be accepted by the DFA.

Example

Suppose a DFA of the following type:

The transition table will be of the following sort:

Example string 1

Let's take an input string $abab$. Its extended transition function will be as follows:

We remove the rightmost characters one by one using the recursion rule:

Here, when the last character is separated, we are left with epsilon by default:

Next, we use the base condition:

We use the transition table to change the states according to the input:

The last transition is as follows:

Since q₂ is a final state, the DFA accepts the string abab.

Example string 2

In contrast, if we take a string $baa$, the transition function will be as follows:

We remove the rightmost characters one by one using the recursion rule:

We use the base condition:

We use the transition table to get the following:

Since q₁ is not a final state, the DFA doesn't accept the string $baa$.