What is the significances of extended transition function?

Question

What is the significance of the extended transition function?

Answer 1

@wa_tle

Language of a Deterministic Finite Automaton ::

A DFA defines a language. The set of all strings that result in a sequence of state transition from start state to an accepting state is the language defined by the DFA...

The language is denoted as L(M) for a DFA M = (Q, Σ, δ, F q0),

and is defined by L(M) = {w:δ*(q0, w) is in F}….

Here δ* is the extended transition function. The language represented by a DFA is regular….

In order to accept a language L, the FA has to accept all the strings in L and reject all the strings in L'(compliment of a language, i.e. strings not in the language)....

 

Extended transition function ::

The extended transition function of an automaton tells us what state ends up in after processing an entire string of characters…

In fact, the definition of is what tells us what we mean when we say "process a string"....

 The first argument is a state q and the second argument is a string w….

It returns a state just like the transition function discussed in the previous tutorials….

It can be defined as the state in which the FA ends up, if it begins in state q and receives string x of input symbols...

We define δ* recursively as follows:

For any q ϵ Q, δ*(q, є) = q ...

For any q ϵ Q and a ϵ Σ, δ*(q, ya) = δ(δ*(q,y), a) ….

For a string of length 1 δ*(q, a) = δ(q, a)....

 

1. https://gateoverflow.in/140550/Toc-dfa-extended-transition-function 

 

2. https://gateoverflow.in/191491/Extended-transition-function-of-nfa