GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 6

Question

In the DFA (not necessarily minimal) for a regular language $L$ over $\Sigma = \{a, b, c,d\},$ the minimum number of outgoing edges for any state is _____

Comments

My doubt was the question asked for ‘Outgoing Edges’ not ‘All edges’, so I thought in a DFA there should be just one ‘Incoming Edge’, and others outgoing. Thus 3 outgoing and 1 incoming.

Answer 1

In any DFA, a state should have a transition for all the symbols in the alphabet set.

So, the correct answer is $4.$

Comments

Correct

Thanks sir

---

Isn’t this the maximum number of outgoing edges as well? In a DFA, every state need to have a transition defined for all the input alphabets. So isn’t it the maximum and minimum as well?

---

deepz yes.

Answer 2

why it’s not 1? i was also confused , so sir written in comments but wanna highlight this , so writing it again here……..so no one can miss this point!! 

 

 only one  edge contain all alphabet set {a,b,c,d}

Then it automatically becomes 4 edges. It is for simplicity of drawing that only one line is shown.

Answer 3

In DFA we should have transition from a state for all the symbols present in alphabet. So answer is 4.