2,311 views

1 Answer

0 votes
0 votes

@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

 

 

Related questions

3 votes
3 votes
0 answers
2
hs_yadav asked Jan 8, 2018
1,040 views
How to find extended transition fucntion of a NFA ...someone explain using a example.....please...and representation symbol of extended transition function....
1 votes
1 votes
0 answers
3
1 votes
1 votes
1 answer
4
rahul sharma 5 asked Jul 29, 2017
477 views
In case of NFA, assume i have defined e(epsilon transition) from qo to q1:-Now if e comes on qo,then can i stay on same qo or do i need to follow transition from qo to q1...