GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
122 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 Veteran (15k points) 12 109 315 | 122 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 Veteran (14.9k points) 6 19 58
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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8264 Points

  4. srestha

    6296 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3966 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Famous Question im.raj
Verified Human gk
Notable Question Sanjay Sharma
Popular Question Pravin Paikrao
Notable Question Sanjay Sharma
Notable Question Vineeta
Popular Question rahul sharma 5
Famous Question rahuldb
Great Question jothee
Notable Question Vaishali Trivedi
27,324 questions
35,176 answers
84,111 comments
33,280 users