GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
33 views
When we define DFA extended transition function :

δ(q, e) = δ( q).

Assume this is extended transition function with q as state and e as epsilon.Now what does e means in case of DFA extended function?The above transition says it stays on same state.But DFA should hang on e,as e is not defined in DFA.?
asked in Theory of Computation by Boss (9.6k points)   | 33 views

1 Answer

0 votes
regarding DFA, δ(q, e) = δ( q). this is not a valid transition function because epsilon transitions are not defined for a DFA.

But we can consider it as a valid transition also, it means if we are not reading any input symbol then DFA remains on the same state.

Regarding extended transition function, in plcae of an input alphabet we provide string as an input for example

δ*(q0, ababa) = δ( q2). is an example of extended transition function
answered by Boss (8k points)  
Actually i think e cannot be there in transition function,but it can be there in extended transition function.I want to know  why it is allowed in extended transition function and not in transition function.
where did you read nit from?

DFA transition function is defined over sigma only. So it cant have epsilon.You can check DFA transition function definition anywhere.One is :- http://www.cs.tau.ac.il/~bchor/CM/Compute2-Printer.pdf. 1st slide.

For extended function. see http://carstenfuehrmann.org/wp-content/uploads/2012/09/lecture04.pdf See slide last.The same if there in hopcroft ullman in one example



Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3118 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,969 questions
32,072 answers
74,565 comments
30,147 users